Comparing Sorting Routines

vegaseat 2 Tallied Votes 249 Views Share

I have joined the thousands who have done it before, and have compared a number of sorting routines. The sorting is done on the same random-integer arrays. No surprises, quicksort wins this simple comparison hands down. There are clever combinations of sorting routines that are faster, like the snippet by Narue shown in:
http://www.daniweb.com/code/snippet61.html
There is also an expert treatise on sorting at:
http://www.eternallyconfuzzled.com/tuts/sorting.html

// 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;
      }
    }
  }
}
bumsfeld 413 Nearly a Posting Virtuoso

I always wondered how qsort was correctly implimented.

vegaseat 1,735 DaniWeb's Hypocrite Team Colleague

If you cannot use "windows.h", you can go with "sys/time.h". Here is an example looking at insertion sort only ...

//
//  main.c
//  insertion_sort
//
// insertionSort101.c
// time the insertion sort of an array of random integers

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

#define NUM_ITEMS 10000

void insertionSort(int numbers[], int array_size);

int numbers[NUM_ITEMS];

// calculate time difference using seconds and microseconds
// return value in milliseconds
float timedifference_msec(struct timeval ts, struct timeval te)
{
    return (te.tv_sec - ts.tv_sec)*1000.0f + (te.tv_usec - ts.tv_usec)/1000.0f;
}

int main()
{
    int k;
    float elapsed;
    struct timeval te, ts;
    clock_t ticks1;

    // seed random number generator
    ticks1 = clock();
    printf("seed = %ld\n", ticks1);
    srand((int)ticks1);

    // fill array with random integers
    for (k = 0; k < NUM_ITEMS; k++)
        numbers[k] = rand();

    gettimeofday(&ts, 0);

    // perform insertion sort on array
    insertionSort(numbers, NUM_ITEMS);

    gettimeofday(&te, 0);
    elapsed = timedifference_msec(ts, te);
    printf("Insertion sort of %d random integers took %f ms\n",
           NUM_ITEMS, elapsed);

    printf("Check first 10 sorted numbers:\n");
    for (k = 0; k < 10; k++)
        printf("%d\n", numbers[k]);

    //getchar();  // console wait
    return 0;
}

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;
    }
}

/* possible result ...
 seed = 2795
 Insertion sort of 10000 random integers took 62.276978 ms
 Check first 10 sorted numbers:
 41043
 63844
 259373
 436615
 497201
 503268
 595312
 682174
 995187
 1410561
*/
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.