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
Comparing Sorting Routines
// 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.