/*
 * sorts.c
 * File revision 0
 * Contrast several sorting methods.
 * The profiling code is probably Linux specific.
 * (c) 2000 Jacob Lundberg, jacob@chaos2.org
 */


#include <stdio.h>
#include <stdlib.h>
#include <sys/timeb.h>
#include <time.h>


/* Function prototypes. */
int *_insertion_sort(int *items, int n);
int *_quick_sort(int *items, int n);


/* Describe the run. */
#define  N_MIN                  20000
#define  N_MAX                  140000
#define  N_STEP                 20000
#define  REPS                   10


/* Profiling macros, do your magic! */
#define  PROFILE_INIT()         struct timeb beg, end
#define  PROFILE(a, b, c)       ftime(&beg); \
                                (a)((b), (c)); \
                                ftime(&end)
#define  ELAPSED_TIME           1000.0 * difftime(end.time, beg.time) \
                                + end.millitm - beg.millitm


int main(int argc, char **argv) {
/*
 * main()
 * Get some data and stress the sorting algs.
 */

   /* timekeeping structures */
   PROFILE_INIT();

   /* data array */
   int *data = NULL;

   /* counts and counters */
   int i, j, n, l;

   /* Worst case for insertion. */
   for(n = N_MIN / 10; n <= N_MAX / 10; n += N_STEP / 10) {

      /* Ten times around the loop for each value of n (sheesh). */
      for(l = 0; l < REPS; ++l) {

         /* Make sure data space is big enough. */
         data = (int *)realloc(data, n * sizeof(int));

         /* Insertion worse case is reverse order. */
         for(i = 0; i < n; ++i)
            data[i] = n - i;

         /* Sort and profile. */
         PROFILE(_insertion_sort, data, n);
         printf("insertion, worst, n = %i, time = %.0f\n", n, ELAPSED_TIME);

      }

   }
   fflush(stdout);

   /* Worst case for quick. */
   for(n = N_MIN / 10; n <= N_MAX / 10; n += N_STEP / 10) {

      /* Ten times around the loop for each value of n (sheesh). */
      for(l = 0; l < REPS; ++l) {

         /* Make sure data space is big enough. */
         data = (int *)realloc(data, n * sizeof(int));

         /* Quick worse case is forward order. */
         for(i = 0; i < n; ++i)
            data[i] = i;

         PROFILE(_quick_sort, data, n);
         printf("quick, worst, n = %i, time = %.0f\n", n, ELAPSED_TIME);

      }

   }
   fflush(stdout);

   /* Average case for insertion. */
   for(n = N_MIN; n <= N_MAX; n += N_STEP) {

      /* Ten times around the loop for each value of n (sheesh). */
      for(l = 0; l < REPS; ++l) {

         /* Make sure data space is big enough. */
         data = (int *)realloc(data, n * sizeof(int));

         /* Create some random data. */
         for(i = 0; i < n; ++i)
            data[i] = n * rand() / RAND_MAX;

         /* Sort and profile. */
         PROFILE(_insertion_sort, data, n);
         printf("insertion, avg, n = %i, time = %.0f\n", n, ELAPSED_TIME);

      }

   }
   fflush(stdout);

   /* Average case for quick. */
   for(n = N_MIN; n <= N_MAX; n += N_STEP) {

      /* Ten times around the loop for each value of n (sheesh). */
      for(l = 0; l < REPS; ++l) {

         /* Make sure data space is big enough. */
         data = (int *)realloc(data, n * sizeof(int));

         /* Create some random data. */
         for(i = 0; i < n; ++i)
            data[i] = n * rand() / RAND_MAX;

         /* Sort and profile. */
         PROFILE(_quick_sort, data, n);
         printf("quick, avg, n = %i, time = %.0f\n", n, ELAPSED_TIME);

      }

   }
   fflush(stdout);

   /* Best case for insertion. */
   for(n = N_MIN; n <= N_MAX; n += N_STEP) {

      /* Ten times around the loop for each value of n (sheesh). */
      for(l = 0; l < REPS; ++l) {

         /* Make sure data space is big enough. */
         data = (int *)realloc(data, n * sizeof(int));

         /* Best case for insertion is forward order. */
         for(i = 0; i < n; ++i)
            data[i] = i;

         /* Sort and profile. */
         PROFILE(_insertion_sort, data, n);
         printf("insertion, best, n = %i, time = %.0f\n", n, ELAPSED_TIME);

      }

   }
   fflush(stdout);

   /* Best case for quick. */
   for(n = N_MIN; n <= N_MAX; n += N_STEP) {

      /* Ten times around the loop for each value of n (sheesh). */
      for(l = 0; l < REPS; ++l) {

         /* Make sure data space is big enough. */
         data = (int *)realloc(data, n * sizeof(int));

         /* Best case for quick is median-pivot. */
         for(i = 0; i < n / 2; ++i) {
            data[2 * i] = i;
            data[2 * i + 1] = n - i;
         }

         /* Sort and profile. */
         PROFILE(_quick_sort, data, n);
         printf("quick, best, n = %i, time = %.0f\n", n, ELAPSED_TIME);

      }

   }
   fflush(stdout);

   free(data);
   return(0);

}


int *_insertion_sort(int *items, int n) {
/*
 * _insertion_sort()
 * Insertion sort the n elements in the array items.
 */

   /* counters, storage */
   int inner, outer, element;

   /* Loop on the items and insert them. */
   for(outer = 1; outer < n; ++outer) {
      element = items[outer];
      inner = outer - 1;
      while(inner >= 0 && items[inner] > element) {
         items[inner + 1] = items[inner];
         --inner;
      }
      items[inner + 1] = element;
   }

   /* Returning the array can be useful. */
   return(items);

}


int _quick_partition(int *items, int beg, int end) {
/*
 * _quick_partition()
 * Rearrange a quick sort sub-partition.
 */

   /* storage */
   int temp, element = items[beg];

   /* We use beg as the left counter and end as the right. */
   --beg;
   ++end;

   while(1) {
      while(items[--end] > element) /* loop */;
      while(items[++beg] < element) /* loop */;
      if(beg < end) {
         temp = items[beg];
         items[beg] = items[end];
         items[end] = temp;
      } else
         return(end);
   }

}


void _quick_recurse(int *items, int beg, int end) {
/*
 * _quick_recurse()
 * Define quick sort recursion separate from interfacing.
 */

   /* The base case will be a no-op of course. */
   if(beg < end) {
      /* Select a pivot. */
      int pivot = _quick_partition(items, beg, end);
      /* Recurse on the left side, pivot inclusive. */
      _quick_recurse(items, beg, pivot);
      /* Recurse on the right side, pivot exclusive. */
      _quick_recurse(items, ++pivot, end);
   }

}


int *_quick_sort(int *items, int n) {
/*
 * _quick_sort()
 * Quick sort the n elements in the array items.
 */

   /* Sort the array (n is a throw-away variable here). */
   _quick_recurse(items, 0, --n);

   /* Returning the array can be useful. */
   return(items);

}