/* Collection of code snippets by Arne Vajhøj */
/* (likely posted to comp.os.vms/INFO-VAX, INFO-TPU, MACRO32, eksperten.dk, newz.dk, LinkedIn or other place sometime between 1990 and now) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_SIZE 1000000

void qsint_help(int n1,int n2,int *ia)
{
   int tmp;
   int l=n1;
   int r=n2;
   int pivot=ia[(n1+n2)/2];
   do {
      while(ia[l]<pivot) l++;
      while(ia[r]>pivot) r--;
      if(l<=r) {
         tmp=ia[l];
         ia[l]=ia[r];
         ia[r]=tmp;
         l++;
         r--;
      }
   } while(l<=r);
   if(n1<r) qsint_help(n1,r,ia);
   if(l<n2) qsint_help(l,n2,ia);
   return;
}

void qsint(int n,int *ia) {
   qsint_help(0,n-1,ia);
   return;
}

int compare(const void *e1, const void *e2)
{
    return (*((int *)e1) - *((int *)e2));
}

void csort(int data[], int number)
{
    int i, swapped, gap = number;
  
    do
    {
        swapped = 0;
        gap = gap * 10 / 13;
        if (gap == 0)
            gap = 1;
        else if (gap == 9 || gap == 10)
            gap = 11;
        for (i=0; i<number-gap; i++)
        {
            if (data[i] > data[i+gap])
            {
                int save = data[i];
                data[i] = data[i+gap];
                data[i+gap] = save;
                swapped = 1;
            }
        }
    }
    while (swapped || gap != 1);
}

int main()
{
    int siz,rep,i;
    double t;
    int *master,*work;
    clock_t t1,t2;
    master = (int *)malloc(MAX_SIZE*sizeof(int));
    work = (int *)malloc(MAX_SIZE*sizeof(int));
    srand(time(NULL));
    for(i=0;i<MAX_SIZE;i++) master[i] = rand();
    printf("%8s %9s %9s %9s\n","n","opt QS","std QS","    CS");
    for(siz=10;siz<=MAX_SIZE;siz*=10)
    {
        printf("%8d",siz);
        rep = 10 * MAX_SIZE / siz;
        t = 0;
        for(i=0;i<rep;i++)
        {
            memcpy(work,master,siz*sizeof(int));
            t1 = clock();
            qsint(siz,work);
            t2 = clock();
            t += (t2 - t1);
        }
        printf(" %9.6f",t/rep/CLOCKS_PER_SEC);
        t = 0;
        for(i=0;i<rep;i++)
        {
            memcpy(work,master,siz*sizeof(int));
            t1 = clock();
            qsort(work,siz,sizeof(int),compare);
            t2 = clock();
            t += (t2 - t1);
        }
        printf(" %9.6f",t/rep/CLOCKS_PER_SEC);
        t = 0;
        for(i=0;i<rep;i++)
        {
            memcpy(work,master,siz*sizeof(int));
            t1 = clock();
            csort(work,siz);
            t2 = clock();
            t += (t2 - t1);
        }
        printf(" %9.6f\n",t/rep/CLOCKS_PER_SEC);
    }
    free(master);
    free(work);
    return EXIT_SUCCESS;
}