Simple comparison of sorting algorithms in C++

Question

I know this has been done a million times before, but this is my implementation of bubble-sort, insertion-sort, merge-sort, heap-sort, and quicksort. Any feedback on how to make it better would be most appreciated. Also, I seem to have a large number of functions in the code before main(). Is it preferable to put these in another file, a header file perhaps? How would I do that?

edit: Also, I don't explicitly use pointers, is there a way that I could do so to be more efficient?

#include <iostream>
#include <math.h>
#include <chrono>

//Is this less offensive than using the entire std namespace?
using std::cout;
using std::endl;

//These little functions are used by the heap-sort algorithm
#define PARENT(i) ((i - 1) / 2)
#define LEFT(i)   (2 * i + 1)
#define RIGHT(i)  (2 * i + 2)



//First comes bubble-sort, the most brute-force sorting method.
//Bubble-sort is a simple sorting algorithm that repeatedly steps 
//through the list to be sorted, compares each pair of adjacent items 
//and swaps them if they are in the wrong order

void bubble_sort(int list[], int size)
{
    int temp;
    for(int i=0; i<size; i++)
    {
        for(int j=size-1; j>i; j--)
        {
            if(list[j]<list[j-1])
            {
                temp=list[j-1];
                list[j-1]=list[j];
                list[j]=temp;
            }
        }
    }
}


//Insertion sort is another n^2 algorithm, which works by taking each element
//and inserting it into the proper spot.  Can work quickly on arrays that 
//are either small or nearly sorted already.

void insertion_sort(int list[], int size)
{
    for(int j=1;j<size;j++)
    {
        int key=list[j];
        int i = j-1;
        while(i>-1 and list[i]>key)
        {
            list[i+1]=list[i];
            i=i-1;
        }
        list[i+1]=key;

    }
}

//Merge-sort is much faster than insertion-sort in general, and works by
//dividing the array successively into smaller arrays, sorting them, and then
//merging the results.  merge_sort is written as two functions, `merge` which takes two
//pre-sorted lists and merges them to a single sorted list.  This is called on by merge_sort, 
//which also recursively calls itself.

void merge(int list[], int p, int q, int r)
{
//n1 and n2 are the lengths of the pre-sorted sublists, list[p..q] and list[q+1..r]
int n1=q-p+1;
int n2=r-q;
//copy these pre-sorted lists to L and R
int L[n1+1];
int R[n2+1];
for(int i=0;i<n1; i++)
{
    L[i]=list[p+i];
}
for(int j=0;j<n2; j++)
{
    R[j]=list[q+1+j];
}


//Create a sentinal value for L and R that is larger than the largest
//element of list
int largest;
if(L[n1-1]<R[n2-1]) largest=R[n2-1]; else largest=L[n1-1];
L[n1]=largest+1;
R[n2]=largest+1;

//Merge the L and R lists
int i=0;
int j=0;
for(int k=p; k<=r; k++)
{
    if (L[i]<=R[j])
    {
    list[k]=L[i];
    i++;
    } else
    {
    list[k]=R[j];
    j++;
    }
}
}

void merge_sort_aux(int list[], int p, int r)
{
if(p<r)
{
    int q=floor((p+r)/2);
    merge_sort_aux(list,p,q);
    merge_sort_aux(list,q+1,r);
    merge(list,p,q,r);
}

}

void merge_sort(int list[], int size)
{
    merge_sort_aux(list, 0, size - 1);
}

//Heap-sort is a really interesting algorithm, which first arranges the 
//array into a max-heap, before sorting.  In a max-heap, each element is 
//greater than its 'children', LEFT and RIGHT.

class heap
{
    public:
        int *nodes;
        int length;
        int heap_size;
};

//max_heapify places the element list[index] into the subarray list[index+1...], 
//which is assumed to already be in max-heap form

void max_heapify(heap list, int index)
{

        int left,right,largest,exchange_temp;

        left = LEFT(index);
        right = RIGHT(index);

        if(left <list.heap_size && list.nodes[left] > list.nodes[index])
        {
            largest = left;
        } else
        {
            largest = index;
        }

        if(right <list.heap_size && list.nodes[right] > list.nodes[largest])
        {
            largest = right;
        }


        if(largest != index)
        {
            exchange_temp = list.nodes[index];
            list.nodes[index] = list.nodes[largest];
            list.nodes[largest] = exchange_temp;
            max_heapify(list, largest);
        }

}

//build_max_heap turns an array into max-heap form by repeatedly calling
//max_heapify

void build_max_heap(heap list)
{
    list.heap_size = list.length;
    for(int i = floor(list.length/2); i>=0; i--)
    {
        max_heapify(list, i);
    }
}

//Since one property of a max-heap is that the first element is the largest,
//heap_sort swaps this element with the last element, then re-heapifies the 
//rest, recursively until the whole array is sorted

void heap_sort(int list[], int size)
{
    int exchange_temp;
    heap tempheap;
    tempheap.length = size;
    tempheap.nodes = list;
    tempheap.heap_size = size;
    build_max_heap(tempheap);


    for(int i= tempheap.length - 1; i>=1; i--)
    {
        exchange_temp = tempheap.nodes[0];
        tempheap.nodes[0] = tempheap.nodes[i];
        tempheap.nodes[i] = exchange_temp;
        tempheap.heap_size = tempheap.heap_size - 1;

        max_heapify(tempheap,0);
    }

}

//Quicksort works by dividing the array based upon a 'pivot' element, everything
//to the right of it are greater than or equal to the pivot, everything 
//smaller than the pivot are moved to the left.  Then the left and right
//arrays are sorted in the same way.  Works great on a random array, but
//data that is nearly already sorted are very slow by this method.

int partition(int list[], int p, int r)
{
    int pivot, index, exchange_temp;
    pivot = list[r];
    index = p - 1;
    for(int i = p; i < r; i++)
    {
        if(list[i] <= pivot)
        {
            index++;
            exchange_temp = list[i];
            list[i] = list[index];
            list[index] = exchange_temp;
        }
    }
    exchange_temp = list[r];
    list[r] = list[index+1];
    list[index+1] = exchange_temp;
    return index+1;
}

void quicksort_aux(int list[], int p, int r)
{
    int q;
    if(p<r)
    {
        q = partition(list, p, r);
        quicksort_aux(list, p, q-1);
        quicksort_aux(list, q+1, r);
    }
}

void quick_sort(int list[], int size)
{
    quicksort_aux(list,0, size-1);
}



int main()
{
    //Now what I want to do is compare the timing of the various sorting routines.  

    std::chrono::high_resolution_clock::time_point t1,t2;
    srand(time(0));

    int npointsmax = 100000, nave = 100, npoints = 46;
    double  bubble_timelist[npoints], insertion_timelist[npoints],merge_timelist[npoints], quick_timelist[npoints], heap_timelist[npoints];

    int *rlist1= new int[npointsmax];
    int *rlist2= new int[npointsmax];
    int *rlist3= new int[npointsmax];
    int *rlist4= new int[npointsmax];
    int *rlist5= new int[npointsmax];

    //I will sort random arrays with number of elements taken from the list
    //{1,2,3..10,20,30..100,200.....100000} .  For each array size I average
    //the time over 100 instances.

    double nplist[npoints];
    nplist[0] = 1;
    for(int n=0;n<5;n++)
    {
        for(int j=2;j<11;j++)
        {
            nplist[9*n + j - 1] = j * pow(10,n);
        }
    }

    int icounter = 0;

    cout<<"Number of random points being sorted:\n";

    for (int npointsi : nplist)
{   
        //bbtime, instime, are the time for an individual run for bubble
        //and insertion sort, respectively. this is added to bb_temp_timer
        //over the 100 instances, then the average is found by dividing this
        //number by 100 and adding it to the list bubble_timelist
        double bbtime,instime,hptime,mgtime,qktime;
        double bb_temp_timer = 0.0;
        double ins_temp_timer = 0.0;
        double hp_temp_timer = 0.0;
        double mg_temp_timer = 0.0;
        double qk_temp_timer = 0.0;
        cout<<npointsi<<endl;
        for(int j = 0; j< nave; j++)
        {

            //generate 5 copies of the exact same random array
            for(int ii=0;ii<npointsi;ii++)
            {
                rlist1[ii]=rlist2[ii]=rlist3[ii]=rlist4[ii]=rlist5[ii]=rand() % 1000;
            }

            //The following section of the code seems repetative, how could I simplify it?

            t1 = std::chrono::high_resolution_clock::now();
            merge_sort(rlist1,npointsi);
            t2 = std::chrono::high_resolution_clock::now();
            mgtime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
            mg_temp_timer += mgtime ;

            t1 = std::chrono::high_resolution_clock::now();
            heap_sort(rlist2,npointsi);
            t2 = std::chrono::high_resolution_clock::now();
            hptime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
            hp_temp_timer += hptime ;

            t1 = std::chrono::high_resolution_clock::now();
            quick_sort(rlist3,npointsi);
            t2 = std::chrono::high_resolution_clock::now();
            qktime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
            qk_temp_timer += qktime ;

            //I know that bubble and insertion grow as O(n^2) in the average
            //case, so I won't bother with them once the array grows too large.
            if(npointsi<=500)
            {
                t1 = std::chrono::high_resolution_clock::now();
                bubble_sort(rlist4,npointsi);
                t2 = std::chrono::high_resolution_clock::now();
                bbtime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
                bb_temp_timer += bbtime ;

                t1 = std::chrono::high_resolution_clock::now();
                insertion_sort(rlist5,npointsi);
                t2 = std::chrono::high_resolution_clock::now();
                instime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
                ins_temp_timer += instime   ;
            } else
            {
                bb_temp_timer = 0.0;
                ins_temp_timer = 0.0;
            }

        }


        merge_timelist[icounter] = mg_temp_timer/nave;
        heap_timelist[icounter] = hp_temp_timer/nave;
        quick_timelist[icounter] = qk_temp_timer/nave;
        insertion_timelist[icounter] = ins_temp_timer/nave;
        bubble_timelist[icounter] = bb_temp_timer/nave;
        icounter++;

    }

    //Is there a better way to generate this data table?  A more C++ way?

    FILE * resultsfile;
    resultsfile=fopen("results-comparison_sort-noBS.dat","w");
    for(int j=0;j< npoints;j++) fprintf(resultsfile, "%5e \t %10.2f \t %10.2f \t %10.2f \t %10.2f \t %10.2f \n",nplist[j], bubble_timelist[j], insertion_timelist[j], merge_timelist[j], heap_timelist[j], quick_timelist[j]);
    fclose(resultsfile);


}

Then here are the results

Answer 1

Using

//Is this less offensive than using the entire std namespace?
using std::cout;
using std::endl;

Yes. But still on the lazy size. Is it that hard to type 5 extra characters.

Prefer functions to macros.

//These little functions are used by the heap-sort algorithm
#define PARENT(i) ((i - 1) / 2)
#define LEFT(i)   (2 * i + 1)
#define RIGHT(i)  (2 * i + 2)

If you are going to treat them as functions may as well define them like functions:

//These little functions are used by the heap-sort algorithm
inline int parent(int i) {return ((i - 1) / 2);}
inline int left(int i)   {return (2 * i + 1);}
inline int right(int i)  {return (2 * i + 2);}

Macros stomp all over the namespace/scope rules (and thus are slightly dangerous). They don't work well with any parameters that are complex (because they just use text substitution).

void bubble_sort(int list[], int size)

Sure bubble sort is the most brute force and worst complexity on average. But for a small number of values it is usually the fastest (as it has the lowest overhead). Check out your graphs when the number of values you want to sort is in the range [1-100].

Also bubble sort has a best case of O(n) you forgot to add this standard optimization for quick exit when the data is already sorted.

Ranges in C++

Ranges in C++ are usually done from beginning to one past the end. This convention is so ingrained that when you don't use it you get people noticing and wondering why.

//n1 and n2 are the lengths of the pre-sorted sublists, list[p..q] and list[q+1..r]

Why not have q by one past the end of the first range and r by one past the end of the second range.

Then your list splits nicely as

 list[p..q)
 list[q..r)

It also makes working out sizes easier as

 n1 = q - p;
 n2 = r - q;

If you think this way then you can often take advantage of the standard algorithms (which are organized like this).

Use iterators for your interface.

In C++ the interface between storage and algorithms is done via iterators. This allows you to perform your algorithm on different types of container without changing the code.

void merge(int list[], int p, int q, int r)

So here I would have used:

template<typename I>
void merge(I p, I q, I r)

Merge Not optimal

//Merge the L and R lists
int i=0;
int j=0;
for(int k=p; k<=r; k++)
{
    if (L[i]<=R[j])
    {
    list[k]=L[i];
    i++;
    } else
    {
    list[k]=R[j];
    j++;
    }
}
}

This is not the optimal implementation of the merge algorithm. Once one side has been completely merged you can move the content of the other rather than continuing to test values.

I would have written merge like this:

template<typename I>
void merge(I p, I q, I r)
{
    int leftSize  = std::distance(p, q);
    int rightSize = std::distance(q, r);

    int L[leftSize];   // Technically not legal but most compilers support it.
    int R[rightSize];  // Normally use vectors here. But I am using the same
                       // technique as shown by the OP

    std::move(p, q, L);
    std::move(q, r, R);

    int left  = 0;
    int right = 0;
    I   d     = p;

    while(left < leftSize && right < rightSize)
    {
        (*d) = std::move((L[left] <= R[right])
                    ? L[left++]
                    : R[right++]);
        ++d;
    }
    // Note only one of these copies will actually do anything.
    std::move(L + left,  L + leftSize,  d);
    std::move(R + right, R + rightSize, d);
}

Avoid using dynamic allocation

int *rlist1= new int[npointsmax];
int *rlist2= new int[npointsmax];
int *rlist3= new int[npointsmax];
int *rlist4= new int[npointsmax];
int *rlist5= new int[npointsmax];

1. Prefer to use automatic variables.
2. Prefer standard containers to raw arrays.

Use C++ fstream

FILE * resultsfile;
resultsfile=fopen("results-comparison_sort-noBS.dat","w");
for(int j=0;j< npoints;j++) fprintf(resultsfile, "%5e \t %10.2f \t %10.2f \t %10.2f \t %10.2f \t %10.2f \n",nplist[j], bubble_timelist[j], insertion_timelist[j], merge_timelist[j], heap_timelist[j], quick_timelist[j]);
fclose(resultsfile);

Prefer to use C++ fstream object (it is excepion safe unlike fopen/fclose).

Now admittedly the C++ stream operators are much much much more verbose then the C code for printing. But the main advantage is that they are TYPE SAFE so you have a much less chance of getting it wrong (though modern compilers actually check this in C now).

To mitigate the verbosity you can use boost::format see Which C I/O library should be used in C++ code?

A basic translation into C++

std::ofstream resultsfile("results-comparison_sort-noBS.dat");
for(int j=0;j< npoints;j++) {
    resultsfile << boost::format("%5e \t %10.2f \t %10.2f \t %10.2f \t %10.2f \t %10.2f \n")
                 % nplist[j] 
                 % bubble_timelist[j]
                 % insertion_timelist[j]
                 % merge_timelist[j]
                 % heap_timelist[j]
                 % quick_timelist[j]);
}

But if you had organized your times into a structure:

 struct TimePoints
 {
      int nplist;
      int bubble_timelist
      int insertion_timelist;
      int merge_timelist;
      int heap_timelist;
      int quick_timelist;
      friend std::ostream& operator<<(std::ostream& str, TimePoints const& d)
      {
          return str << boost::format("%5e \t %10.2f \t %10.2f \t %10.2f \t %10.2f \t %10.2f \n")
                 % d.nplist
                 % d.bubble_timelist
                 % d.insertion_timelist
                 % d.merge_timelist
                 % d.heap_timelist
                 % d.quick_timelist;
     }
 }
 // Then stored your times in a vector:
 std::vector<TimePoints>  times;

 // Now you could print easily in a couple of ways

 std::copy(std::begin(times), std::end(times),
           std::ostream_iterator<TimePoints>(std::cout, "\n")
          );
 // or
 for(TimePoints const& tp: times) {
     std::cout << tp << "\n";
 }

Answer 2

Here are some comments that may help you improve your code.

Don't rely on variable length arrays

Lines like these:

int L[n1+1];
int R[n2+1];

are not legal C++11. They were OK for C99, but strictly speaking, you can't rely on using variables to declare the length of arrays like this in C++11.

Use constexpr where practical

In main, the variables npointsmax, npoints and nave are all actually used as constants, so it would make sense to at least declare them as const and preferably constexpr.

Free allocated memory

For every new there should be a corresponding delete; otherwise the program is leaking memory.

Write results to the std::cout

All of the value of the program is in the detailed timing and not really in the number of points. For that reason, send the detailed timing data to std::cout instead of to a hardcoded file. If the user then wants to save a copy, doing so is then a simple matter of command line output redirection.

Emit the data on the fly rather than storing and dumping it

There is not really much need to save the data only to store it all at the end. Instead, why not just emit the data as it's generated? This reduces the overall memory needed and avoids having to manage yet another data structure.

Bail out on timeout rather than hardcoded exit

Rather than having hard-coded special case code for the slowest sorts, instead set a maximum time you're willing to wait for completion and then use that to determine when and if the test runs.

Avoid C-style macros

The macros LEFT and RIGHT are only used once each and the PARENT macro isn't used at all. I'd advise not using macros like those, preferring either inline functions or even lambdas. In this case, I'd probably just put the equation inline and explain it with a comment.

Use <cmath> rather than <math.h>

Use the new style <cmath> rather than the C-style <math.h> for two reasons. First, it is more idiomatic modern C++, but also because it uses namespaces.

Use whitespace to improve readability

Lines like this:

for(int ii=0;ii<npoints;ii++) {

become much easier to read with a little bit of whitespace:

for( int i=0; i < npoints; i++) {

Prefer ++i to i++ in loops

There is not a big difference for most uses, but if you don't need to save the pre-incremented value, make it simple for both the reader and the compiler and say ++i. This also will help when you start using iterators which often only implement the prefix ++ operator.

Populate the unsorted array just once

Rather than using new random values each time, the program can simply generate the largest unsorted array just once and then each iteration would simply copy the appropriate number of elements. This saves time for the overall program without affecting the timing of the sort routines.

Use objects

If you have more than two of something, it should probably be an object. Specifically, each of the sort routines operates over the same size data, uses the same kind of counter, has an associated timer, etc. For that reason, I'd recommend defining an object to encapsulate each test. Here's what I did:

class SortTest
{
public:
    SortTest(void (*fn)(int[], int), std::string fnname, 
        double max_ns=1.5e9)
        : sort_{fn}, 
          name_{fnname},
          slowtime_{max_ns},
          tooslow_{false}
    {}
    // measure one sort and return time in ns
    double timeOne(int rlist[], int npoints) const;
    // measure N sort iterations and return average ns
    double timeN(int N, int rlist[], int npoints);
    // convenience class to return the name
    std::string name() const { return name_; }
    // allow reset of tooslow_ flag
    bool fastenough(bool flag) { tooslow_=!flag; }
private:
    // the sort routine to be used
    void (*sort_)(int list[], int size);
    // the name of the sort routine
    std::string name_;
    double slowtime_;
    bool tooslow_;
};

That's the basic class. Here are the two timing functions:

double SortTest::timeN(int N, int rlist[], int npoints) 
{
    if (tooslow_)
        return 0.0;
    double elapsed{0};
    int *rlistclone = new int[npoints];
    for (int i=N; i; --i) {
        std::copy(rlist, &rlist[npoints], rlistclone); 
        elapsed += timeOne(rlistclone, npoints);
    }
    delete[] rlistclone;
    tooslow_ = elapsed > slowtime_;
    return elapsed/N;
}

double SortTest::timeOne(int rlist[], int npoints) const
{
    auto t1 = std::chrono::high_resolution_clock::now();
    sort_(rlist,npoints);
    auto t2 = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
}

Finally, here is the much simplified main:

int main()
{
    constexpr int npointsmax = 100000, nave = 100, npoints = 46;
    SortTest sorts[]{ 
        { bubble_sort,    "bubble"},
        { insertion_sort, "insertion"},
        { merge_sort,     "merge"},
        { quick_sort,     "quick"},
        { heap_sort,      "heap"}
    };

    // the nplist code remains the same
    srand(time(0));
    double nplist[npoints];
    nplist[0] = 1;
    for(int n=0;n<5;n++) {
        for(int j=2;j<11;j++) {
            nplist[9*n + j - 1] = j * pow(10,n);
        }
    }
    // create the master unsorted list just once
    int rlist0[npointsmax];
    for(int i=0 ; i < npointsmax; i++) {
        rlist0[i] = rand() % 1000;
    }
    for (int npointsi : nplist) {
        cout << std::setw(6) << npointsi;
        for (auto &sort : sorts) {
            cout << '\t' << std::setw(12) << std::setprecision(10) 
                << sort.timeN(nave, rlist0, npointsi);
        }
        cout << '\n';
    }
}

Now that we have a nice data structure, if we wanted to add, say, a radix sort, all that would be required is to add a single obvious line item to the sorts array.

Answer 3

The sort algorithms themselves look excellent. Minor issues include:

• sometimes not using the most succinct notation (use --i; instead of i = i - 1;)
• a few variables declared in too wide a scope (always declare your variables for the smallest possible scope)
• cryptic variable names (variable names should be meaningful except possibly for loop indexes)
• indentation (please use your editor's automatic indent)
• use memcpy() instead of copying lists an item at a time (the compiler may be smart enough to do this for you)
• class heap should probably be struct heap

You mention your suspicion that the repeated code is a code smell. It is. There's a clue earlier: Numeric suffixes on variable names is also a code smell, but it suggests that it should be an array. How about this:

struct sortStatistics
{
    void * sortRoutine(int list[], int size);
    int threshold;
    double timeList[npoints];
    int * rlist;
    double temp_timer;
};

Then initialize it like so:

sortStatistics algorithmArray[] =
{
     { merge_sort, 100000 }
    ,{ heap_sort, 100000 }
    ,{ quick_sort, 100000 }
    ,{ bubble_sort, 500 }
    ,{ insertion_sort, 500 }
} 

int numAlgorithms = sizeof(algorithmArray)/sizeof(sortStatistics);

So that way, your main loop is fully scalable:

    // initialize rlist for each algorithm
    for (int alg=0; alg<numAlgorithms; alg++)
    {
        algorithmArray[alg].rlist = new int[nPointsMax];
    }
    for(int j = 0; j< nave; j++)
    {
        //generate random array
        for(int ii=0;ii<npointsi;ii++)
        {
            algorithmArray[0].rlist[ii]=rand() % 1000;
        }

        //copy random array to each sort routine
        for (int alg=1; alg < numAlgorithms; alg++)
        {
            memcpy(algorithmArray[alg].rlist,algorithmArray[0].rlist;npoints*sizeof(int));
        }

        // perform tests on each algorithm
        for (sortStatistics sa : algorithmArray)
        {
           if (npointsi <= sa.threshold)
           {
               t1 = std::chrono::high_resolution_clock::now();
               sa.sortRoutine(sa.rlist,npointsi);
               t2 = std::chrono::high_resolution_clock::now();
               time = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
               sa.temp_timer += time;
           }
        }

        for (sortStatistics sa : algorithmArray)
        {
            sa.timelist[j] = temp_timer / nave;
            sa.temp_timer = 0;
        }
    }

I bet you can figure out how to write out the file.

Answer 4

Without having looked in-depth in your code I would say to use std::vector instead of new/delete (in fact you forgot to call delete) and to use std::uniform_int_distribution instead of rand() % n. The latter can introduce bias however it is not very important in this example.

Also to answer your pointer question I always implement merge sort bottom-up. You can allocate your \$\mathcal{O}(n)\$ extra space once and only once and then by swapping pointers you can avoid copying the sorted array back to itself except potentially at the end.