Skip to content

Instantly share code, notes, and snippets.

@andlima
Created February 9, 2012 02:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andlima/1776496 to your computer and use it in GitHub Desktop.
Save andlima/1776496 to your computer and use it in GitHub Desktop.
Quick selection algorithm
int quick_find_kth(int *v, int n, int k) {
if (n == 1 && k == 0) return v[0];
int pivot = v[n-1];
int store = 0;
for (int i=0; i<n-1; i++) {
if (v[i] < pivot) {
swap(v[i], v[store++]);
}
}
swap(v[store], v[n-1]);
if (store == k) {
return pivot;
} else if (store > k) {
return quick_find_kth(v, store, k);
} else {
return quick_find_kth(v+store+1, n-store-1, k-store-1);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment