Description
Quickselect is a powerful algorithm for finding the kth smallest element in an unordered list. It works by selecting any element from a list, which we will call a "pivot". Then, we can put every element "smaller" than the pivot to its left and every element "larger" than the pivot to its right. By doing so, we can determine whether the kth smallest element is to the left of the pivot, to the right of the pivot, or is the pivot. To demonstrate how it works, we will be asking you to implement two functions:
void SwapString(char **str1, char **str2);
This function should swap strings str1 and str2.
For example, if we have an array of fruit names A and we call SwapString(&A[2], &A[6]), the resulting array will be:
int Partition(char **A, int l, int r);
This function should choose any string from the index between l and r (inclusively) and use that string to partition the strings in the range. After that, return the index where your pivot ended up at.
For example, if we have an array of fruit names, A, and we call Partition(A, 2, 6), the resulting array might look like this:
and the function will return 5, which is the index of the pivot ("Pear").
The QuickSelect algorithm works as follows:
Suppose we want to find the 4th smallest element (in human notation). First, a pivot is selected from a list:
Then, all elements that come before the pivot are moved before it, and all elements that come after the pivot are moved after it. In this case, no elements come after "Watermelon", so the array looks the same.
At this point, we know the smallest element is not the pivot nor after it, so we can repeat the same process on the array before the pivot. We select another pivot:
And partition the array:
Since the index of the pivot is 4, it must be the 5th smallest element. Thus, we can ignore the elements after it and itself:
We can continue this process until we find our desired element.
Hint: You can use the function strcmp() to compare the strings.
Input
The first line contains an integer N.
The next N lines contain a string.
The last line contains another integer k.
Output
The kth smallest string in the list.