/*
 * $Header: /home/gene/library/website/docsrc/shiva-0/RCS/driver0.c,v 395.1 2008/04/20 17:25:51 gene Exp $
 *
 * This is a modified version of the "driver.c" program
 * provided at <http://www.cs.princeton.edu/~rs/shell/>.
 * It compares the performances of various sequences of
 * increments for Shellsort, including three new sequences
 * generated by genetic algorithms (Stover run 7, Stover 
 * run 8, & Bennett et al).
 *
 * Gene Michael Stover
 * Sunday, 8 December 2002
 */

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

#define maxN 1000000

typedef long itemType;

#define randomLong lrand48()

#define less(A, B)  (A < B)
#define exch(A, B) { itemType t = A; A = B; B = t; }

#define IENN 8

void
showItem (itemType x)
{
  printf ("%11ld ", x);
}

void
showArray (itemType a[], int l, int r)
{
  int i;
  for (i = l; i <= r; i++)
    if ((r - l < IENN) || (i - l + 1 < IENN / 2) || (r - i + 1 < IENN / 2))
      showItem (a[i]);
    else if (i == l + IENN / 2 - 1)
      printf ("... ");
  printf ("\n");
}

void
randArray (itemType a[], int N)
{
  int i;
  for (i = 0; i < N; i++)
    a[i] = randomLong;
}

void
copyArray (itemType a[], itemType b[], int N)
{
  int i;
  for (i = 0; i < N; i++) {
    a[i] = b[i];
  }
}

void
shellsortSh (itemType a[], int l, int r)
{
  int i, h;
  for (h = 1; h <= (r - l) / 4; h = 2 * h);
  for (; h > 0; h /= 2)
    for (i = l + h; i <= r; i++) {
      int j = i;
      itemType v = a[i];
      while (j >= l + h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortKn (itemType a[], int l, int r)
{
  int i, h;
  for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
  for (; h > 0; h /= 3)
    for (i = l + h; i <= r; i++) {
      int j = i;
      itemType v = a[i];
      while (j >= l + h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortGo (itemType a[], int l, int r)
{
  int i, h;
  for (h = r - l + 1; h > 0; h = ((h > 1) && (h < 5)) ? 1 : 5 * h / 11)
    for (i = l + h; i <= r; i++) {
      int j = i;
      itemType v = a[i];
      while (j >= l + h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortSe (itemType a[], int l, int r)
{
  int i, j, h, t;
  itemType v;

  for (t = 1; 4 * t * t <= (r - l); t += t);

  for (h = (r - l) / 4; t > 0; t /= 2, h = t * t - (3 * t) / 2 + 1)
    for (i = l + h; i <= r; i++) {
      v = a[i];
      j = i;
      while (j >= h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortPr (itemType a[], int l, int r)
{
  int incs[28] = { 262144, 229376, 200704, 175616, 153664, 134456, 117649,
    32768, 28672, 25088, 21952, 19208, 16807,
    4096, 3584, 3136, 2744, 2401, 512, 448, 392, 343,
    64, 56, 49, 8, 7, 1
  };
  int i, j, k, h;
  itemType v;

  for (k = 0; k < 28; k++)
    for (h = incs[k], i = l + h; i <= r; i++) {
      v = a[i];
      j = i;
      while (j >= h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}


void
shellsortIS (itemType a[], int l, int r)
{
  int incs[16] = { 1391376, 463792, 198768, 86961, 33936, 13776,
    4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1
  };
  int i, j, k, h;
  itemType v;

  for (k = 0; k < 16; k++)
    for (h = incs[k], i = l + h; i <= r; i++) {
      v = a[i];
      j = i;
      while (j >= h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortSto7 (itemType a[], int l, int r)
{
  int incs[16] = { 499871, 494198, 451488, 128823, 35957, 13353,
    5467, 2673, 1097, 340, 171, 58, 24, 9, 4, 1
  };
  int i, j, k, h;
  itemType v;

  for (k = 0; k < 16; k++)
    for (h = incs[k], i = l + h; i <= r; i++) {
      v = a[i];
      j = i;
      while (j >= h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortSto8 (itemType a[], int l, int r)
{
  int incs[16] = { 498201, 461299, 275360, 62025, 18168, 8186, 3716,
    1325, 444, 177, 61, 23, 13, 4, 1
  };
  int i, j, k, h;
  itemType v;

  for (k = 0; k < 16; k++)
    for (h = incs[k], i = l + h; i <= r; i++) {
      v = a[i];
      j = i;
      while (j >= h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
shellsortBe (itemType a[], int l, int r)
{
  int incs[16] = { 91433, 72985, 13229, 5267, 2585, 877, 155, 149, 131,
    23, 8, 1
  };
  int i, j, k, h;
  itemType v;

  for (k = 0; k < 16; k++)
    for (h = incs[k], i = l + h; i <= r; i++) {
      v = a[i];
      j = i;
      while (j >= h && less (v, a[j - h])) {
	a[j] = a[j - h];
	j -= h;
      }
      a[j] = v;
    }
}

void
doit (void (*sortprog) (), itemType a[], int l, int r)
{
  clock_t start, stop;
  int j;
  int i;
  int count;
  itemType *tmp;
  double seconds;

  count = r - l + 1;
  tmp = (itemType *) malloc (count * sizeof *tmp);
  copyArray (tmp, a, count);
  start = clock ();
  for (j = 0; j < 5; ++j) {
    copyArray (a, tmp, count);
    (*sortprog) (a, l, r);
    for (i = l; i < r; i++)
      if (less (a[i + 1], a[i])) {
        printf ("%s:%d: unsorted\n", __FILE__, __LINE__);
        abort ();
      }
  }
  stop = clock ();
  free (tmp);
  seconds = (stop - start) / (double) CLOCKS_PER_SEC;
  printf (" %6.3f", seconds);
  fflush (stdout);
}

int
main (int argc, char *argv[])
{
  itemType *a;
  int N;
  int i;
  struct datum {
    char *column;
    void (*sort) ();
  } ff[] = { 
    { "O", &shellsortSh }, { "K", &shellsortKn }, { "G", &shellsortGo },
    { "S", &shellsortSe }, { "P", &shellsortPr }, { "I", &shellsortIS },
    { "7", &shellsortSto7 }, { "8", &shellsortSto8 }, { "B", &shellsortBe }
  };
  int ff_len = sizeof ff / sizeof ff[0];

  printf ("%6s", "N");
  for (i = 0; i < ff_len; ++i) {
    printf (" %6s", ff[i].column);
  }
  printf ("\n");

  a = malloc (maxN * sizeof *a);
  for (N = 12500; N <= 800000; N *= 2) {
    printf ("%6d", N);
    for (i = 0; i < ff_len; ++i) {
      fflush (stdout);
      randArray (a, N);
      if (i == 0 && N > 200000)
        printf (" %6s", "n/a");
      else {
        doit (ff[i].sort, a, 0, N - 1);
      }
    }
    printf ("\n");
  }
  free (a);
  printf ("\n");
  printf ("           O:  Shell's original\n");
  printf ("           K:  Knuth\n");
  printf ("           G:  Gonnet\n");
  printf ("           S:  Sedgewick\n");
  printf ("           P:  Pratt\n");
  printf ("           I:  Incerpi-Sedgewick\n");
  printf ("           7:  Stover, run 7\n");
  printf ("           8:  Stover, run 8\n");
  printf ("           B:  Bennett et al\n");
  return 0;
}

/* --- end of file --- */