Page 1 of 1

The Real Bubble Sort

#1 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,689
  • Joined: 16-October 07

Posted 09 May 2011 - 12:04 PM

*
POPULAR

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.

Is This A Good Question/Topic? 9
  • +

Replies To: The Real Bubble Sort

#2 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 2003
  • View blog
  • Posts: 4,168
  • Joined: 11-December 07

Posted 10 May 2011 - 04:11 AM

A nice and interesting history there. I quite like a version that combines the quick exit when there are no more swaps with the fact that the elements at one end of the list end up in their final positions. Something like this:


	public static void bubble(int[] arr) {
		int end = arr.length - 1;
		do {
			int greatestSwapIndex = -1;
			for(int i = 0, j = 1; i < end; i++, j++) {
				if (arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i]   = arr[j];
					arr[j]   = temp;
					greatestSwapIndex = i;
				}
			}
			end = greatestSwapIndex;
		} while(end > 0);
	}

Was This Post Helpful? 0
  • +
  • -

#3 Renagado  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 117
  • View blog
  • Posts: 388
  • Joined: 14-June 09

Posted 10 May 2011 - 04:59 PM

Interesting, thank you for your effort.
Was This Post Helpful? 0
  • +
  • -

#4 skorned  Icon User is offline

  • New D.I.C Head

Reputation: 13
  • View blog
  • Posts: 41
  • Joined: 30-August 08

Posted 12 May 2011 - 02:56 AM

View Postbaavgai, on 09 May 2011 - 12:04 PM, said:

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.


Wow thanks, this clears up a lot. I actually got in trouble once because I described the original, intuitive algorithm on an exam, and my teacher demanded the modified one. Luckily, wikipedia came to the rescue and I was able to convince him that I had the original bubble sort, and what he wanted was a later optimization, of which there are many, like the one posted by cfoley.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1