Quad-sort: 4 sorting methods in one C++ file

Question

I am fairly new to C++, and to have a break from all that Java programming, I decided to do something in C++, which is sorting. The four sorting algorithms are:

• Bubble Sort
• Insertion Sort
• Quick Sort
• Merge Sort

Code:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iterator>
#include <chrono>

#define SIZE 100
#define MAX 1000

typedef std::chrono::high_resolution_clock Clock;

void bubbleSort(int toSort[], int length);
void insertionSort(int toSort[], int length);
void quickSort(int toSort[], int length);
void mergeSort(int toSort[], int length);

void printArray(int arr[], int length)
{
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

int main()
{
    srand(time(NULL));
    int arr[SIZE];
    for (int i = 0; i < SIZE; i++) {
        arr[i] = rand() % MAX;
    }
    int arrCopy[SIZE];

    std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
    auto start = Clock::now();
    bubbleSort(arrCopy, SIZE);
    auto end = Clock::now();
    printArray(arrCopy, SIZE);
    std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;

    std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
    start = Clock::now();
    insertionSort(arrCopy, SIZE);
    end = Clock::now();
    printArray(arrCopy, SIZE);
    std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;

    std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
    start = Clock::now();
    quickSort(arrCopy, SIZE);
    end = Clock::now();
    printArray(arrCopy, SIZE);
    std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;

    std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
    start = Clock::now();
    mergeSort(arrCopy, SIZE);
    end = Clock::now();
    printArray(arrCopy, SIZE);
    std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;

    return 0;
}

void swapElements(int toSort[], int i, int j) {
    int temp = toSort[i];
    toSort[i] = toSort[j];
    toSort[j] = temp;
}

void insertionSort(int toSort[], int length)
{
    int temp;
    for (int i = 0; i < length; i++) {
        for (int j = i; j > 0; j--) {
            if (toSort[j] < toSort[j - 1]) {
                temp = toSort[j];
                toSort[j] = toSort[j - 1];
                toSort[j - 1] = temp;
            }
        }
    }
}

void bubbleSort(int toSort[], int length)
{
    int temp;
    for (int i = 0; i < length; i++) {
        for (int j = 1; j < length - i; j++) {
            if (toSort[j] < toSort[j - 1]) {
                temp = toSort[j];
                toSort[j] = toSort[j - 1];
                toSort[j - 1] = temp;
            }
        }
    }
}

int partitionElements(int toSort[], int beginPtr, int endPtr) {
    int pivot = toSort[(rand() % endPtr - beginPtr + 1) + beginPtr];
    beginPtr--;
    while (beginPtr < endPtr) {
        do {
            beginPtr++;
        } while (toSort[beginPtr] < pivot);
        do {
            endPtr--;
        } while (toSort[endPtr] > pivot);
        if (beginPtr < endPtr) {
            // Make sure they haven't crossed yet
            swapElements(toSort, beginPtr, endPtr);
        }
    }
    return beginPtr;
}

void quickSort(int toSort[], int beginPtr, int endPtr)
{
    if (endPtr - beginPtr < 2) {
        return;
    }
    if (endPtr - beginPtr == 2) {
        // Optimization: array length 2
        if (toSort[beginPtr] > toSort[endPtr - 1]) {
            swapElements(toSort, beginPtr, endPtr - 1);
        }
        return;
    }
    int splitIndex = partitionElements(toSort, beginPtr, endPtr);
    quickSort(toSort, beginPtr, splitIndex );
    quickSort(toSort, splitIndex, endPtr);
}

void quickSort(int toSort[], int length)
{
    srand(time(NULL));
    quickSort(toSort, 0, length);
}

void copyArray(int src[], int srcPos, int dest[], int destPos, int toCopyLength)
{
    for (int i = 0; i < toCopyLength; i++) {
        dest[i + destPos] = src[i + srcPos];
    }
}

void mergeParts(int toSort[], int buffer[], int beginPtr, int middle,
        int endPtr) {
    copyArray(toSort, beginPtr, buffer, beginPtr, endPtr - beginPtr);

    int index1 = beginPtr;
    int index2 = middle;
    int resultindex = beginPtr;

    while (index1 < middle && index2 < endPtr) {
        if (buffer[index1] < buffer[index2]) {
            toSort[resultindex++] = buffer[index1++];
        } else {
            toSort[resultindex++] = buffer[index2++];
        }
    }

    if (index1 < middle) {
        copyArray(buffer, index1, toSort, resultindex, middle - index1);
    }
    if (index2 < endPtr) {
        copyArray(buffer, index2, toSort, resultindex, endPtr - index2);
    }
}

void mergeSort(int toSort[], int buffer[], int beginPtr, int endPtr) {
    if (beginPtr + 1 < endPtr) {
        mergeSort(toSort, buffer, beginPtr, (beginPtr + endPtr) / 2);
        mergeSort(toSort, buffer, (beginPtr + endPtr) / 2, endPtr);
        mergeParts(toSort, buffer, beginPtr, (beginPtr + endPtr) / 2, endPtr);
    }
}

void mergeSort(int toSort[], int length)
{
    mergeSort(toSort, new int[length], 0, length);
}

Results:

...
Time taken (nanoseconds): 0
...
Time taken (nanoseconds): 0
...
Time taken (nanoseconds): 0
...
Time taken (nanoseconds): 0

NOTE: The results above do not print the correct time taken. Please ignore that fact, and review my code.

Questions:

1. Any bad practices? I carry everything from Java, and anything that is different (e.g. System.nanoTime() and std::chrono::high_resolution_clock) I get off SO.

2. Algorithm criticism?

3. Anything that can be done more efficiently and/or with less code?

Answer 1

This answer is mostly about design and good practice, and not so much about the algorithms themselves. Therefore, I will mostly use mergeSort in the examples.

For the sake of completeness: a sorting algorithm with an array + size interface is really C-ish. A proper C++ algorithm would take a pair of iterators and would be templated:

template<typename RandomAccessIterator>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last);

Moreover, most of the sorting algorithms in the standard library additionally accept an optional Compare parameter so that you can use something else than operator< to compare two elements. Assuming you have a C++14 compiler, you can use std::less<> as a default:

template<
    typename RandomAccessIterator,
    typename Compare = std::less<>
>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare={});

Now, let's have a look at the functions that you have reimplemented and that you can already find in the standard library (there is some overlap with other answers):

• swapElements actually performs std::swap(toSort[i], toSort[j]);, or std::swap(*it1, *it2); if we consider that it1 and it2 are iterators corresponding to toSort + i and toSort + j. Note that we have templated mergeSort so that it can sort any random-access collection of any type. We would like our program to be able to use user-defined swap function instead of std::swap so that it can take advantage of the potential optimizations. We can use argument-dependent lookup to do the job:

  using std::swap;
  swap(*it1, *it2);
  

  The first line tells the compiler to take std::swap into account for unqualified calls to swap. The second makes an unqualified call to swap: the compiler will check the types of *it1 and *it2 and search for a swap function in their associated namespace. If the lookup finds such a function, it will use it, otherwise it will use std::swap instead. Note that you can also use std::iter_swap which does exactly that:

  std::iter_swap(it1, it2);
  

• partitionElements could probably be replaced by std::partition.

• You can replace copyArray by std::copy, or std::move if you know that you won't read the elements after they have been moved-from. Note that std::sort from the standard library is required to work with move-only types too, so it would be nice if you could ensure that your sorting algorithms work with such types (agreed, it's not trivial for quicksort).

• I am pretty sure that mergeParts could be replaced by std::inplace_merge too.

---

So, taking all of that into account, here is how a modern C++ mergesort could look:

template<typename RandomAccessIterator, typename Compare>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare, std::size_t size) {
    if (size < 2) return;
    auto middle = first + size / 2;
    mergeSort(first, middle, compare, size / 2);
    mergeSort(middle, last, compare, size - size/2);
    std::inplace_merge(first, middle, last, compare);
}

template<
    typename RandomAccessIterator,
    typename Compare = std::less<>
>
void mergeSortImpl(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare={})
{
    std::size_t size = last - first;
    mergeSortImpl(first, last, compare, size);
}

This is better, but still not perfect: the algorithm currently works with random-access iterators, which is ok with std::vector, std::deque or std::array, but it also means that it doesn't work with std::list or std::forward_list which respectively expose bidirectional iterators and forward iterators. std::inplace_merge doesn't work with forward iterators (yet?) but it works fine with bidirectional iterators; here is what we have to change to make our mergeSort work with bidirectional iterators:

• Change iterators subtractions by calls to std::distance.
• Change the iterator-size addition by std::next.
• Change the name of the template parameters so that they do not lie.

Those simple functions from the header <iterator> work with any category of iterator that is at least forward iterator. That also means that if one day std::inplace_merge works with forward iterators, then mergeSort will also work with forward iterators out-of-the-box and allow to sort, for example, singly linked lists. Here is our new enhanced algorithm:

template<typename RandomAccessIterator, typename Compare>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare, std::size_t size) {
    if (size < 2) return;
    auto middle = std::next(first, size / 2);
    mergeSort(first, middle, compare, size / 2);
    mergeSort(middle, last, compare, size - size/2);
    std::inplace_merge(first, middle, last, compare);
}

template<
    typename RandomAccessIterator,
    typename Compare = std::less<>
>
void mergeSortImpl(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare={})
{
    std::size_t size = std::distance(first, last);
    mergeSortImpl(first, last, compare, size);
}

More than an in-depth review of your algorithms, this answer was more about good pratices when writing algorithms. Basically, here is what you should keep in mind:

• Make your algorithms generic when possible.
• Iterators are the way to go (even though ranges will enhance things).
• The standard library can help you.
• Categories of iterators matter.
• Custom comparisons are cool (if you give std::greater<> instead of std::less<> to a sorting algorithm, it will sort the collection in reverse order).

Answer 2

Bug

This line in your quicksort isn't right:

int pivot = toSort[(rand() % endPtr - beginPtr + 1) + beginPtr];

It should be:

int pivot = toSort[rand() % (endPtr - beginPtr) + beginPtr];

Notice that the main problem was the location of the parentheses. Right now, your code can pick a pivot from almost anywhere in the array, including before beginPtr, because the current expression simplifies to rand() % endPtr + 1.

Insertion sort improvements

In your insertion sort, you currently swap your next element down to its correct place. This takes 2n array writes to move your element n spots. Instead of swapping, you could move only the array elements up one spot, and then write the new element into its final location. This takes only n writes.

Another thing is that you don't stop the inner loop once you've found the correct spot. You should break out of the loop the moment you find an element smaller than the current element. Here is a rewrite:

void insertionSort(int toSort[], int length)
{
    for (int i = 1; i < length; i++) {
        int temp = toSort[i];
        int j;
        for (j = i; j > 0; j--) {
            if (temp < toSort[j - 1]) {
                toSort[j] = toSort[j - 1];
            } else {
                break;
            }
        }
        toSort[j] = temp;
    }
}

Answer 3

In merge sort, instead of repeatedly writing (beginPtr + endPtr) / 2 like this:

mergeSort(toSort, buffer, beginPtr, (beginPtr + endPtr) / 2);
mergeSort(toSort, buffer, (beginPtr + endPtr) / 2, endPtr);
mergeParts(toSort, buffer, beginPtr, (beginPtr + endPtr) / 2, endPtr);

It would be better to store in a variable and write it only once:

int midPtr = beginPtr + (endPtr - beginPtr) / 2;
mergeSort(toSort, buffer, beginPtr, midPtr);
mergeSort(toSort, buffer, midPtr, endPtr);
mergeParts(toSort, buffer, beginPtr, midPtr, endPtr);

---

When you call the 4 sorting methods, there's quite a lot of boilerplate code. Since all the sorting methods have the same signature (as they should), you could create a helper function that takes the original array and a sort function as parameter:

void runSort(int arr[], int length, void (*sort)(int[], int))
{
    int arrCopy[SIZE];
    std::copy(arr, arr + length, std::begin(arrCopy));
    auto start = Clock::now();
    sort(arrCopy, SIZE);
    auto end = Clock::now();
    printArray(arrCopy, SIZE);
    std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;
}

Then running the 4 sort functions becomes a lot simpler:

runSort(arr, SIZE, bubbleSort);
runSort(arr, SIZE, insertionSort);
runSort(arr, SIZE, quickSort);
runSort(arr, SIZE, mergeSort);

Answer 4

1. I suggest you allow printing to a different stream with printArray, though std::cout is a good default:

   void printArray(int arr[], int length, std::ostream& out = std::cout)
   

2. If you define your functions before you use them, you don't need any forward-declarations. Repeating yourself is error-prone and tedious.

3. return 0; is implicit for main in C++ and C99+.

4. There's a standard-function std::swap for swapping objects. Though if you really need to swap elements in an array that often, sure a convenience-function is a good idea, though it should be static:

   static void indexed_swap(int arr[], int i, int j) { std::swap(arr[i], arr[j]); }
   

5. In bubbleSort you forgot about your convenience-function and the standard-function, doing it manually instead. But why do you define your temporary all the way outside the loop?

6. Why do you pass around a pointer to the full array, a start- and an end-index in your implementations of quicksort and mergesort?
   It's irrelevant where the slice you are working on in that moment is in relation to the full array, so a pointer to the beginning and a length (or pointer to end) are enough.

   Ah, yes, you said you were contaminated by Java...

   Also, in C++ we have unsigned types.

7. In both quicksort and mergesort, consider sorting small sequences (maybe up to 4 elements, yours to test) with bubble-sort, insertion-sort or such.

8. Consider writing an in-place variant for merging, but at least get rid of the memory leak in mergeSort, you forgot to delete [] your side-buffer.

9. One can easily replace recursive calls to mergesort with iteration.

   Start with small windows (whatever you want to sort with a different method, or 2 if you want it pure, the last in each iteration is potentially partial), and work your way up until a single window encompasses the whole sequence.

10. If you keep needing copyArray, that's easily provided by the standard-library:

    void copyArray(int src[], int srcPos, int dest[], int destPos, int toCopyLength) {
        std::copy_n(src+srcPos, toCopyLength, dest+destPos);
    }
    

Answer 5

Some minor improvements:

In insertionSort() and bubbleSort(), I don't use the already written swap() method. Instead, I do:

    temp = toSort[j];
    toSort[j] = toSort[j - 1];
    toSort[j - 1] = temp;

In bubbleSort(), my code will still iterate over the remaining elements even if the array is already sorted. To break out at a solved array, I should do:

void bubbleSort(int toSort[], int length)
{
    int temp;
    bool sorted = false;
    for (int i = 0; i < length || !sorted; i++) {
        sorted = true;
        for (int j = 1; j < length - i; j++) {
            if (toSort[j] < toSort[j - 1]) {
                sorted = false;
                temp = toSort[j];
                toSort[j] = toSort[j - 1];
                toSort[j - 1] = temp;
            }
        }
    }
}

Answer 6

Just commenting on the bad practices, I think you could remove theacros and use srd::array as you are in c++11. Or if you want to keep the pointer, use a pointer directly instead of [].