#include <iostream>
#include <time.h>
using namespace std;

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

int numswaps = 0;
void swap(int a[], int i, int j)
{
	int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
	numswaps++;
}

int select(int a[], int k, int l, int r);
void printArr(int a[], int l, int r)
{
	for (int i=l; i<=r; ++i)
		printf("%i ", a[i]);
	printf("\n");
}

void insertSort(int a[], int l, int r)
{
	for (int i=l+1; i<=r; ++i)
	{
		int j = i;
		while (j>l && a[j] < a[j-1])
		{
			swap(a,j,j-1);
			j--;
		}
	}
}

int medMed(int a[], int l, int r)
{
	int j = l-1;
	for (int i=l; i<=r; i+=5)
	{
		int rr = min(i+4,r);
		insertSort(a,i,rr);
		swap(a,++j,(i+rr)/2);
	}
	int m = (j-l)/2+1;
	return select(a,m,l,j);
}

int partition(int a[], int l, int r)
{
	int pp = medMed(a,l,r);
	swap(a[pp],a[r]);
	int p = a[r];
	int i = l-1;
	for (int j=l; j<r; ++j)
		if (a[j] < p)
			swap(a,++i,j);
	swap(a,++i,r);
	return i;
}

int numselect = 0;
int select(int a[], int k, int l, int r)
{
	numselect++;
	if (l>r) { printf("error l>r\n"); exit(-1); }
	if (l==r) { if (k == 1) return l; printf("error k!=1"); exit(-1); }
	int p = partition(a,l,r);
	if (k<p+1-l) select(a,k,l,p-1);
	else if (k>p+1-l) select(a,k-(p+1-l),p+1,r);
	else return p;
}

const int SIZE = 10000000;
int arr[SIZE+1];
void  generate()
{
	numswaps = 0;
	numselect = 0;
	for (int i=0; i<=SIZE; ++i)
		arr[i] = rand();
}
void verify(int s)
{
	int last = -1;
	for (int i=1; i<=s; ++i)
	{
		int cur = select(arr,i,0,s);
		if (last > cur) { printf("invalid"); exit(-2); }
		last = cur;
	}
}
int main() {
	clock_t begin = clock();
	for (int i=1; i<=SIZE; i*=10)
	{
		generate();
		select(arr,(1+i)/2,1,i);
		printf("#swaps for finding median of %8i elements: %8i (%i)\n", i, numswaps, numselect);
	}
	clock_t end = clock();
	double time = (double)(end - begin) / CLOCKS_PER_SEC;
	printf("Total time: %f", time);
	return 0;
}