Code:
#include <stdio.h>
#include <stdlib.h>
// no -DN=nnn on command line
#ifndef N
#define N 10240
#define NO_DUMP
#endif
// read pentium fast clock with gcc3.2
#define RDTSC(llptr) { \
__asm__ __volatile__ ( \
"rdtsc" \
: "=A" (llptr) \
); }
int qsort_cmp ( const void *a, const void *b ) {
const int *pa = a;
const int *pb = b;
if ( *pa > *pb ) return +1;
if ( *pa < *pb ) return -1;
return 0;
}
// simple bubble sort with no attempt at optimisation
// to act as reference for improvement comparisions
void bubble_reference ( int arr[], int len ) {
int sorted, scan;
for ( sorted = len-1 ; sorted >= 0 ; sorted-- ) {
for ( scan = 0 ; scan < sorted ; scan++ ) {
if ( arr[scan+1] < arr[scan] ) {
int temp = arr[scan+1];
arr[scan+1] = arr[scan];
arr[scan] = temp;
}
}
}
}
// exchange unsorted elements with the end element
// not the adjacent element
// not strictly a bubble sort anymore (I don't think)
void bubble_salem ( int arr[], int len ) {
int sorted, scan;
for ( sorted = len-1 ; sorted >= 0 ; sorted-- ) {
for ( scan = 0 ; scan < sorted ; scan++ ) {
if ( arr[sorted] < arr[scan] ) {
int temp = arr[sorted];
arr[sorted] = arr[scan];
arr[scan] = temp;
}
}
}
}
void bubble_sort_nick (int A[], int n) {
int i, j;
int clean_pass = 0;
for (i = 0; !clean_pass && i < n - 1; ++i) {
clean_pass = 1;
for (j = i + 1; j < n; ++j) {
if (A[i] > A[j]) {
int t = A[i];
A[i] = A[j];
A[j] = t;
clean_pass = 0;
}
}
}
}
int adv_bubble(int array[], int len) {
register int i, tmp, tmp1, test, *pointer;
int counter = len-2;
do {
test = 1;
i = 0;
pointer = array;
do {
// new code ~25% faster
if(*pointer > *(pointer+1)) {
tmp = *pointer;
*pointer = *(pointer+1);
*(pointer+1) = tmp;
test = 0;
}
// old code -> slow
/*if (pointer[i] > pointer[i+1])
{
tmp = pointer[i+1];
pointer[i+1] = pointer[i];
pointer[i] = tmp;
test = 1;
}*/
++pointer;
//i++ and counter = N-2 is faster than ++i and counter = N-1
// I guess I am making something wrong here ... though the array is sorted
//correctly ...
} while(i++ < counter);
if ( test ) return 1;
} while(--counter >= -1);
return 1;
}
int main ( ) {
int array0[N], array1[N],array2[N],array3[N],array4[N],array5[N];
unsigned long long start, end;
unsigned long long t1, t2, t3, t4, t5;
int i;
// prepare 5 identical data sets
for ( i = 0 ; i < N ; i++ ) array0[i] = rand() % N;
memcpy( array1, array0, sizeof(array0) );
memcpy( array2, array0, sizeof(array0) );
memcpy( array3, array0, sizeof(array0) );
memcpy( array4, array0, sizeof(array0) );
memcpy( array5, array0, sizeof(array0) );
RDTSC(start);
qsort( array1, N, sizeof(array1[0]), qsort_cmp );
RDTSC(end); t1 = end-start;
RDTSC(start);
bubble_reference( array2, N );
RDTSC(end); t2 = end-start;
RDTSC(start);
bubble_sort_nick( array3, N );
RDTSC(end); t3 = end-start;
RDTSC(start);
adv_bubble( array4, N );
RDTSC(end); t4 = end-start;
RDTSC(start);
bubble_salem( array5, N );
RDTSC(end); t5 = end-start;
/* check results */
#ifndef NO_DUMP
/* if a value for N was specified on the command line, print everything */
for ( i = 0 ; i < N ; i++ )
printf( "%4d %4d %4d %4d %4d %4d\n",
array0[i], array1[i], array2[i], array3[i], array4[i], array5[i] );
#endif
for ( i = 0 ; i < N ; i++ ) {
if ( array1[i] != array2[i] ) printf( "Array2 diff at %d\n", i );
if ( array1[i] != array3[i] ) printf( "Array3 diff at %d\n", i );
if ( array1[i] != array4[i] ) printf( "Array4 diff at %d\n", i );
if ( array1[i] != array5[i] ) printf( "Array5 diff at %d\n", i );
}
printf( "Qsort time=%lld\n", t1 );
printf( "bubble_reference time=%lld\n", t2 );
printf( "bubble_sort_nick time=%lld\n", t3 );
printf( "adv_bubble time=%lld\n", t4 );
printf( "bubble_salem time=%lld\n", t5 );
return 0;
}
I get these results