[Back to basics] Bubble sort

In the first post, we’ve taken a look at the binary search. Let’s continue with some simple sorting algorithms. I will start with my favourite one — bubble sort.

The algorithm

The algorithm goes through the array and compares each element with the next one. If the latter is smaller, it swaps them.

If you go from the beginning to the end, the biggest element will move to the end like a bubble upwards in the water. This means, in order to put all N elements at their places we need to go through all elements of the array N times.

Performance

To “bubble up” one element we need to go from the beginning to the end, which is N iterations. However, we still need to sort other N-1 elements, so we need to do N iterations N times which is N². There’re some ways to optimize it tho, but in terms of O-notation, the algorithm’s complexity is O(N²).

Ruby

The simplest implementation

Exactly like described: N times going through the array and bubble up the biggest elements.

Classic implementation

Notice that after each walk-through the biggest element raises to its place. This means, that we don’t have to compare with it further — it’s going to be the biggest one.

Imagine, we have an array 100…1. After 90 walk-throughs we would still go through all 100 elements even tho 90 of them are already sorted and not going to change their positions.

That said, we can optimize this bit, which is, for me, is the classic implementation:

The only thing changed is the last index in the inner loop. Instead of going through the whole array it goes only through not bubbled elements yet.

How good is this optimisation? Let’s count. The original has N² iterations, the optimized version is N + (N -1) + (N — 2) … = N * (N-1) / 2
The difference is
N²-N²/2 + N/2 = N²/2 + N/2

For 1000 elements this is 500500 iterations. Not too shabby.

Haskell

Let’s start with making a function for “bubbling up” elements in a list.

I love how declarative this solution seems:

• An empty list has nothing to bubble up
• List of one element is the same, the only element is in its place
• For lists of two or greater elements, we take the smallest of the first two and concatenate it with the rest bubbled.

Let’s use it now

Solution #1

All we need to do is to just use bubbling N times.

For applying bubble_greatest N times I created a sequence 1..N and reduced it (we don’t care about the numbers themselves, we just need the function to be applied N times).

As in the simplest Ruby implementation, there’s still room for improvement. But I decided to leave it undone.

Solution #2

We just need the function to be applied N times

That got me thinking. Can we just compose the function with itself N times and then apply it to a list once?

The solution I came up with uses iterate, which creates an infinite sequence by applying a function to its tail.

bubbling is a sequence of bubble_greatest(x), bubble_greatest(bubble_greatest(x)), ...

All we need to do is to get N-th element which will be the function composed with itself N times. The !! operator does exactly this — it takes an n-th element from a list by its index (starting from zero).

It still lacks the optimization but I thought it was an interesting idea.

Pascal

My first programming language was Pascal and the bubble sort was the first sorting algorithm I learned. Time to press some keys to pay respects.

Funnily enough, it was an actual struggle to write Pascal code again.

1. I had to introduce IntArray because the compiler (fpc) refused to accept Array of Integer as a function type.
2. Interesting enough, IntArray is not an alias of Array of Integer. Procedures (functions without a return value) receive copies of Array of Integer but originals (pointers?) of IntArray. This means that changing array of integer in a procedure would have zero effect, however, changing IntArray is mutating operation. I didn’t dive into this further.
3. Different Pascal compilers have slightly different syntax. Usually, you will not see thereturn operator (cool, eh?), instead, you need to assign the result to a special variable. Usually, it’s Result but in this case, the special variable has the same name as the function.
4. Pascal doesn’t have array literals. We don’t care about them in this particular snippet but it was quite annoying.

Shaker sort

The fastest variation of the bubble sort I know of is the shaker sort.

It eliminates two weaknesses of the original bubble sort:

1. A sorted array will still go through the whole process. Bubble sort doesn’t acknowledge the possibility of an array being sorted or partially sorted. Shaker sort narrows sorting area depending on how many elements at the head of an array are already sorted.
2. The smallest element in the end. Imagine, we have an array [1, 2, 3, …, 10, 0]. The first 10 elements are already sorted, all we need to do is just shift them rightward and put zero at the beginning. Original bubble sort will move zero leftward by 1 with each walk-through. What if we could move it right away? Shaker sort does that, it doesn’t walk an array only from left to right, it also walks it from right to left.

Let’s take a look at Ruby code:

This is far more complicated, isn’t it?:)

Let’s highlight the main points:

• We work an array from both left and right. That’s why we have two loops inside the outer until loop.
• Each loop walks an array from its own starting point (left and right)
• Both starting points are being moved if the elements around a starting point are already sorted.
• If starting points collide, it means that the array is sorted and there’s no point in going forward.

Selection sort

There’s another sorting algorithm I personally consider relative to the bubble sort. It’s called “selection sort”. The idea is similar: walk through the array N times and put the biggest (or the smallest) element to its place. Let’s see the code first:

The difference is that bubble sort swaps adjacent elements whereas selection just looks for the smallest/biggest one and swaps it with one occupying its rightful place. If my memory serves me right, my teacher called this algorithm somewhat like “direct exchange sort”.

It’s kind of interesting to think how bubble sort differs from selection sort. In my opinion, selection sort is a bit faster (fewer assignment operations). However, one cool thing about bubble sort is that elements that are ordered relative to each other will never become unordered.

Consider array [2, 3, 4, 1] . After first iteration it becomes:

• Bubble sort: [2, 3, 1, 4]
• Selection sort: [1, 3, 4, 2]

The way I see it, bubble sort improves the order of an array with every iteration; the current order preserved but some bigger elements got closer to the end. Selection sort may not do so; here it literally put the smallest element to its place but also put the second smallest element to the position of the biggest one.

With every mutation, the bubble sort improves the order of an array. Maybe there’s a way to use it as a partial sorting?

Conclusion

Bubble sort is one of two of my favourite sorting algorithms. Technically, it doesn’t carry any value for us, because:

• Sorting algorithms are already implemented everywhere and are flexible.
• Bubble sort has the complexity of O(N²) which is not good for big arrays of data. Simply put, it’s inefficient. Shaker sort, even tho greatly optimises it, still doesn’t scale very well and still does have the O(N²) complexity.

However, I think it has it’s advantages:

• Simplicity. It’s simple to implement and simple to understand. Great for those who make their first steps in algorithms and computer science.
• Can be further optimized. One can gradually optimize it and evolve from the simplest version towards something like shaker sort. It’s also great for teaching and learning algorithm complexity.
• It’s just cool and pretty. Take a look at what it looks like in practice: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html