select.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void insertion_sort(int a[], int size) {
  for (int i = 1; i < size; ++i) {
		int key = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > key) {
			a[j + 1] = a[j];
			--j;
		}
		a[j + 1] = key;
	}
}

int partition(int a[], int p, int r, int key) {
	int j = p - 1;
	for (int i = p; i < r; ++i) {
		if (a[i] <= key) {
			++j;
			int tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
		}
	}
	return j + 1;
}

int select(int a[], int p, int r, int index) {
	if (r - p <= 5) {
		insertion_sort(a + p, r - p);
		return a[p + index - 1];
	}
	int length = r - p;
	int n = length / 5 + (length % 5 != 0);
	int k = p;
	for (int i = p; i < r; i += 5) {
		insertion_sort(a + i, 5);
		swap(a[k++], a[i + 2]);
	}
	int mid_mid = select(a, p, p + n, (n + 1) / 2);
	int x = partition(a, p, r, mid_mid);
	if (x == index) {
		return a[x];
	}
	else if (x > index) {
		return select(a, p, x - 1, index);
	}
	else {
		return select(a, x + 1, p, index - x);
	}
}

void print(int a[], int size) {
	for (int i = 0; i < size; ++i) {
		cout << a[i] << " ";
	}
	cout << endl;
}

class Less {
public:
	int operator()(int a, int b) {
		return a <= b;
	}
};

int main() {
	//int a[] = {3, 0, 3, 8, 2,
			   //5, 9, 1, 0, 3,
			   //6, 8, 1, 9, 4,
			   //9, 0, 2, 3, 8,
			   //0, 2, 9, 1, 3,
			   //6, 4, 3};
	int a[] = {1, 3, 6, 27, 5,
			   2, 19, 18, 10, 21,
			   8, 7, 6, 9, 11,
			   4, 28, 14, 12, 20,
			   24, 25, 17, 16, 22,
			   13, 23, 15};
	int size = sizeof(a) / sizeof(*a);
	print(a, size);
	vector<int> iv;
	for (int i = 0; i < size; ++i) {
		iv.push_back(a[i]);
	}
	sort(iv.begin(), iv.end(), Less());
	for (int i = 0; i < size; ++i) {
		cout << iv[i] << " ";
	}
	cout << endl;
	int w = select(a, 0, size, 3);
	//cout << "w: " << w << endl;
	print(a, size);


	return 0;
}