Why are universities still teaching bubble sort? There’s always some value in learning things and maybe the bubble sort could be a historical lesson. The problem is that it’s not always presented like that. It’s often presented as a simple sorting algorithm. It’s easy to teach and easy to learn. When you know how to program, the only reason the bubble sort would ever be your only choice is if it was the only thing you know. That’s why it’s so important to take the time to teach better sorting algorithms, even if the other algorithms are a little more complicated. This episode compares the bubble sort algorithm with the quicksort algorithm. You’ll see that quicksort isn’t much more complicated than bubble sort.
A bubble sort will make multiple passes through the numbers and compare two numbers at a time. If it finds any two numbers out of order, it swaps them and moves on. When it can make a full pass through the numbers without making any swaps, then it’s done.
If we start with the numbers 2, 1, 5, 4, 3 and sort them with bubble sort until they are in the order 1, 2, 3, 4, 5, then here’s the steps that bubble sort will go through:
2, 1, 5, 4, 3 – Compare 2 with 1 and swap them.
1, 2, 5, 4, 3 – Compare 2 with 5 and leave them. Compare 5 with 4 and swap them.
1, 2, 4, 5, 3 – Compare 5 with 3 and swap them.
First pass is complete. Begin second pass because there was at least one swap.
1, 2, 4, 3, 5 – Compare 1 with 2 and leave them, then 2 with 4 and leave them, then 4 with 3 and swap them.
1, 2, 3, 4, 5 – Compare 4 with 5 and leave them.
Second pass is complete. Begin third pass because there was at least one swap.
1, 2, 3, 4, 5 – Compare each number again and leave them all in place.
Third pass is complete and the bubble sort is also complete since there was no swap.
Now for the quicksort, this algorithm works by dividing and conquering. Anytime you can divide a problem into smaller problems and solve them separately, you’ll have a much better algorithm than repeatedly doing the same work over and over. Quicksort works by selecting a number called the pivot and then making a pass through the numbers putting anything smaller than the pivot on one side and anything larger than the pivot on the other side. The pivot itself then goes between the two sides. It doesn’t try to sort each side yet. It just places numbers in the correct side. All that’s left to do then is sort each side. These are now smaller and simpler problems and will be solved faster. The algorithm just repeats the same process of selecting a pivot, organizing sides, and then placing the pivot in the middle. Each time a pivot gets placed in the middle, it’s in the correct spot and doesn’t need to be looked at again. Notice how the bubble sort kept comparing numbers such as the 1 and 2 even though they were already in the proper location. Once the quicksort places a pivot, it doesn’t need to compare that pivot anymore.
There are different ways to select a pivot and quicksort does have the potential to be just as slow as bubble sort if the absolute worst choice for a pivot is made each time. In practice, this doesn’t happen. But it could. What’s the worst choice for a pivot? Well, either the largest or smallest number is the worst choice. Why? Because either the largest or smallest number will end up putting all the other numbers on only one side. You lose the benefit of dividing the problem when all you do is move everything except the pivot to one side or the other. For this example, we’ll choose the last item as the pivot each time. Here’s how quicksort handles the first pass through the same numbers:
2, 1, 5, 4, 3 – The last number is 3, that’s the pivot.
Compare 2 with 3. Two then goes into a group that will be on the left. This is a logical group and the 2 doesn’t actually need to move.
Then compare 1 with 3. The 1 also goes in the left which just means that the logical group expands to include the 1. By logical group, all I mean is that the algorithm keeps track of the index separating the left from the right. At this point, we haven’t identified anything that belongs in the right.
Then compare 5 with 3. The 5 becomes the first number that belongs in the right. It doesn’t need to move.
Then compare 4 with 3. The 4 also belongs in the right and doesn’t need to move.
At this point, all the numbers have been compared with the pivot and we just need to place the pivot. Instead of shifting both the 5 and 4 over one position, it’s easier to just swap the 5 and 3. That gives the first actual move so far.
2, 1, 3, 4, 5 – You can see that the 3 is in the correct spot and now the sorting just needs to consider the 2 and 1 and then the 4 and 5.