/* Copyright (C) 1999 Lucent Technologies */

/* From 'Programming Pearls' by Jon Bentley */

/* sort.cpp -- test and time sorting algorithms

Input lines: algnum n mod

Output lines: algnum n mod clicks nanosecs_per_elem

This is predominantly a C program; the only use of C++

sort function immediately below the include line.

*/

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// To change from C++ back to C, remove the following two lines

// and the call to sort in main

#include <algorithm>

using namespace std;

/* Data and supporting functions */

#define MAXN 10000000

typedef int DType;

DType realx[MAXN];

int *x = realx; /* allow x to shift for heaps */

int n;

void swap(int i, int j)

{ DType t = x[i];

x[i] = x[j];

x[j] = t;

}

int randint(int l, int u)

{ return l + (RAND_MAX*rand() + rand()) % (u-l+1);

}

/* LIBRARY QSORT */

int intcomp(int *x, int *y)

{ return *x - *y;

}

/* INSERTION SORTS */

/* Simplest insertion sort */

void isort1()

{ int i, j;

for (i = 1; i < n; i++)

for (j = i; j > 0 && x[j-1] > x[j]; j--)

swap(j-1, j);

}

/* Write swap function inline */

void isort2()

{ int i, j;

DType t;

for (i = 1; i < n; i++)

for (j = i; j > 0 && x[j-1] > x[j]; j--) {

t = x[j];

x[j] = x[j-1];

x[j-1] = t;

}

}

/* Move assignments to and from t out of loop */

void isort3()

{ int i, j;

DType t;

for (i = 1; i < n; i++) {

t = x[i];

for (j = i; j > 0 && x[j-1] > t; j--)

x[j] = x[j-1];

x[j] = t;

}

}

/* QUICKSORTS */

/* Simplest version, Lomuto partitioning */

void qsort1(int l, int u)

{ int i, m;

if (l >= u)

return;

m = l;

for (i = l+1; i <= u; i++)

if (x[i] < x[l])

swap(++m, i);

swap(l, m);

qsort1(l, m-1);

qsort1(m+1, u);

}

/* Sedgewick's version of Lomuto, with sentinel */

void qsort2(int l, int u)

{ int i, m;

if (l >= u)

return;

m = i = u+1;

do {

do i--; while (x[i] < x[l]);

swap(--m, i);

} while (i > l);

qsort2(l, m-1);

qsort2(m+1, u);

}

/* Two-way partitioning */

void qsort3(int l, int u)

{ int i, j;

DType t;

if (l >= u)

return;

t = x[l];

i = l;

j = u+1;

for (;;) {

do i++; while (i <= u && x[i] < t);

do j--; while (x[j] > t);

if (i > j)

break;

swap(i, j);

}

swap(l, j);

qsort3(l, j-1);

qsort3(j+1, u);

}

/* qsort3 + randomization + isort small subarrays + swap inline */

int cutoff = 50;

void qsort4(int l, int u)

{ int i, j;

DType t, temp;

if (u - l < cutoff)

return;

swap(l, randint(l, u));

t = x[l];

i = l;

j = u+1;

for (;;) {

do i++; while (i <= u && x[i] < t);

do j--; while (x[j] > t);

if (i > j)

break;

temp = x[i]; x[i] = x[j]; x[j] = temp;

}

swap(l, j);

qsort4(l, j-1);

qsort4(j+1, u);

}

/* selection */

void select1(int l, int u, int k)

{ int i, j;

DType t, temp;

if (l >= u)

return;

swap(l, randint(l, u));

t = x[l];

i = l;

j = u+1;

for (;;) {

do i++; while (i <= u && x[i] < t);

do j--; while (x[j] > t);

if (i > j)

break;

temp = x[i]; x[i] = x[j]; x[j] = temp;

}

swap(l, j);

if (j < k)

select1(j+1, u, k);

else if (j > k)

select1(l, j-1, k);

}

/* HEAP SORTS */

void siftup(int u)

{ int i, p;

i = u;

for (;;) {

if (i == 1)

break;

p = i / 2;

if (x[p] >= x[i])

break;

swap(p, i);

i = p;

}

}

void siftdown1(int l, int u)

{ int i, c;

i = l;

for (;;) {

c = 2*i;

if (c > u)

break;

if (c+1 <= u && x[c+1] > x[c])

c++;

if (x[i] > x[c])

break;

swap(i, c);

i = c;

}

}

void siftdown1b(int l, int u) /* More C-ish version of 1 */

{ int i, c;

for (i = l; (c = 2*i) <= u; i = c) {

if (c+1 <= u && x[c+1] > x[c])

c++;

if (x[i] > x[c])

break;

swap(i, c);

}

}

void hsort1()

{ int i;

x--;

for (i = 2; i <= n; i++)

siftup(i);

for (i = n; i >= 2; i--) {

swap(1, i);

siftdown1(1, i-1);

}

x++;

}

void hsort2()

{ int i;

x--;

for (i = n/2; i >= 1; i--)

siftdown1(i, n);

for (i = n; i >= 2; i--) {

swap(1, i);

siftdown1(1, i-1);

}

x++;

}

void siftdown3(int l, int u) /* push to bottom, then back up */

{ int i, c, p;

i = l;

for (;;) {

c = 2*i;

if (c > u)

break;

if (c+1 <= u && x[c+1] > x[c])

c++;

swap(i, c);

i = c;

}

for (;;) {

p = i/2;

if (p < l)

break;

if (x[p] > x[i])

break;

swap(p, i);

i = p;

}

}

void hsort3()

{ int i;

x--;

for (i = n/2; i >= 1; i--)

siftdown3(i, n);

for (i = n; i >= 2; i--) {

swap(1, i);

siftdown3(1, i-1);

}

x++;

}

void siftdown4(int l, int u) /* replace swap with assignments */

{ int i, c, p;

DType t;

t = x[l];

i = l;

for (;;) {

c = 2*i;

if (c > u)

break;

if (c+1 <= u && x[c+1] > x[c])

c++;

x[i] = x[c];

i = c;

}

x[i] = t;

for (;;) {

p = i/2;

if (p < l)

break;

if (x[p] > x[i])

break;

swap(p, i);

i = p;

}

}

void hsort4()

{ int i;

x--;

for (i = n/2; i >= 1; i--)

siftdown4(i, n);

for (i = n; i >= 2; i--) {

swap(1, i);

siftdown4(1, i-1);

}

x++;

}

/* Other Sorts -- Exercises in Column 11 */

void selsort() /* Selection sort */

{ int i, j;

for (i = 0; i < n-1; i++)

for (j = i; j < n; j++)

if (x[j] < x[i])

swap(i, j);

}

void shellsort()

{ int i, j, h;

for (h = 1; h < n; h = 3*h + 1)

;

for (;;) {

h /= 3;

if (h < 1) break;

for (i = h; i < n; i++) {

for (j = i; j >= h; j -= h) {

if (x[j-h] < x[j]) break;

swap(j-h, j);

}

}

}

}

/* SCAFFOLDING */

/* Timing */

void timedriver()

{ int i, k, algnum, mod, start, clicks;

while (scanf("%d %d %d", &algnum, &n, &mod) != EOF) {

if (mod <= 0)

mod = 10*n;

for (i = 0; i < n; i++)

x[i] = randint(0, mod-1);

k = n/2;

start = clock();

switch (algnum) {

case 11: qsort(x, n, sizeof(int), (int (__cdecl *)(const void *,const void *)) intcomp); break;

case 12: sort(x, x+n); break;

case 21: isort1(); break;

case 22: isort2(); break;

case 23: isort3(); break;

case 31: qsort1(0, n-1); break;

case 32: qsort2(0, n-1); break;

case 33: qsort3(0, n-1); break;

case 34: qsort4(0, n-1); isort3(); break;

case 41: select1(0, n-1, k); break;

case 51: hsort1(); break;

case 52: hsort2(); break;

case 53: hsort3(); break;

case 54: hsort4(); break;

case 61: selsort(); break;

case 62: shellsort(); break;

}

clicks = clock() - start;

if (algnum == 41) { /* Test selection */

for (i = 0; i < k; i++)

if (x[i] > x[k])

printf(" SELECT BUG i=%d\n", i);

for (i = k+1; i < n; i++)

if (x[i] < x[k])

printf(" SELECT BUG i=%d\n", i);

} else { /* Test sort */

for (i = 0; i < n-1; i++)

if (x[i] > x[i+1])

printf(" SORT BUG i=%d\n", i);

}

printf("%d\t%d\t%d\t%d\t%g\n",

algnum, n, mod, clicks,

1e9*clicks/((float) CLOCKS_PER_SEC*n));

}

}

/* Main */

int main()

{ timedriver();

return 0;

}