// taking a comparative look at several sort routines
// typical results: qsort() = 31ms  shellsort = 922ms  insertionsort = 2672ms  bubblesort = 12032ms
// a Windows Console Application tested with Pelles C     vegaseat    04sep2005
 
#include <stdio.h>
#include <stdlib.h>   // qsort(), srand(), rand()
#include <string.h>   // strcmp()
#include <windows.h>  // GetTickCount()  ms since WIN has started
 
#define NUM_ITEMS 50000  // might tax memory capacity
 
int compare(const void *a, const void *b);
void shellSort(int numbers[], int array_size);
void insertionSort(int numbers[], int array_size);
void bubbleSort(int numbers[], int array_size);
 
int main(void)
{
  int k;
  long te, ts;
  int numbers1[NUM_ITEMS], numbers2[NUM_ITEMS], numbers3[NUM_ITEMS], numbers4[NUM_ITEMS];
 
  //seed random number generator
  srand(GetTickCount());
 
  //fill arrays with random integers 0 to 49999
  for (k = 0; k < NUM_ITEMS; k++)
    numbers1[k] = numbers2[k] = numbers3[k] = numbers4[k] = rand() % NUM_ITEMS;
 
  //perform quicksort on array and time it ...
  ts = GetTickCount();
  qsort(numbers1, NUM_ITEMS, sizeof(int *), compare);
  te = GetTickCount();
  printf("Quicksort of %d random integers took %d ms\n", NUM_ITEMS, te - ts);
 
  //perform shellsort on array and time it ...
  ts = GetTickCount();
  shellSort(numbers2, NUM_ITEMS);
  te = GetTickCount();
  printf("Shellsort of %d random integers took %d ms\n", NUM_ITEMS, te - ts);
 
  //perform insertion sort on array and time it ...
  ts = GetTickCount();
  insertionSort(numbers3, NUM_ITEMS);
  te = GetTickCount();
  printf("Insertionsort of %d random integers took %d ms\n", NUM_ITEMS, te - ts);
 
  //perform bubble sort on array and time it ...
  printf("Bubbling away ...\n");
  ts = GetTickCount();
  bubbleSort(numbers4, NUM_ITEMS);
  te =  GetTickCount();
  printf("Bubble sort of %d random integers took %d ms\n", NUM_ITEMS, te - ts);
 
  /*
  // test: show first 100 sorted numbers of each sort
  printf("\n---------------------\n");
  for (k = 0; k < 100; k++)
    printf("%8d  ", numbers1[k]);
  printf("\n---------------------\n");
  for (k = 0; k < 100; k++)
    printf("%8d  ", numbers2[k]);
  printf("\n---------------------\n");
  for (k = 0; k < 100; k++)
    printf("%8d  ", numbers3[k]);
  printf("\n---------------------\n");
  for (k = 0; k < 100; k++)
    printf("%8d  ", numbers4[k]);
  */
 
  getchar();  // wait
  return 0;
}
 
// this odd compare function using generic pointers is required by qsort()
int compare(const void *a, const void *b)
{
  // cast generic pointer to appropriate pointer
  // for strings use  return( strcmp((char *)a,(char *)b) );
  return ( *(int*)a - *(int*)b );
}
 
void shellSort(int numbers[], int array_size)
{
  int i, j, increment, temp;
 
  increment = 3;
  while (increment > 0) {
    for (i=0; i < array_size; i++) {
      j = i;
      temp = numbers[i];
      while ((j >= increment) && (numbers[j-increment] > temp)) {
        numbers[j] = numbers[j - increment];
        j = j - increment;
      }
      numbers[j] = temp;
    }
    if (increment/2 != 0)
      increment = increment/2;
    else if (increment == 1)
      increment = 0;
    else
      increment = 1;
  }  // while
}
 
void insertionSort(int numbers[], int array_size)
{
  int i, j, temp;
 
  for (i = 1; i < array_size; i++) {
    temp = numbers[i];
    j = i;
    while ((j > 0) && (numbers[j-1] > temp)) {
      numbers[j] = numbers[j-1];
      j = j - 1;
    }
    numbers[j] = temp;
  }
}
 
void bubbleSort(int numbers[], int array_size)
{
  int finished = 0, i, j, temp;
 
  for (i = (array_size - 1); i >= 0; i--) {
    if (finished)
      break;
    finished = 1;
    for (j = 1; j <= i; j++) {
      if (numbers[j-1] > numbers[j]) {
        finished = 0;
        // swap
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}