Image courtesy of wikipedia user crashmatrix.
So I got curious this morning about a way you could write a recursive bubble sort algorithm. As in, a version of bubble sort that uses absolutely no looping constructs at all. After all, who needs loops anyway? You wanna know how many loops are in the Wizard Book? None!
In any event, recursion is apparently a fairly common strategy for implementing this algo among CS students, but I studied Mechanical Engineering and although I write C++ for a living now (and recursion is the method I prefer from an aesthetic perspective), somehow this particular exercise has escaped me. So I real quick whipped this bad boy up:
template<typename T>
auto recursiveBubbleSort(T arr[], const int size, int pos = 0, bool swapped = false) -> void
{
if(size <= 1) return;
auto left {&arr[pos]};
auto right {&arr[++pos]};
if(*right < *left)
{
auto temp {*right};
*right = *left;
*left = temp;
swapped = true;
}
if(&arr[pos] != &arr[size - 1])
recursiveBubbleSort(arr, size, pos, swapped);
else if(swapped)
recursiveBubbleSort(arr, size);
}It’s a pretty standard bubble sort, but there are exactly ZERO loops. You'll notice that I introduced a flag to signal that two elements had been swapped in the array. If we reach the end of the array and no elements have been swapped, we're done. But if the flag is set high, we go for another trip through the array. I'm also passing the position of the current step in the algorithm. So there's more going on and it's certainly longer than an iterative bubble sort, but I will say that it feels clearer than an iterative bubble sort.
So how does this stack up against an iterative bubble sort? I wrote one so I could compare their execution times:
template<typename T>
auto IterativeBubbleSort(T arr[], const int size) -> void
{
for (auto i {0} ; i < (size - 1); ++i)
for (auto j {0} ; j < (size - 1 - i); ++j)
if (arr[j] > arr[j + 1])
{
auto temp {arr[j]};
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}Yep, that’s a bubble sort alright. And it’s extremely iterative, nested loop and all. Before I move on, I decided to look at how someone else might write a recursive bubble sort algo, just to see if it had some obvious advantage over my own. This and this were the first two links that Google gives you when you look up “recursive bubble sort”, and they both more or less look like this:
template<typename T>
void kindaSortaRecursiveBubbleSort(T arr[], const int size)
{
if (size == 1)
return;
for (int i = 0; i < (size - 1); ++i)
{
if (arr[i] > arr[i + 1])
{
auto temp {arr[i]};
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
kindaSortaRecursiveBubbleSort(arr, size - 1);
}I mean, it’s just kinda sorta recursive. It calls itself but it still uses a loop and is therefore also iterative, and I'm targeting a much stricter criteria here. I decided I’d time it’s execution along with the others to see if it was better or worse that my own, but first I wanted to write a template that would work with iterators.
99% of the time I need a container of some sort (and I’m writing something that isn’t going to live on a microcontroller) I use something from the STL, usually a std::vector. So it makes sense that I'd write something that would do the job on a container I might actually use. Here's what I came up with:
template<typename Iter>
auto bubbleSortWithIterators(const Iter start, const Iter end, Iter pos, bool swapped = false) -> void
{
auto left = pos;
auto right = ++pos;
if(*right < *left)
{
auto temp = *pos;
*right = *left;
*left = temp;
swapped = true;
}
if(pos != (end - 1))
bubbleSortWithIterators(start, end, pos, swapped);
else if(swapped)
bubbleSortWithIterators(start, end, start);
}It's literally the same thing as my recursiveBubbleSort(), but translated into the language of iterators.
At this point I had four versions of bubble sort to test. But to find out how useful my bubble sort is, I decided I should probably benchmark it against std::sort, which is the thing you really should use instead of writing your own. That call just looks like this:
std::sort(my_vector.begin(), my_vector.end());In the end, I tested both bubbleSortWithIterators() and std::sort() with a std::vector<int> and a std::array<int, n>. I timed the execution of each 100,000 times, and these were the results:
Total Execution Time For n = 100000. [ms]
Recursive: 134
Iterative: 32
Kinda Sorta Recursive: 29
Recursive With Iterators (std::vector): 585
Recursive With Iterators (std::array): 105
std::sort(std::vector): 59
std::sort(std::array): 9
Done!
[Finished in 1.9s]Running this same round of tests several times, the results were remarkably consistant. My recursive algo for raw arrays and my recursive algo for std::array were pretty much dead even, and when it comes to speed, both are trash. std::vector takes an eternity to sort with my recursive algo, and in fact std::sort() (the undisputed champ of this test) takes 6 times longer to sort a std::vector than a std::array. This is the price we pay for the convenience granted by std::vectors.
kindaSortaRecursiveBubbleSort() was actually dead even with iterativeBubbleSort() in every trial, which makes sense to me since both are Θ(n^2). Elsewhere in the world of time complexity, std::sort() is Θ(nlog(n)) and my recursive algo is probably something like Θ(2^n).
I think I'll stick to using std::sort(), but this was a fun way to spend a morning anyway.
Cheers!