On The Optimization of Bubble Sort
Bubble sort is inefficient. Like really really really inefficient. But you see, I didn’t know that when I first started learning C++, so with pen and paper while I sat in Calculus, I wrote bubble sort, a list of ten numbers, and proceeded to sort them by hand.
I like playing games. If I could take that feeling of setting a score for yourself, knowing that it can be beaten, then working towards and eventually beating that score into a capsule, I’d be a drug addict. When it came to sorting my little handwritten lists of numbers, the parallels were immediately apparent. As someone who doesn’t enjoy the act of writing, the first score I cared about was the number of passes the algorithm would have to go through before the list was sorted. Once I started turning my scribbles into code and putting them into XCode, the score I chased was time. It became a game of millisecond golf that’s still continues today. Note that I don’t expect any of what I did to be novel. I’m sure it’s all been done before. This is about me more than it is about bubble sort.
Let’s start by looking at the generic bubble sort. It looks something like this.
The basic idea is it runs through an array, and if the index after the one you’re looking at is less, you swap the two and set sorted to false. If any swaps have happened in the last pass, do the entire thing over again. If not, the list is sorted.
This is what it looks like. Each row represents one pass. Using this algorithm, sorting a list that contains 1 million randomly generated integers takes 2242928.0ms. That’s about 37 and minutes. That’s absurdly long. So what can we do to fix this? Let’s start by looking at where this basic bubble sort fails.
If you follow the numbers through each pass, you’ll notice a few things. The first being that the 10 gets pushed all the way into position right off the bat. This is because bubble sort by nature will push the highest element left out of position during each pass into position. This is a really nice feature. We automatically know that some elements are sorted after each pass, and can therefore ignore those elements.
Doing that brings our time down to 1626360.0ms or 27 minutes and 58 seconds which seems odd. It’s not that much! Why? By neglecting the final elements in the list, we eliminate some of the unnecessary comparisons, but the number of swaps remains the same. Sadly, swapping is where most of the time is spent, so limiting the comparisons doesn’t help us as much as one might hope.
So how do we do that? This is the first solution I came up with when I was sitting in calculus class. What we’re going to do is start from the ends of the array (the first and last elements) and move towards the center making comparisons and swapping as necessary. In the above example, 10 had to be swapped all the way down the list which is expensive computationally. By instead swapping from opposite ends of the list, we manage to move elements that find themselves far from their rightful positions a good distance closer, therefore allowing the sort to be far less computationally expensive!
With that, we bring our time down to 1095600.0ms or 18 minutes and 49 seconds. We’ve cut our original time down by over a third! How great is that? In the words of the late Billy Mays “But wait! There’s more!” I’m going to again remind you, dear reader, that the code you’re about to see was written when I was just getting started with C++. DRY was completely foreign to me. I tell you this so you don’t hurt me when you see this monstrosity:
I’m so, so sorry. Really I am. Hopefully you’ll forgive me if I explain. It didn’t take me long to realize that by further subdividing the array, then preforming swap sorts on each subdivision, we can bring down the total amount of swapping even further, but I was an idiot, so I decided the best way to do it would be manually. That thousand+ line program you’re looking at, is the result of what I thought would be the best way to swap sort the whole array, then in halves, quarters, 8ths, 16ths, 32nds, and 64ths. All that shitty code did pay off though, because a 0ne million element integer array can now be sorted in 25650.0ms. That’s about 26 seconds or ~1/70th of the time of our original bubble sort.
At the point I was at in my education, I wasn’t able to go any further unless I wanted to spend a few hours copy/pasting, so that was it for me then. But of course, here I sit writing this so I must have a reason, right? Right you are! I picked up where I left a few days ago and finished a much shorter V2.0 that night. Here is that V2.0.
What have I done here? For one, I rolled up that massive block from V1.0 so that not only does looking at the thing no longer cause dysentery, it will also continue subdividing until it can’t anymore. Total runtime: 9162.0ms or 1/200th of the original. But I’m still not satisfied so let’s go a little further.
There’re a few months in between the above and what I’m writing now so bear with me for a bit here. I turned my bubble sort into a Cocktail Shaker Sort which is the bidirectional version of the bubble sort. By doing this, I know that one additional element on both ends of the array is in place after each pass. I also adapted the swap sort portion to ignore the in place elements rather than checking them on each pass. With that plus some tweaking, we’re down to ~3150 ms or 1/712th of the original.
After doing all that though, I suspect I may be able to squeeze a little more speed out of this thing if I only bubble sort in one direction and account for that in the swap sort. Let’s look at why.
Notice that by shifting the entire sort over one element every time rather than cutting off the ends, the elements being compared are more likely to be different from the elements compared in the previous pass. By doing this, we’re also able to implement another bubblesort optimization method. Occasionally by chance, more than one value will fall into place. We can detect that by keeping track of the last swapped element, and comparing up the that point.
But I think I’m going to leave off with that cliffhanger. I fear that if I don’t publish this now I’ll keep hacking away at this problem and never publish anything, and what’s the point of coding if no one ever sees your work?
Thus
To be continued…
