#line 115 "select.nw"
#include <algorithm>
#line 312 "select.nw"
#include <stdlib.h>
#line 360 "select.nw"
#include <iostream>

#line 117 "select.nw"
using std::swap;

#line 200 "select.nw"
template <typename T>
int median5(T* a) {
    int a0 = a[0];
    int a1 = a[1];
    int a2 = a[2];
    int a3 = a[3];
    int a4 = a[4];
#line 211 "select.nw"
    if (a1 < a0) 
	swap(a0, a1);
    if (a2 < a0)
	swap(a0, a2); 
    if (a3 < a0)
	swap(a0, a3);
    if (a4 < a0)
	swap(a0, a4);

    if (a2 < a1)
	swap(a1, a2);
    if (a3 < a1)
	swap(a1, a3);
    if (a4 < a1)
	swap(a1, a4);

    if (a3 < a2)
	swap(a2, a3);
    if (a4 < a2)
	swap(a2, a4);
#line 238 "select.nw"
    if (a2 == a[0])
	return 0;
    if (a2 == a[1])
	return 1;
    if (a2 == a[2])
	return 2;
    if (a2 == a[3])
	return 3;
    // else if (a2 == a[4])
        return 4;
}

#line 267 "select.nw"
template <typename T>
int partition(T a[], int size, int pivot) {
    int pivotValue = a[pivot];
    swap(a[pivot], a[size-1]);
    int storePos = 0;
    for(int loadPos=0; loadPos < size-1; loadPos++) {
	if (a[loadPos] < pivotValue) {
	    swap(a[loadPos], a[storePos]);
	    storePos++;
	}
    }
    swap(a[storePos], a[size-1]);
    return storePos;
}

#line 131 "select.nw"
template <typename T>
void select(T a[], int size, int k) {
    
#line 103 "select.nw"
    if (size < 5) {
	for (int i=0; i<size; i++)
	    for (int j=i+1; j<size; j++)
		if (a[j] < a[i])
		    swap(a[i], a[j]);
	return;
    }


#line 135 "select.nw"
    
#line 156 "select.nw"
int groupNum = 0;
int* group = a;
for( ; groupNum*5 <= size-5; group += 5, groupNum++) {
    swap(group[median5(group)], a[groupNum]);
}
int numMedians = size/5;
// Index of median of medians
int MOMIdx = numMedians/2;
select(a, numMedians, MOMIdx);


#line 137 "select.nw"
    int newMOMIdx = partition(a, size, MOMIdx);
    if (k != newMOMIdx) {
	if (k < newMOMIdx) {
	    select(a, newMOMIdx, k);
	} else /* if (k > newMOMIdx) */ {
	    select(a + newMOMIdx + 1, size - newMOMIdx - 1, k - newMOMIdx - 1);
	}
    }
}


#line 75 "select.nw"
template <typename T>
void selectRandom(T a[], int size, int k) {
    
#line 103 "select.nw"
    if (size < 5) {
	for (int i=0; i<size; i++)
	    for (int j=i+1; j<size; j++)
		if (a[j] < a[i])
		    swap(a[i], a[j]);
	return;
    }

#line 78 "select.nw"
    int pivotIdx = partition(a, size, rand() % size);
    if (k != pivotIdx) {
	if (k < pivotIdx) {
	    selectRandom(a, pivotIdx, k);
	} else /* if (k > pivotIdx) */ {
	    selectRandom(a + pivotIdx + 1, size - pivotIdx - 1, k - pivotIdx - 1);
	}
    }
}


#line 302 "select.nw"
const int SEED = 352302;

void makeRandomArray(int* a, int size) {
    srand(SEED);
    for (int i=0; i<size; i++) {
	a[i] = rand();
    }
}

#line 317 "select.nw"
int main(int argc, char* argv[]) {
    int size = atoi(argv[1]);
    int* a = new int[size];

    makeRandomArray(a, size);
    clock_t selectBegin = clock();
    select(a, size, size/2);
    clock_t selectEnd = clock();
    int selectResult = a[size/2];

    makeRandomArray(a, size);
    clock_t selectRandomBegin = clock();
    selectRandom(a, size, size/2);
    clock_t selectRandomEnd = clock();
    int selectRandomResult = a[size/2];

    makeRandomArray(a, size);
    clock_t sortBegin = clock();
    std::sort(a, a+size);
    clock_t sortEnd = clock();
    int sortResult = a[size/2];

    delete[] a;
#line 344 "select.nw"
    using std::cout;
    using std::endl;

    if (!(selectResult == selectRandomResult &&
	  selectRandomResult == sortResult)) {
        cout << "Inconsistent result" << endl;
    }

    cout << "Select time (ms): " << double(selectEnd-selectBegin)*1000/CLOCKS_PER_SEC << endl;
    cout << "Randomized select time (ms): " << double(selectRandomEnd-selectRandomBegin)*1000/CLOCKS_PER_SEC << endl;
    cout << "Sort time (ms): " << double(sortEnd-sortBegin)*1000/CLOCKS_PER_SEC << endl;
    
    return 0;
}