/**  * Implement kth select.  *  * Use the provided random object to select your pivots.  * For example if you need a pivot between a (inclusive)  * and b (exclusive) where b > a, use the following code:  *  * int pivotIndex = r.nextInt(b - a) + a;  *  * It should be:  * in-place  *  * Have a worst case running time of:  * O(n^2)  *  * And a best case running time of:  * O(n)  *  * You may assume that the array doesn't contain any null elements.  *  * Make sure you code the algorithm as you have been taught it in class.  * There are several versions of this algorithm and you may not get full  * credit if you do not implement the one we have taught you!  *  * @throws IllegalArgumentException if the array or comparator or rand is  * null or k is not in the range of 1 to arr.length  * @param  data type to sort  * @param k the index to retrieve data from + 1 (due to 0-indexing) if  * the array was sorted; the 'k' in "kth select"; e.g. if k ==  * 1, return the smallest element in the array  * @param arr the array that should be modified after the method  * is finished executing as needed  * @param comparator the Comparator used to compare the data in arr  * @param rand the Random object used to select pivots  * @return the kth smallest element  */ public static  T kthSelect(int k, T[] arr, Comparator comparator, Random rand) { }

K-Select (Quickselect) A. Premise - you want to find a specific value in an array, eg. the smallest, second smallest, third smallest, etc. where you would know which index it would be at if the array was sorted 1. For example, the smallest element will always be at index 0, the second smallest at index 1, etc.; the kth smallest element is at index k-1 B. Algorithm - italicized steps are the exact same as quicksort 1. calculate the index of your random pivot between indices start and end inclusive- swap the pivot with the element at start 2. initialize i to start 1 and i to end 3. while i has not crossedj a) move i until it has crossed j or the data at i is > pivot b) move j until it has crossed i or the data at j is k-1 - recursively call quicksort on left side (start toj-1) 6. ifje k-1 recursively call quicksort on the right side(j+1 to end) C. Qualities - unstable, in place 1. Best case O(n) - different from best case quicksort because instead of recursing on both halves for each iteration, you only recurse on one half 2. Worst case O(n2) - bad pivots K-Select (Quickselect) A. Premise - you want to find a specific value in an array, eg. the smallest, second smallest, third smallest, etc. where you would know which index it would be at if the array was sorted 1. For example, the smallest element will always be at index 0, the second smallest at index 1, etc.; the kth smallest element is at index k-1 B. Algorithm - italicized steps are the exact same as quicksort 1. calculate the index of your random pivot between indices start and end inclusive- swap the pivot with the element at start 2. initialize i to start 1 and i to end 3. while i has not crossedj a) move i until it has crossed j or the data at i is > pivot b) move j until it has crossed i or the data at j is k-1 - recursively call quicksort on left side (start toj-1) 6. ifje k-1 recursively call quicksort on the right side(j+1 to end) C. Qualities - unstable, in place 1. Best case O(n) - different from best case quicksort because instead of recursing on both halves for each iteration, you only recurse on one half 2. Worst case O(n2) - bad pivots