Sort and search arrays in C / C++ - PART 2

Continuing from Sort and search arrays in C / C++ - part 1, if you haven't already read it, I suggest you do that first.

In this article I will start to look at methods of partitioning arrays to increase the speed of sorting the values ascending. The idea of partitioning is basically to split the sorting of the array into "partitions".

First I will start by creating a new sort procedure and name it array_dacsort; literally meaning divide and conquer sort.

//
// procedure to sort the array using partitioning and recursion
//
void array_dacsort(int a[], int lower, int upper) {
    // if lower index is higher or equal to upper just return
    if (lower >= upper) return;

    // let's start to calculate the pivot of the partition starting with the passed upper index of the array
    int pivot = a[upper];
    // we will use "i" as a track index
    int i = lower - 1;

    // loop through our array from lower to upper indexes
    for (int j = lower; j < upper; j++)
        // if the value of the current index is lower than the array pivot, we should increment the track index and swap the values
        if (a[j] < pivot) std::swap(a[++i], a[j]);

    // swap the last upper value with the current track index + 1
    std::swap(a[i+1], a[upper]);

    // now we will do a recursive call to sort the 2 partitioned parts
    array_dacsort(a, lower, i);
    array_dacsort(a, i+2, upper);
}

The procedure is fairly simple, especially as it is recursively calling itself. Aftering writing this procedure and doing some research on my implementation, it turns out this algorithm is known as quicksort. I used the code from the previous article to test the speed with the exact same conditions as the previous sort procedure and this one came in consecutively as 0.006s - a HUGE difference.

After reading about quicksort and looking at similar implementations, I read more about using an algorithm known as HeapSort which is considered better when using in embedded systems where memory usage may be limited.

After reading a few articles on heap sort and what it actually does, they all seemed to implement a variation of a re-arrangement loop, often called "heapify", so first was to write the code for this:

//
// procedure to re-arrange values obeying heap properties.
//
void array_heapify(int a[], int parent, int len) {
    // upper is our current upper maximum index
    int upper = parent;

    // simple while loop
    while (true) {
        // set the left index like a binary tree, we want the left child which is parent * 2 + 1
        int left = parent * 2 + 1;
        // right is 1 index higher
        int right = left + 1;

        // self explanatory
        if ((left < len) && (a[left] > a[upper])) upper = left;
        if ((right < len) && (a[right] > a[upper])) upper = right;
        if (upper == parent) break;

        std::swap(a[parent], a[upper]);

        parent = upper;
    }
}

To understand this, you need ideally to understand binary trees and read into heap operations. Here we consider the array as a binary tree. The left child in a binary tree is always i*2+1, where i is the index of the parent.

Now we need to start building and sorting the heap. We start from half way down the array and decrement, then call our heapify procedure at the current step index to re-arrange the values.

for (int i = (len / 2 - 1); i >= 0; i--)
        array_heapify(a, i, len);

Next we will actually sort the full re-arranged array using the same heapify procedure, again from upper to lower.

for (int i = len - 1; i >= 0; i--) {
	// swap the root element
	std::swap(a[0], a[i]);
	// re-arrange using our heapify procedure
	array_heapify(a, 0, i);
}

The final implementation of our heap sort with some slight changes looks like this:

//
// procedure to re-arrange values obeying heap properties.
//
inline void array_heapify(int a[], int parent, int len) {
    // upper is our current upper maximum index
    int upper = parent;

    // simple while loop
    while (true) {
        // set the left index like a binary tree, we want the left child which is parent * 2 + 1
        // use bitwise instead of multiplication
        int left = (parent << 1) + 1;
        // right is 1 index higher
        int right = left + 1;

        // self explanatory
        if ((left < len) && (a[left] > a[upper])) upper = left;
        if ((right < len) && (a[right] > a[upper])) upper = right;
        if (upper == parent) break;

        std::swap(a[parent], a[upper]);

        parent = upper;
    }
}


//
// our heapsort procedure that is basically the loops calling our re-arrange
//
void array_heapsort(int a[], int len) {
    // build the heap
    for (int i = (len / 2 - 1); i >= 0; i--)
        array_heapify(a, i, len);

    // sort the heap
    for (int i = len - 1; i >= 0; i--) {
		// swap the root element
        std::swap(a[0], a[i]);
		// re-arrange using our heapify procedure
        array_heapify(a, 0, i);
    }
}

This one took a little longer for me to wrap my head around, but so far it works! Now for speed testing with the same setup as earlier.

This sorted the 50000 random values consecutively 6 times in a row at 0.009s.



That wraps up this article for now. In the next follow-up I plan to move on to the searching algorithms, but I may also swing back to sorting to build some kind of hybridized algorithm and maybe also turn everything into a fully fledged class for re-usability.

Now adding some additional notes for myself - I may also try writing some sorting and searching algorithms for different data types.

Thank you for reading, please drop me any suggestions and recommendations you have or if you've found this article interesting drop me a comment below!

That's all for this entry into the Captain's log for now, keep checking back for more!