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

184 Views
``````// 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;
}
}
}
}``````
vegaseat

Scientist

I always wondered how qsort was correctly implimented.

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
*/
``````