I will give thumbs up for the answer. I have provided all the documentation needed below. Please let me know if something isn't clear.

please let me know what kind of info you need so I can edit the question! What's not clear?

Divide and conquer: quick selection (10 points)

Implement the QuickSelect method found in figure 1.12 on page 36. As you can see from that pseudocode, you will have to choose a pivot. I suggest randomly generating an index p and select A[p]. You will also have to implement the partition method as well, which you can find in figure 1.8 on page 29. Call the program Select.java or select.py. The input will be a list of numbers in a text file. Have your program take the name of the file from the command line, as in past programs.

Also implement a main method or section that:

1. Reads the data from the input file into the array A. This is a list of integers, each separated from the next by one or more whitespace characters.
2. Calls the QuickSelect method 3 times, each one taking A and the parameter k set, successively, to 4, n/2, n-1.
3. Prints a suitable message with k and the value returned by the quick select method.

Warning Do NOT sort the array! Doing so will result in a score of 0. Sorting requires at least O(n lg n) steps and quick select is supposed to run in linear time.

Use the file finalexamselect.txt for testing. To see what the outputs should be, sort the numbers separately (not in the program!) and look at the values in positions 4, n/2, and n-1.

QuickSelect method, figure 1.12 on page 36:

Partition method, figure 1.8 on page 29:

finalexamselect.txt

20 25 3 239 6 184 211 155 245 25 13 73 73 82 70 164 164 102 193 44 205 250 145 102 95 83 152 168 148 193 54 228 86 244 10 26 181 106 53 209 249 21 150 213 92 234 135 121 54 8 241 252 68 169 165 159 182 56 58 158 72 15 19 10 

Quickselect The generic quickselect algorithm chooses a pivot element, partitions the array using the same PARTITION subroutine as QUICKSORT, and then recursively searches only one of the two subarrays, specifically, the one that contains the kth smallest element of the original input array. Pseudocode for quickselect is given in Figure 1.12. 35 1. RECURSION QUICKSELECT(A[1..n],k): if n=1 return A[1] else Choose a pivot element A[p] s PARTITION(A[1..n],p) if k r return QUICKSELECT(A[r +1..n],k-r) else return A[r] Figure 1.12. Quickselect, or one-armed quicksort This algorithm has two important features. First, just like quicksort, the correctness of quickselect does not depend on how the pivot is chosen. Second, even if we really only care about selecting medians (the special case k= n/2), Hoare's recursive strategy requires us to consider the more general selection problem; the median of the input array A[1.. n] is almost never the median of either of the two smaller subarrays Ai..r-1] or Ar +1..n). RK CUSTOMER SERVICE This algorithm has two important features. First, just like quicksort, the correctness of quickselect does not depend on how the pivot is chosen. Second, even if we really only care about selecting medians (the special case k = n/2), Hoare's recursive strategy requires us to consider the more general selection problem; the median of the input array A[1.. n] is almost never the median of either of the two smaller subarrays A[1..r-1] or A[r +1..n]. The worst-case running time of QUICKSELECT obeys a recurrence similar to QUICKSORT. We don't know the value of r, or which of the two subarrays we'll recursively search, so we have to assume the worst. T(n) s max max{T(r 1),T(n-r)} +O(n) 11) for i=1 to n-1 Choose a pivot element A[p] if A[i]