2

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

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.