Lecture on Pointer Arrays and Quick Sort in C

Overview

• Simple example of pointer arrays in C, taken from a textbook.
• Implements a program that sorts a sequence of strings entered by the user.

Data Structure

• Array of Pointer Arrays
  • Uses an array of character pointers (char*) which point to arrays of characters (strings).
  • Example array defined with three char* pointers.

Program Steps

1. Input Handling

   • Get a sequence of strings from command line input.
   • Store strings in a static structure.
   • Example inputs: "defghi", "jklmnopqrst", "abc".

2. Sorting

   • Sort the array of strings alphabetically.
   • Example sorted order: "abc", "defghi", "jklmnopqrst".

3. Output

   • Print the sorted list of strings.

Function Descriptions

Main Function

• Calls readlines, qsort, and writelines functions.
• Handles input, sorting, and output.

Readlines Function

• Receives up to 'n' lines from standard input (keyboard).
• Stores strings in a char* array called lineptr.
• Handles error by returning a negative number if input is too large.*

Writelines Function

• Prints the list of strings stored in lineptr using a loop.

Qsort Function

• Implements a recursive Quick Sort algorithm.
• Uses left and right indices to sort subarrays.
• Base Case: If left >= right, the array is either empty or has one element.
• Uses strcmp for string comparison.

Swap Function

• Swaps two indices in the same array using a temporary variable.

Detailed Steps

Readlines Function

• Uses a while loop to call getline (or fgets as a common alternative).
• Checks line length; uses a max length of 999 characters.
• Allocates memory using malloc (or alloc in textbook).
• Copies line into heap and stores reference in lineptr array.

Qsort Algorithm Explanation

• Picks a pivot (middle element).
• Moves elements less than pivot to the left, greater to the right.
• Recursively sorts left and right subarrays.
• Uses a swap function to reorder elements.

Example of Quick Sort

• Illustration with numbers for simplicity.
• Chooses a pivot and rearranges elements.
• Continues recursively until the array is sorted.

Error Handling

• If readlines encounters an error (e.g., memory full), it returns negative.
• Error message "input too big to sort" is printed if input exceeds limits.

Conclusion

• Demonstrated a simple C program utilizing pointer arrays and quick sort to alphabetically sort strings.
• Key functions: readlines, writelines, qsort, and swap.