Median of medians selection algorithm

gistfile1.cpp

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

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

this code have an error

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

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

@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.