Timing Sort Functions:

In this project, you will time the sort algorithms you will implement

• insertion sort
• bubble sort
• quick sort
• merge sort
• heap sort

All your sort functions will have the following signature:

template <class T>
void sort_function(T a[], unsigned int size);

The Timer Class:

First, you will need a class to help you time functions:

#include <time.h>
using namespace std;
class timer{
private:
    clock_t _start;
    clock_t _stop;
public:
    timer():_start(clock()), _stop(clock()){}
    void start(){
        _start = clock();
    }
    void stop(){
        _stop = clock();
    }
    float duration(){
        return (float(_stop) - float(_start))/CLOCKS_PER_SEC;
    }
};

Timer class usage:

    timer t;
    t.start();
    f(a, size);
    t.stop();
    return t.duration();

Functions as arguments:

Now, we need to be able to pass functions as arguments to other functions:

float time_sort_routine(int a[], unsigned int  size,
                        void (*f)(int *, unsigned int)){
    timer t;
    t.start();
    f(a, size);
    t.stop();
    return t.duration();
}

Here, we are passing an argument called f. f is a void function that takes an array of ints and an unsigned int argument.

The Call:

You will call f just like you would any regular function:

    f(a, size);

provided that a is an array of ints and size in an unsigned integer.

and the call to this example function looks like this:

double d = time_sort_routine(a, SIZE, quickSort);

The function we used above as an example times one run of the sort function. 

Write a function that will declare an array, then repeats the following code 500 times:

• shuffle the array of a constant size (50,000)
• get the time it took to sort this array,
• keep a running total of the times
• then, after the loop, calculate the average time it took to sort the array of a specific size
• another function will repeatedly call this averaging function to find out how long it will take (on average) to sort 50,000 items shuffled randomly.

The output:

average duration - quickSort(50000): 0.008105
average duration - mergeSort(50000): 0.010183
average duration - heapSort(50000): 0.030169
average duration - heapSort2(50000): 0.014783