bubblesort.c

void
bubblesort(int A[], unsigned int n)
{
  int i, j;

  for(i = 0; i < n; i++) {
    for(j = i; j < n; j++) {
      if(A[i] > A[j]) {
        int  t = A[j];
          A[j] = A[i];
          A[i] =    t;
      }
    }
  }
}



#ifdef DEBUG
#include <stdio.h>

int
main(int argc, char **argv) {
  int i, n;
  int A[] = {1,3,4,2,5};

  n = sizeof(A)/sizeof(A[0]);

  bubblesort(A, n);

  for(i = 0; i < n; i++) {
    printf("%d\n", A[i]);
  }

  return 0;
}
#endif

quicksort.c

void
quicksort(int A[], unsigned int i, unsigned int j)
{
    unsigned int k, z;
    int pivotValue, t;

    if(j <= i || 1 > j - i) return;

    pivotValue = A[j];

    for(z = i, k = i; k < j; k++) {
        if(A[k] <= pivotValue) {
               t = A[k];
            A[k] = A[z];
            A[z] =    t;

            z++;
        }
    }

       t = A[z];
    A[z] = A[j];
    A[j] = t;


    if(z > i) {
        quicksort(A, i, z - 1);
    }

    quicksort(A, z + 1, j);
}



#ifdef DEBUG
#include <stdio.h>

int main (void) {
    int i, n;
    int A[] = { 5, 7, 1, 3, 4, 1, 3, 1, 2, 4, 7, 12 };

    n = sizeof(A)/sizeof(A[0]);

    for(i = 0; i < n; i++) {
        printf("%d\n", A[i]); 
    }

    quicksort(A, 0, n - 1);

    for(i = 0; i < n; i++) {
        printf("%d\n", A[i]); 
    }

    return 0;
}
#endif

random.c

/* 
 * KISS random number generator from:
 * <http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf>
 */

/* Seed variables */ 
static unsigned int x = 123456789, y = 362436000, z = 521288629, c = 7654321;

unsigned int
rng() 
{ 
    unsigned long long t, a = 698769069ULL; 
    
    x = 69069*x+12345; 
    y ^= (y<<13); y ^= (y>>17); y ^= (y<<5); /* y must never be set to zero! */ 
    t = a*z+c; c = (t>>32); /* Also avoid setting z=c=0! */ 
       
    return x+y+(z=t); 
} 

void
rng_seed(unsigned int sx, unsigned int sy, unsigned int sz)
{
  x = sx;
  y = sy;
  z = sz;
}

results

dualbus@debian ~/local/src/dualbus-data_structures/sorts
 % gcc -O3 -o timethem timethem.c   bubblesort.c quicksort.c random.c
dualbus@debian ~/local/src/dualbus-data_structures/sorts
 % ./timethem 
bubblesort| [YES] 1579.4294800683 (sec)
quicksort | [YES] 0.93907 (sec)

timethem.c

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

#define ITEMS 1000000



void bubblesort   (int A[], unsigned int n);
void quicksort    (int A[], unsigned int i, unsigned int j);
void insertionsort(int A[], unsigned int n);

int  verify     (int A[], unsigned int n);

unsigned int rng();
void rng_seed(unsigned int, unsigned int, unsigned int);



int main() {
  int *A, *B;
  unsigned int i;
  struct timeval r_tv, tv_Ax, tv_Ay, tv_Bx, tv_By;
  
  A = (int *)malloc(sizeof(int) * ITEMS);
  B = (int *)malloc(sizeof(int) * ITEMS);

  if(B == NULL || A == NULL) return 1;


  gettimeofday(&r_tv, NULL);
  rng_seed(r_tv.tv_sec ^ r_tv.tv_usec, getpid(), 12345);


  for(i = 0; i < ITEMS; i++) {
    int random = (int)rng();

    A[i] = random;
    B[i] = random;
  }

  gettimeofday(&tv_Ax, NULL);
  bubblesort(A, ITEMS);
  gettimeofday(&tv_Ay, NULL);

  gettimeofday(&tv_Bx, NULL);
  quicksort (B, 0, ITEMS - 1);
  gettimeofday(&tv_By, NULL);


  printf("bubblesort| [%s] %u.%u (sec)\n",
      verify(A, ITEMS) ? "YES" : "NO ",
      tv_Ay.tv_sec - tv_Ax.tv_sec,
      tv_Ay.tv_usec - tv_Ax.tv_usec
      );

  printf("quicksort | [%s] %u.%u (sec)\n",
      verify(B, ITEMS) ? "YES" : "NO ",
      tv_By.tv_sec - tv_Bx.tv_sec,
      tv_By.tv_usec - tv_Bx.tv_usec
      );

  return 0;
}


int
verify(int A[], unsigned int n)
{
  unsigned int i, m;

  for(i = 0, m = n - 1; i < m; i++) {
    if(A[i] > A[i+1]) {
      return 0;
    }
  }

  return 1;
}