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

You can find quickSelect here using 3-way partitioning.

The code is written in Scala. In addition, I will be adding more algorithms and data structures in my journey to mastering the subject.

You can also notice that there's a median function for arrays with an odd number of elements implemented using quickSelect.

edit: It is required to shuffle the array to guarantee a linear average running time

Answer 3

Partition is pretty simple: it rearranges the elements so those less than a selected pivot are at lower indices in the array than the pivot and those larger than the pivot are at higher indices in the array.

I talked about the rest it in a previous answer.

Answer 4

int quickSelect(int A[], int l, int h,int k)
{
        int p = partition(A, l, h); 
        if(p==(k-1)) return A[p];
        else if(p>(k-1)) return quickSelect(A, l, p - 1,k);  
        else return quickSelect(A, p + 1, h,k);

}

// partition function same as QuickSort

Answer 5

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

Answer 6

int partition(vector<int> &vec, int left, int right, int pivotIndex)
{
        int pivot = vec[pivotIndex];
        int partitionIndex = left;

        swap(vec[pivotIndex],vec[right]);
        for(int i=left; i < right; i++) {
                if(vec[i]<pivot) {
                        swap(vec[i],vec[partitionIndex]);
                        partitionIndex++;
                }
        }
        swap(vec[partitionIndex], vec[right]);

        return partitionIndex;
}

int select(vector<int> &vec, int left, int right, int k)
{
        int pivotIndex;
        if (right == left) {
                return vec[left];
        }
        pivotIndex = left + rand() % (right-left);

        pivotIndex = partition(vec,left,right,pivotIndex);
        if (pivotIndex == k) {
                return vec[k];
        } else if(k<pivotIndex) {
                /*k is present on the left size of pivotIndex*/
                return partition(vec,left,pivotIndex-1, k);
        } else {
                /*k occurs on the right size of pivotIndex*/
                return partition(vec, pivotIndex+1, right, k);
        }
        return 0;
}