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

I may be too specific with my needs - A general understanding of quickselect is what would help most, the code I provided is an example of it. — Edge, Jun 01 '12 at 07:56
That information from MIT is on sorting, not selecting. As far as I can see. — Edge, Jun 01 '12 at 07:57

score 71 · Accepted Answer · answered Jun 01 '12 at 08:02

71

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.

answered Jun 01 '12 at 08:02

Vikas

8,790
4
38
48

Does the code example I provided conduct those 3 checks against k? – Edge Jun 01 '12 at 08:04
I notice I don't check k == pivot – Edge Jun 01 '12 at 08:05
@Andrew, `k == pivot` is captured in the the last `else` block in your code. – Vikas Jun 01 '12 at 08:06
@Andrew, also not that `k < pivot - first` is to do the comparison with reference to the `first` index passed. – Vikas Jun 01 '12 at 08:09

score 5 · Answer 2 · answered Jan 24 '14 at 19:47

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

answered Jan 24 '14 at 19:47

Haitao

132
2
6

2

yours has a bug too. second quickSelect should be `quickSelect(items, pivot+1, last, k- (pivot-first+1));` – UmNyobe Oct 19 '15 at 08:36

score 3 · Answer 3 · edited May 23 '17 at 11:54

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.

edited May 23 '17 at 11:54

Community

1
1

answered Jun 01 '12 at 08:12

Jerry Coffin

476,176
80
629
1,111

score 1 · Answer 4 · answered Aug 21 '14 at 11:43

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

Kousik Mandal · Answer 5 · 2020-08-13T05:53:59.093

I was reading CLRS Algorithm book to learn quick select algorithm, we may implement the algorithm in easy way.

package selection;    
import java.util.Random;

/**
 * This class will calculate and print Nth ascending order element
 * from an unsorted array in expected time complexity O(N), where N is the
 * number of elements in the array.
 * 
 * The important part of this algorithm the randomizedPartition() method.
 * 
 * @author kmandal
 *
 */
public class QuickSelect {
    public static void main(String[] args) {
        int[] A = { 7, 1, 2, 6, 0, 1, 96, -1, -100, 10000 };
        for (int i = 0; i < A.length; i++) {
            System.out.println("The " + i + "th ascending order element is "
                    + quickSelect(A, 0, A.length - 1, i));
        }
    }

    /**
     * Similar to Quick sort algorithm partitioning approach works, but after
     * that instead of recursively work on both halves here will be recursing
     * into desired half. This step ensure to the expected running time to be
     * O(N).
     * 
     * @param A
     * @param p
     * @param r
     * @param i
     * @return
     */
    private static int quickSelect(int[] A, int p, int r, int i) {
        if (p == r) {
            return A[p];
        }
        int partitionIndex = randomizedPartition(A, p, r);
        if (i == partitionIndex) {
            return A[i];
        } else if (i < partitionIndex) {// element is present in left side of
                                        // partition
            return quickSelect(A, p, partitionIndex - 1, i);
        } else {
            return quickSelect(A, partitionIndex + 1, r, i);// element is
                                                            // present in right
            // side of partition
        }
    }

    /**
     * 
     * Similar to Quick sort algorithm this method is randomly select pivot
     * element index. Then it swap the random pivot element index with right
     * most element. This random selection step is expecting to make the
     * partitioning balanced. Then in-place rearranging the array to make all
     * elements in the left side of the pivot element are less than pivot
     * element and the right side elements are equals or grater than the pivot
     * element. Finally return partition index.
     * 
     * @param A
     * @param p
     * @param r
     * @return
     */
    private static int randomizedPartition(int[] A, int p, int r) {
        int partitionIndex = p;
        int random = p + new Random().nextInt(r - p + 1);// select
                                                            // pseudo random
                                                            // element
        swap(A, random, r);// swap with right most element
        int pivot = A[r];// select the pivot element
        for (int i = p; i < A.length - 1; i++) {
            if (A[i] < pivot) {
                swap(A, i, partitionIndex);
                partitionIndex++;
            }
        }
        swap(A, partitionIndex, r);
        return partitionIndex;
    }

    /**
     * Swapping 2 elements in an array.
     * 
     * @param A
     * @param i
     * @param j
     */
    private static void swap(int[] A, int i, int j) {
        if (i != j && A[i] != A[j]) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}


Output:
The 0th ascending order element is -100
The 1th ascending order element is -1
The 2th ascending order element is 0
The 3th ascending order element is 1
The 4th ascending order element is 1
The 5th ascending order element is 2
The 6th ascending order element is 6
The 7th ascending order element is 7
The 8th ascending order element is 96
The 9th ascending order element is 10000

I still think you could add some explanations to your code. – mate00 Aug 12 '20 at 14:17 — mate00, Aug 12 '20 at 14:17
I have added meaningful description. – Kousik Mandal Aug 13 '20 at 05:26 — Kousik Mandal, Aug 13 '20 at 05:26

score 0 · Answer 6 · edited Jan 21 '17 at 09:43

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

This is incorrect, when `pivotIndex == k` the value on that index is returned, whilst in other the `partition` is called and the index of the partition is returned. No idea why this has been up voted. — Samer Tufail, Dec 22 '17 at 06:46

QuickSelect Algorithm Understanding

6 Answers6

Linked