Skip to content

Instantly share code, notes, and snippets.

@andlima
Created February 8, 2012 21:34
Show Gist options
  • Save andlima/1774060 to your computer and use it in GitHub Desktop.
Save andlima/1774060 to your computer and use it in GitHub Desktop.
Median of medians selection algorithm
int find_kth(int *v, int n, int k) {
if (n == 1 && k == 0) return v[0];
int m = (n + 4)/5;
int *medians = new int[m];
for (int i=0; i<m; i++) {
if (5*i + 4 < n) {
int *w = v + 5*i;
for (int j0=0; j0<3; j0++) {
int jmin = j0;
for (int j=j0+1; j<5; j++) {
if (w[j] < w[jmin]) jmin = j;
}
swap(w[j0], w[jmin]);
}
medians[i] = w[2];
} else {
medians[i] = v[5*i];
}
}
int pivot = find_kth(medians, m, m/2);
delete [] medians;
for (int i=0; i<n; i++) {
if (v[i] == pivot) {
swap(v[i], v[n-1]);
break;
}
}
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 find_kth(v, store, k);
} else {
return find_kth(v+store+1, n-store-1, k-store-1);
}
}
@Noble-Mushtak
Copy link

@liqiu This is not an error. The above algorithm uses selection sort to find the minimum three elements out of the sublist of five elements. Then, it takes the third element (medians[i] = w[2]) to be the median of that sublist. However, because we only care about the median, there is no point in sorting the last two elements of the list, so the fact that the last two elements in the sublist of five elements might be swapped does not actually impact the algorithm since those last two elements do not affect the median.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment