median of medians select

gistfile1.cpp

#include <iostream>

using namespace std;

int select(int array[], int left, int right, int k) {
    int len = right - left;
    if (len <= 10) {
        for (int i = left + 1; i < right; ++i) {
            for (int j = i; j > left; --j) {
                if (array[j] < array[j - 1]) {
                    array[j - 1] = array[j - 1]^array[j];
                    array[j] = array[j - 1]^array[j];
                    array[j - 1] = array[j - 1]^array[j];
                }
            }
        }
        return left + k - 1;
    }
    int group_nums = len / 5;
    int x[group_nums];
    for (int i = 0; i < group_nums; ++i) {
        x[i] = array[select(array, left + i * 5, left + (i + 1) * 5, 3)];
    }
    int median = select(x, 0, group_nums, len / 10);
    for (int i = left; i < right; ++i) 
        if (x[median] == array[i]) {
            median = i;
            break;
        }
    array[left] = array[left]^array[median];
    array[median] = array[left]^array[median];
    array[left] = array[left]^array[median];
    int i = left + 1;
    int j = right - 1; 
    while (i < j) {
        while (array[i] < array[left]) ++i;
        while (array[j] > array[left]) --j;
        if (j <= i) break;
        array[i] = array[i]^array[j];
        array[j] = array[i]^array[j];
        array[i] = array[i]^array[j];
    }
    array[left] = array[left]^array[j];
    array[j] = array[left]^array[j];
    array[left] = array[left]^array[j];
    int t = j - left + 1;
    if (k == t) return j;
    if (k < t) 
        return select(array, left, j , k);
    else 
        return select(array, j + 1, right, k - t);
}

int main() {
    int n = 20;
    //cout << "input array size n" << endl;
    //cin >> n;
    int array[n];
    //cout << "input array element:" << endl;
    for (int i = 0; i < n; ++i) {
        array[i] = n - i;
    }

    cout << array[select(array, 0, n, 11)] << endl;
    cout << "k\tvalue" << endl;
    for (int i = 1; i <= n; ++i) {
        cout << i << "\t" << array[select(array, 0, n, i)] << endl;
    }
    return 0;
}