Find the kth smallest element in an unordered list.

quickselect.cpp

//
//  http://en.wikipedia.org/wiki/Quickselect
//  Quickselect
//
//  Find the kth smallest element in an unordered list
//

#include <iostream>
using namespace std;

int partition(int list[], int left, int right, int pivotIndex)
{
    int pivotValue = list[pivotIndex];
    swap(list[pivotIndex], list[right]);  // Move pivot to end
    int storeIndex = left;
    for (int i = left; i < right; i++)
        if (list[i] < pivotValue) {
            swap(list[storeIndex], list[i]);
            storeIndex++;
        }
    swap(list[right], list[storeIndex]);  // Move pivot to its final place
    return storeIndex;
}

int select(int list[], int left, int right, int k)
{
    if (left == right)
        return list[left];
    while (true) {
        int pivotIndex = (left + right) / 2;    // select pivotIndex between left and right
        pivotIndex = partition(list, left, right, pivotIndex);
        if (k == pivotIndex)
            return list[k];
        else if (k < pivotIndex)
            right = pivotIndex - 1;
        else
            left = pivotIndex + 1;
    }
}

int main(int argc, const char * argv[])
{
    int k = 3;
    int list[] = {2, 5, 7, 8, 3};
    cout << select(list, 0, 4, k-1) << endl;
    return 0;
}