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);
}
}
@bjuergens
Copy link

note: swap comes from #include

And when calling the function, the params are:

  • v: first int in an interval in array (e.g. the first element in the array)
  • n: size of interval (e.g. the size of the array)
  • k: the k-th biggest element will be returned

I thought this was note-worthy, because this showed up as the first google-result when looking for c++ implementations of Median of medians selection algorithm

@sihyun222
Copy link

this code have an error

@OkazakiNaoki
Copy link

You are not reading what wotanii said.
Just include algorithm and using namespace std.

@liqiu
Copy link

liqiu commented Dec 9, 2018

There is minor error in sorting:

int main()
{
int w[5] = {3, 6, 7, 5, 4};

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

    for (int i = 0; i < 5; i++)
            printf("%d ", w[i]);

    printf("\n");

}

output: 3 4 5 7 6

@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