O(n) Selection

#include <stdio.h>
#include <stdlib.h>

#define min(a,b) (((a)<(b))?(a):(b))

void swap(int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}

void selection_sort(int *x, int n)
{
	for(int k=0;k<n-1;k++)
	{
		int min_position = k;
		for(int i=k;i<n;i++)
			if (x[min_position] > x[i])
				min_position = i;
		swap(x[min_position], x[k]);
	}
}

int select(int *x, int n, int k);

int choose_pivot(int *x, int n)
{
	for(int start=0;start<n;start+=5)
		selection_sort(x+start, min(5, n-start));
	for(int i=0;i<n/5;i++)
	{
		int start = i*5;
		int end = min(n-1, start+5-1);
		int mid = (start+end)/2;
		swap(x[i], x[mid]);
	}
	return select(x, n/5, n/10);
}

int partition(int *x, int n)
{
	int pivot_position = choose_pivot(x, n);
	swap(x[pivot_position], x[0]);
	int last = 1;
	for(int i=1;i<n;i++)
		if (x[0] >= x[i])
		{
			swap(x[last], x[i]);
			last++;
		}
	swap(x[last-1], x[0]);
	return last-1;
}

int select(int *x, int n, int k)
{
	if (n <= 1)
		return 0;
	else
	{
		int mid = partition(x, n);
		if (k == mid)
			return mid;
		else if (k < mid)
			return select(x, mid, k);
		else
			return select(x+mid+1, n-mid-1, k-mid-1);
	}
}

int a[10000];

#define FOR(__i, __times) for(int __i=0;__i<__times;__i++)

int main()
{
	FOR(i, 10000)
		a[i] = rand() % 32767;
	int answer = select(a, 10000, 5000);
	printf("%d\n", answer);
	return 0;
}