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

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

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

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