QuickSelect Algorithm Understanding

Question

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     } } 

Courtesty: @Haitao

Answer 1

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:

1. 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.
2. k < pivot. Then kth smallest is on the left side of pivot.
3. 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.

Answer 2

btw, your code has a few bugs..

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     } }