Why to Study Bubble Sort?
I teach senior high students bubble sort every semster. However one day I talking to my friend, it turned out that there's so many versions, so I delve into it to explore the history of bubble sort.
The Bubble Sort We Know
Bubble sort is a very common and easy-to-learn algorithm. Assuming you're going to sort an array of numbers, and you want the order ascending, from the smallest to the largest. Then, you start from the left and compare the adjacent numbers, if the order is incorrect (in this case, the left is greater than the right), exchange them. We call it one stage. We can continue the same process for at most n-1 stages; then, the array would be sorted.
We can write the pseudocode as follows:
Repeat n-1 times:
for index i from first to the last two:
if array[i] > array[i + 1]:
exchange the position of the nubmers.
I know, you may have heard many other version, especially a little refinment of the above. That is in the k-th stage we start from the first one to the n-k one.
So the pseudocode is revised to:
Repeat n-1 times:
for index i from first to the n-k index:
if array[i] > array[i + 1]:
exchange the position of the nubmers.
History of Bubble Sort
However, one of my friends told me that the very original version is "backward" instead of the "upward" version, which we generally learned.
As a result I went to find the history of bubble sort and its original paper. Here's two key papers:
- [1] Sorting on Electronic Commputer Systems. Edward Harry Friend, 1955.
- [2] A Programming Language. Kenneth E. Iverson, 1962.
Friend [1] used "Exchanging" to describe bubble sort. Plus, he stated that the sort start from the beginning, which is "upward".
At the beginning of each pass the first abbreviated item is compared with the second and the smaller assumes first position.
Iverson [2] on the other hand first deliver the word "bubble sort" and stated that the comparsion begins from the buttom of the numbers, and the smaller goes up, which is "backward".
The basic operation of the bubble sort is the comparison and possible transposition of a pair of adjacent items so as to place the smaller of the two keys earlier in the sequence. The first stage consists of such operations performed in sequence on the item pairs (xᵥ₋₁, xᵥ), (xᵥ₋₂, xᵥ₋₁), ⋯, (x₁, x₂) .
bubble sort example from Iverson, 1956
Some facts:
- Considering the efficiency, no difference between upward and backward.
- The original "bubble sort" [2] is backward instead of upward that we commonly know.
- Both papers have the termination condition if the vector is already sorted during the process, terminate the process. It's usually excluded in text book when first introduce the bubble sort.
How to Introduce Bubble Sort Correctly
So, how to introduce bubble sort correctly based on these two papers? Here's the suggestion on my point of view.
First, explain the core concept of bubble sort, that is we sort the vector by comparing adjacent numbers, if the order is not what we want, then we exchange it. This concept is from Friend [1], the exchanging thought.
Secondly, we tell the history about Iverson [2], who first deliver the word "bubble sort". Imagine there are many bubbles under the sea, from the buttom, the lighter goes up and the heavier goes down. It means that we compare the numbers from the last one and eventually the vector becomes ascending. In this moment, if you are not going to write the code or explain how to implement it, I think Iverson's version is better to understand why it's named "bubble sort".
Third, if you want to continue to implementation, you can chose upward or backward. Here I often teach my student in upward way.
Teaching Guide
Here's the example that how I gradually teach my students bubble sort concept.
The first one is a trad-off version for efficiency, which is very easy to understand meanwhile wasting time. (However the CPU runs very fast, so it doesn't matter.)
nums = [1, 2, 9, 8, 3]
n = len(nums)
t = 0
for k in range(n - 1):
for i in range(n - 1):
t += 1
if (nums[i] > nums[i + 1]):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(f'{nums = }, compare {t} times.')
# nums = [1, 2, 3, 8, 9], compare 16 times.
Next I will say that as we can see in the k-th stage, the biggest k-1 numbers are fixed, so we don't need to compare them.
nums = [1, 2, 9, 8, 3]
n = len(nums)
t = 0
for k in range(n - 1):
for i in range(n - k - 1):
t += 1
if (nums[i] > nums[i + 1]):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(f'{nums = }, compare {t} times.')
# nums = [1, 2, 3, 8, 9], compare 10 times.
Finally, in some situation the vector has already sorted, no exchange during a stage, then we can terminate it, which optimize it more.
nums = [1, 2, 9, 8, 3]
n = len(nums)
t = 0
for k in range(n-1):
hasSwapped = False
for i in range(n-k-1):
t += 1
if (nums[i] > nums[i + 1]):
hasSwapped = True
nums[i], nums[i + 1] = nums[i + 1], nums[i]
if not hasSwapped:
break
print(f'{nums = }, compare {t} times.')
# nums = [1, 2, 7, 8, 9], compare 9 times.
Feel free to use these as material when teaching. But for commercial use please contact me.
