#include <iostream>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
using namespace std;
int medianSearch(int A[], int size, int k)
{
int *lows = (int *)calloc(size, sizeof(int));
int lowsLen = 0;
int *highs = (int *)calloc(size, sizeof(int));
int highsLen = 0;
int *pivots = (int *)calloc(size, sizeof(int));
int pivotsLen = 0;
int median;
int pivot;
int i;
if (size == 1)
return A[0];
// Other ways of randomly picking a pivot
// pivot = 0;
// pivot = size-1;
// pivot = size/2;
assert(size > 0);
pivot = rand() % size;
for (i = 0; i < size; ++i)
{
if (A[i] < A[pivot])
{
lows[lowsLen] = A[i];
lowsLen++;
}
else if (A[i] > A[pivot])
{
highs[highsLen] = A[i];
highsLen++;
}
else
{
pivots[pivotsLen] = A[i];
pivotsLen++;
}
}
if (k < lowsLen)
median = medianSearch(lows, lowsLen, k);
else if (k < lowsLen + pivotsLen)
median = A[pivot];
else
median = medianSearch(highs, highsLen, k - lowsLen - pivotsLen);
free(lows);
free(highs);
free(pivots);
return median;
}
int compare(const void *a, const void *b)
{
return ( *(int *)a - *(int *)b );
}
int medianSorted(int A[], int size, int k)
{
qsort(A, size, sizeof(int), compare);
return A[k];
}
#define N 1000
int main()
{
int arr[N];
int brr[N];
int n = sizeof(arr) / sizeof(arr[0]);
int k = 200;
int x;
int y;
for (int i = 0; i < n; ++i)
arr[i] = brr[i] = rand();
x = medianSearch(arr, n, (k-1)%n);
y = medianSorted(brr, n, (k-1)%n);
string suffix;
switch (k % 10)
{
case 1: suffix = "st"; break;
case 2: suffix = "nd"; break;
case 3: suffix = "rd"; break;
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:
case 0: suffix = "th"; break;
}
cout << k << suffix << " smallest is: " << x << endl;
cout << k << suffix << " smallest is: " << y << endl;
}
