Sorting Execution Times

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <malloc.h>

#define     NUMELEMENTS 1000000
#define     NUMDIGITS   5
const int   VERIFY = 0;

inline void swap ( int *left, int *right )
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

// Bubble Sort method which returns time elapsed while sorting
double bubblesort ( int a[ ], int n )
{
    clock_t time1 = clock ( );
    int i, j;
    for ( i = 0; i < n - 1; i++ )
        for ( j = 0; j<n - 1; j++ )
            if ( a[ j ]>a[ j + 1 ] )
                swap ( &a[ j ], &a[ j + 1 ] );
    return (double) ( clock ( ) - time1 ) / CLOCKS_PER_SEC;
}

// Selection Sort method which returns time elapsed while sorting
double selectionsort ( int a[ ], int n )
{
    clock_t time1 = clock ( );
    int i, j, min, pos;
    for ( i = 0; i < n - 1; i++ )
    {
        min = a[ pos = i ];
        for ( j = i + 1; j < n; j++ )
            if ( a[ j ] < min )
                min = a[ pos = j ];
        a[ pos ] = a[ i ];
        a[ i ] = min;
    }
    return (double) ( clock ( ) - time1 ) / CLOCKS_PER_SEC;
}

// Insertion Sort method which returns time elapsed while sorting
double insertionsort ( int a[ ], int n )
{
    clock_t time1 = clock ( );
    int i, j, val;
    for ( i = 0; i<n - 1; i++ )
    {
        val = a[ i + 1 ];
        for ( j = i; j >= 0; j-- )
        {
            if ( a[ j ]>val )
                a[ j + 1 ] = a[ j ];
            else
                break;
        }
        a[ j + 1 ] = val;
    }
    return (double) ( clock ( ) - time1 ) / CLOCKS_PER_SEC;
}

void merge ( int x[ ], int lb, int m, int ub )
{
    int i = lb, j = m + 1, k = lb;
    while ( i <= m && j <= ub )
        if ( x[ i ] < x[ j ] )
            x[ k++ ] = x[ i++ ];
        else
            x[ k++ ] = x[ j++ ];
    while ( i <= m )
        x[ k++ ] = x[ i++ ];
    while ( j <= ub )
        x[ k++ ] = x[ j++ ];
}

void mergesort_worker ( int a[ ], int l, int u )
{
    if ( l < u )
    {
        int mid = ( l + u ) / 2;
        mergesort_worker ( a, l, mid );
        mergesort_worker ( a, mid + 1, u );
        merge ( a, l, mid, u );
    }
}

void quicksort_worker ( int a[ ], int low, int high )
{
    int pivot, j, i;
    if ( low < high )
    {
        pivot = i = low;
        j = high;
        while ( i < j )
        {
            while ( ( a[ i ] <= a[ pivot ] ) && ( i < high ) )
                i++;
            while ( a[ j ] > a[ pivot ] )
                j--;
            if ( i < j )
                swap ( &a[ i ], &a[ j ] );
        }
        swap ( &a[ pivot ], &a[ j ] );
        quicksort_worker ( a, low, j - 1 );
        quicksort_worker ( a, j + 1, high );
    }
}

void print_times ( double times[ ], int n )
{
    int i, mul = 1;
    for ( i = 0; i < n; i++ )
    {
        mul *= 10;
        printf ( "%d\t:\t%.3fs\n",
                 mul,
                 times[ i ] );
    }
}

// Merge Sort method which returns time elapsed while sorting
double mergesort ( int a[ ], int n )
{
    clock_t time1 = clock ( );
    mergesort_worker ( a, 0, n );
    return (double) ( clock ( ) - time1 ) / CLOCKS_PER_SEC;
}

// Quick Sort method which returns time elapsed while sorting
double quicksort ( int a[ ], int n )
{
    clock_t time1 = clock ( );
    quicksort_worker ( a, 0, n );
    return (double) ( clock ( ) - time1 ) / CLOCKS_PER_SEC;
}

// Check if array is sorted
int verify ( int a[ ], int n )
{
    int i;
    for ( i = 0; i != n - 1; i++ )
        if ( a[ i ] > a[ i + 1 ] )
            return 0;
    return 1;
}

int main ( )
{
    int *rand_collection, *a,
        check[ 5 ] = { 0 },                 // To verify that the array is sorted
        i, n = 1;
    double
        bubble_times[ NUMDIGITS ],
        selection_times[ NUMDIGITS ],
        insertion_times[ NUMDIGITS ],
        merge_times[ NUMDIGITS ],
        quick_times[ NUMDIGITS ];
    rand_collection = (int*) malloc ( NUMELEMENTS * sizeof ( int ) );
    a = (int *) malloc ( NUMELEMENTS * sizeof ( int ) );
    srand ( (unsigned) clock ( ) );
    for ( i = 0; i < NUMELEMENTS; i++ )
        rand_collection[ i ] = rand ( ) % 1000;
    for ( i = 0; i < NUMDIGITS; i++ )
    {
        n = n * 10;
        memcpy ( a, rand_collection, n * sizeof ( int ) );
        bubble_times[ i ] = bubblesort ( a, n );
        if ( VERIFY )
            check[ 0 ] |= verify ( a, n );
        memcpy ( a, rand_collection, n * sizeof ( int ) );
        selection_times[ i ] = selectionsort ( a, n );
        if ( VERIFY )
            check[ 1 ] |= verify ( a, n );
        memcpy ( a, rand_collection, n * sizeof ( int ) );
        insertion_times[ i ] = insertionsort ( a, n );
        if ( VERIFY )
            check[ 2 ] |= verify ( a, n );
        memcpy ( a, rand_collection, n * sizeof ( int ) );
        merge_times[ i ] = mergesort ( a, n );
        if ( VERIFY )
            check[ 3 ] |= verify ( a, n );
        memcpy ( a, rand_collection, n * sizeof ( int ) );
        quick_times[ i ] = quicksort ( a, n );
        if ( VERIFY )
            check[ 4 ] |= verify ( a, n );
    }
    printf ( "Execution times for Bubble Sort:\n" );
    print_times ( bubble_times, NUMDIGITS );
    printf ( "Execution times for Selection Sort:\n" );
    print_times ( selection_times, NUMDIGITS );
    printf ( "Execution times for Insertion Sort:\n" );
    print_times ( insertion_times, NUMDIGITS );
    printf ( "Execution times for Merge Sort:\n" );
    print_times ( merge_times, NUMDIGITS );
    printf ( "Execution times for Quick Sort:\n" );
    print_times ( quick_times, NUMDIGITS );
    if ( VERIFY )
        for ( i = 0; i < 5; i++ )
            printf ( "%d\t", check[ i ] );
    getchar ( );
    return 0;
}