QuickSelect Algorithm Understanding
algorithm, quickselect
Solution
The important part in quick select is partition. So let me explain that first.
Partition in quick select picks a `pivot` (either randomly or first/last element). Then it rearranges the list in a way that all elements less than `pivot` are on left side of pivot and others on right. It then returns index of the `pivot` element.
Now here we are finding kth smallest element. After partition cases are:
- `k == pivot`. Then you have already found kth smallest. This is because the way partition is working. There are exactly `k - 1` elements that are smaller than the `kth` element.
- `k < pivot`. Then kth smallest is on the left side of `pivot`.
- `k > pivot`. Then kth smallest is on the right side of pivot. And to find it you actually have to find `k-pivot` smallest number on right.
Problem
I've been poring over various tutorials and articles that discuss quicksort and quickselect, however, my understanding of them is still shaky. Given this code structure, I need to be able to grasp and explain how quickselect works. ``` // return the kth smallest item int quickSelect(int items[], int first, int last, int k) { int pivot = partition(items, first, last); if (k < pivot-first) { return quickSelect(items, first, pivot, k); } else if (k > pivot) { return quickSelect(items, pivot+1, last, k-pivot); } else { return items[k]; } } ``` I need a little help with breaking down into pseudo-code, and while I haven't been provided with the partition function code, I'd like to understand what it would do given the quickselect function provided. I know how quicksort works, just not quickselect. The code I just provided is an example we were given on how to format quick select. EDIT: The corrected code is ``` int quickSelect(int items[], int first, int last, int k) { int pivot = partition(items, first, last); if (k < pivot-first+1) { //boundary was wrong return quickSelect(items, first, pivot, k); } else if (k > pivot-first+1) {//boundary was wrong return quickSelect(items, pivot+1, last, k-pivot); } else { return items[pivot];//index was wrong } } ```