Subscribe to Non Static

## The Real Bubble Sort

Few algorithms can claim the notoriety, and defamation, of the bubble sort. It is often the first sort taught to programming students. It's usually offered as a "don't use this, for educational purposes only" kind of example. So well known that the President of the United States called it "the wrong way to go.”

In simplest terms a bubble sort:
1. iterates through a list a values, swapping adjacent values that are out of order.
2. while swapping occurs, repeat step 1.

Simple code for this might look like:
```do {
swapped = false; // flag to indicate if any swapping occurred
for(i=0; i<size-1; i++) { // loop though all but the last element of the array
// compare the current element to the next element
// this is why the loop stops at the second to last element
if (compare(list, i, i+1)>0) { // if the current element is greater than the next element
swap(list, i, i+1); // transpose current and next values
swapped = true; // set the swapped flag
}
}
} while(swapped); // continue until no swaps occur

```

While not the most concise sort, the elements are easily broken down and explained. Once offered to students as a reasonable way to sort small sets of data, it is now often dismissed altogether. Somewhat unjustly.

The term "bubble sort" was coined in 1962, by K.E. Iverson in "A Programming Language". Prior to Iverson, algorithms for a "transposition" sort exist, but he gave it the name. This name does get applied retroactively at times. Iverson is fond of this sort, preferring it to some other of its class, explaining it in some detail and also enumerating the logical variants.

Knuth, on the other hand, is instrumental in demonizing the humble algorithm, stating "the bubble sort seems to have nothing to recommend it, except a catchy name" ( Donald Knuth. The Art of Computer Programming, Volume 3 [1973] ). Knuth finds that "compared to straight insertion, bubble sorting requires a more complicated program and takes about twice as long!" That's his emphasis. I'd argue that this is somewhat subjective. Knuth gives his examples in his own brand of assembly for the hypothetical MIX computer. But Knuth does get the algorithm correct, which is more than can be said for others.

An influential book (Aho, A. V., Hopcroft, J. E., and Ullman, J. D., The Design and Analysis of Computer Algorithms [1974]) will soon offer this code for a bubble sort (Example 1.9. Fig. 1.13):
```procedure bubble ( var A: array [1..n] of integer );
{ bubble sorts array A into increasing order }
var
i, j, temp: integer;
begin
for i := 1 to n-1 do
for j := n downto i+1 do
if A[j-1] > A[j] then begin
{ swap A[j - 1] and A[j] }
temp := A[j-1];
A[j-1] := A[j];
A[j] := temp
end
end; { bubble }

```

The code appears to be based on one of the qualities of the sort, "The net effect of each pass of the inner loop of statements is to 'bubble' the smallest element toward the front of the array." And as the code goes out of it's way to produce this particular effect, it essentially offers a backwards and somewhat lobotomized selection sort.

And much confusion follows.

You now have two different sorts claiming the same name. One of the qualities of the bubble sort is it's best case O(n) (the swapped flag exit after the first pass), which the above faux version simply doesn't have. That best case claim is pervasive and many papers have been written, looking at the wrong code, asserting it doesn't exist. Which, of course, it doesn't if you're looking at the wrong code.

A quick google of bubble sort will only add to the confusion. One early hit is "Bubble Sort: An Archaeological Algorithmic Analysis" ( http://www.cs.duke.e...ble/bubble.html ), the paper that actually led me to Iverson as the programmer zero. It notes the false bubble sort. It also references the above textbook that offers the wrong code in the first place.

When faced with such conflicting information, we must go to primary sources. Iverson is the primary source here. His "code", the first representation of a "bubble sort", uses a swapped flag. Knuth, while critical, does agree on the algorithm. This is the real bubble sort, the one with the flag.

The bubble sort, while unarguably not the best algorithm, is arguably not the worst, either. It is simple and offers an approachable introduction to sort algorithms. It's quality of stopping when the list is ordered is useful, though other sorts can do the same trick. The quality of moving towards order during each pass, though perhaps not the most efficiently, has value.

For reference, Iverson:

Quote

6.5 Bubble sort.

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. ... In particular, the smallest item is bubbled to the top. Successive stages repeat the process, but since the jth stage brings the jth smallest item to the jth position, the (j + 1 )th stage need not treat the first j positions. I t is clear that v(x) - 1 stages suffice, but it is advantageous to allow termination at the end of the first stage during which no transpositions occur.

Iverson's book doesn't actually give computer source code so much as a flow charted exercise in untypeable symbols that was his idea of what a programming language should be. Strangely, it was actually implemented and called APL (A Programming Language). A small, dedicated, user base still exists. Perhaps they also bubble sort...

Those who get it right:

Quote

Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
-- http://en.wikipedia....iki/Bubble_sort

Quote

Definition: Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.
-- http://xlinux.nist.g...bubblesort.html

Those who don't... I'll leave that as an exercise to the reader. There are many and some are worse and more righteous than others.

### 1 Comments On This Entry

Page 1 of 1

#### RetardedGenius

13 May 2011 - 11:20 AM
Bubble sort seems to be the most widely taught "My First Sorting Algorithm". Although I often wonder why because Selection Sort is no harder to implement, but is faster. Selection Sort also has the advantage of being similar in function to Insertion Sort; which is faster than both of them, but somewhat harder to implement.

Just my two pennies, BTW nice blog mate! ;)
0
Page 1 of 1

S M T W T F S
123456
78910111213
14151617181920
21 22 2324252627
28293031