What is that sorting algorithm?!

Hits: 129

Yes, for a while I was mystified. I had taught what I was sure was the Bubble Sort, the most basic sorting algorithm given to computer students. It was so simple, I felt little need to look it up (but should have), and just write it from memory. Here was my algorithm, written in pseudocode:

You have an array of numbers A[]
for i <- 1 to N
   for j <- (i+1) to N
      if A[i] > A[j] then
         swap A[i] and A[j]

That’s the Bubble Sort, as I thought it was, and as I have been teaching it for 5 years. The algorithm works, is inefficient as the Bubble Sort has been advertised to be, and I have never questioned it. It was also an easy one to teach and students picked up on it easily.

But from this or that source over the 5 years, I have found others attributing a wholly different algorithm to the Bubble Sort. I dove into my copy of Algorithms 2e (Cormen, Leiserson, RIvest and Stein, 2001), a text which was used in many of the better computer science programs in North America, and this was how they described it:

Let A be an array of data to sort
for i <- 1 to length[A] do
   for j <- length[A] downto (i + 1) do
      if A[j] < A[j - 1] then
         Swap A[j] and A[i]

Yes, this is the source I should have cited rather than going on memory, and that would have been the end of it. But notice that we are only ever comparing two adjacent array elements in a bubble sort. But at the time, I only saw evidence of this cropping up on a YouTube video and some other nameless, faceless websites, and thought maybe there is more than one algorithm called a bubble sort. I tried this several times on paper with several short combinations of numbers, and convinced myself that their algorithm works also.

There are other versions. Harvard CS50 adds some efficiency to the pseudocode. Since the list is often sorted well before both loops have completed, the modification is to have a conditional loop (rather than a counted one) which uses a swap counter, which is used to decide if the list really is sorted. If there are no swaps after one turn of the outermost loop, the list is declared sorted and the algorithm exits. It went something like this:

Let A be an array
Set swap_counter to a nonzero value
Repeat
|   reset swap_counter to 0
|   look at each adjacent pair in A
|   |  if A[n] and A[n-1] are not in order,
|   |     Swap A[n] and A[n-1]
|   |     Add 1 to swap_counter
|   v  end if
v   move to the next adjacent pair
Until swap_counter is 0

You have to play with some short lists on a sheet of paper to convince yourself that this will actually sort a list. It is still a nested loop, but a conditional one.

Then, there was Wikipedia. Their entry on Bubble Sort, apart from being about the proper bubble sort, had a footnote on the bottom, to a paper describing a sorting method called I can’t believe it can sort. Seriously, that was the name given and cited. Here is their algorithm, as elucidated by Dr. Stanley Fung from the University of Leicester (UK) (3 October, 2021) in a paper he entitles “Is this the simplest (and most suprising) sorting algorithm ever?”, publically archived at Cornell Univesity:

Let A be an array of length n
for i <- 1 to n do
   for j <- 1 to n do
      if A[i] < A[j] then
         Swap A[i] and A[j]

This is where I began to question my sanity. This was very close to my version of Bubble Sort, except that I started at and tested . It was similar in that it used a nested for loop, comparison, and swap.

But Fung wrote a paper giving this as a kind of Ripleys’ Believe it or Not. He seemed incredulous that this could work at all. And yes I can see his point. His test of seems backward, yet the numbers end up in increasing order. This is becuase allowing both nested loops going to the array size allows for redundant comparisons and for additional swaps which can take place if , which he explains. Is it efficient? Hell, no. But it is still shares a similar efficiency to Bubble Sort, . Would anyone in their right mind offer this to students as a sorting algorithm? Nope. And yes, he does make these points also. It’s as close as I have seen to a sorting algorithm that appears “brute force”. In addition, he gives a proof of correctness of the algorithm to sort in ascending order.

But now I began to wonder what I was doing. I had been using something like this algorithm for 4 years before Fung wrote his paper. What was my algorithm then? Did I invent something new? Am I going to be famous? That feeling was short-lived as I read on. The next algorithm he offered was the one I taught. It was called an Exchange Sort.

I stand by Exchange Sort as an basic algorithm to teach and for students to grasp in high school, and seems more straightforward than the Bubble Sort. I will probably end up teaching both in due course, and I have already changed my notes and slides, as I haven’t taught it yet this year.

This whole episode illustrates the importance of readily letting go of old ideas once they have been proven wrong, and then learning the right way. Learning takes humility, one of our human virtues we are endowed with. People who feel no need of such reflection and change are people whom I feel are crippled with one of the worst learning disabilities, not the result of biological barriers or mental illness, but instead merely borne of pride and hubris. Life is too short to hang on to old ideas that don’t work and actually never did in the past either.