Softpanorama
May the source be with you, but remember the KISS principle ;-)

Contents Bulletin Scripting in shell and Perl Network troubleshooting History Humor

Bubblesort

News

Sorting algorithms Recommended Books Recommended Links Shaker sort Insertion sort
Animations Testing Sorting Algorithms Donald Knuth The Art of Computer Programming Humor Etc

This horrible bubblesort algorithm tortured generations of students who take programming classes ;-).

In reality, bubblesort is an extremely simple algorithm the most distinctive feature of which is that this is most often incorrectly implemented sorting algorithms in existence. Looks like few writes of bubblesort even open Knuth.

It is not only incorrectly implemented in popular web pages, it is also  often implemented incorrectly in textbooks and animations :-). Again, bubblesort is probably the champion of incorrect implementations among simple sorting algorithms

Bubblesort is probably the champion of incorrect implementations among simple sorting algorithms  

The idea is to swap adjacent elements, if the elements are out of order, moving up or down the data set. Usually multiple passes are necessary.  Each subsequent pass is shorter as elements after the last swap are already sorted (it is this element that is often missed in "naive" implementations that dominate the web). It terminated as soon as no swaps were performed during the pass.  See animation to get better idea of the details

On any set of data it is less efficient then Insertion sort so it has purely theoretical value as it has some interesting properties. Like insertion sort it is a stable sorting algorithm. 

See Reversed Initial Order - Sorting Algorithm Animations for nice animation

An interesting and often overlooked feature of the algorithm is that the last swap signify the boundary of the already sorted part of the array.  In this sense bubblesort is similar to selection sort as on each pass the maximum or minimum element in the unsorted part is found and subsequent sort can be done on a subset that is smaller then initial by one or more elements (the place of last swap is the boundary). 

Speed with which largest element "sinks" is high -- he occupies its proper place in one pass, but the speed with which small element "floats up" is slow:  only one exchange is done on each path. That's why sometimes largest elements in bubble sort are called "rabbits" and smallest "tortoises".

But it's details of the implementation that are presented are often incorrect. For example Robert Sedgewick's implementation Algorithms in Java, Third Edition, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching is definitely wrong (too primitive to be exact) and does not corresponds to Donald Knuth's version:

static void bubble(ITEM[] a, int l, int r) 
  { for (int i = l; i < r; i++) 
      for (int j = r; j > i; j--) 
        compExch(a, j-1, j); 
  } 

As most implementations of bubblesort presented on the web and some implementations in the textbooks are incorrect it is important to understand two properties of the correct implementation of bubblesort:

  1. If there are no exchanges then the sorting is complete (the simplistic implementation above does not have even this feature; it should generally be avoided).
  2. Each next pass ends at the last swap of the previous pass.  It does not make any sense to continue comparing elements below this point.
Two properties of the correct implementation of bubblesort:
  1. If there are no exchanges, then the sorting is complete .
  2. Each next pass ends at the last swap of the previous pass.

Here is the reimplementation of the algorithm as it was discussed by Knuth: 

void bubbleSort(int a[], int n)
/* Sorts in increasing order the array A of the size N */
{
  int k;
  int bound = n-1;
  int t;
  int last_swap;
 
  while (bound) {
    last_swap = 0;
    for ( k=0; k<bound; k++ )
       t = a[k]; /* t is a maximum of A[0]..A[k] */
       if ( t > a[k+1] ) {
         a[k] = a[k+1]; a[k+1] = t; /*swap*/
         last_swap = k; /* mark the last swap position */
       }//if
    }//for
    bound=last_swap; /*elements after bound are already sorted */       
  }//while
} // bubbleSort

 

There the valuable bound determines when the sorting is finished and it is assigned the position of the last swap. The part of the code that "drags" maximum element to the bottom is sometimes called "bubblemax" and can be coded as subroutines but that does not make much sense.  You can also double this part of algorithm adding "bubblemin" pass on the opposite direction to compensate for the slowness with which minimum elements are "bubbling up" while max element is "sinking" in a single pass. This enhancement to bidirectional bubblesort is known also as shaker sort. But the question is whether this enhancement worth the additional complexity as there are more efficient algorithms of comparable complexity which achieve the same goals (first of all Mergesort).

If you were to watch a graphical representation of the sorting occurring, you would see that each path the smallest element gets "bubbled" up to the top, while the largest element is sinking to the bottom.   

One of the few advantages of Bubblesort is that like insertion sort it is a natural algorithm to be used on lists.  It is also works very well on already sorted lists, or lists with just few permutations. If there is just one permutation the algorithm requires just one pass to sort. 

It is possible to increase the speed of Bubblesort, but only at the cost of increased complexity of the code. One trivial enhancement is to make it symmetrical alternating passes in each direction. This variant is often called cocktail sort (implementations at Wikipedia are incorrect) or shaker short. It works much better is only works much better when some small and large items are swapped in the data set and concentrated on the "wrong end".

The other possibility is shorten the size of the pass based on observation that the element before the first swap can be used for the beginning of next pass: previous elements cannot change their places as they are in partial order. This adds to total number of comparison as check for the first swaps will be performed for each swap.   See C++ Notes Algorithms More Bubble Sorts for the implementation of this idea.


Top updates

Bulletin Latest Past week Past month
Google Search


NEWS CONTENTS

Old News ;-)

bubble-sort

Incorrect implementation, but good animation including random, nearly sorted reverses and few unique data samples. It's visible how inefficient bubblesort is on reversely sorted data array.

Bubble Sort

Several implementation in Perl, Python and C++ using swap subroutine. Does not too correct to me.

Bubble sort misconceptions

Bubble Sort is Never the Answer

Tinsology
It is not too often in the real world that you have to implement your own sort. Generally, whatever language you are using has a library with this functionality built in. If the occasion does arise, however, it is important to understand which algorithms are applicable in which situations. As with most choices, there is no absolute correct answer; there are many trade offs to consider. When choosing an algorithm there are three things you should consider: performance, overhead, and ease of implementation.

You should give equal consideration to each of these factors, disregarding any one of them can lead to poor choices. It is common, for instance, for people to ignore the ease of implementation and focus on the performance of the algorithm. The problem with this is that not every operation is critical. No one is going to die if they songs on their play list do not get sorted quickly enough. Programmer time is more expensive than run time as a professor of mine often said. In addition to this, some high performance algorithms can slower than simpler algorithms due to overhead. If you are sorting 100 items, you can probably insertion sort them just as fast or faster than you can heap sort them. The same would not be true with one million items; heap sort would be faster.

Once we consider all of the factors, you should find that no one algorithm is ideal in every case. There are some algorithms, however, that are not ideal in any case. Unfortunately one of these algorithms is among the most popular: bubble sort. Bubble sort is a very simple algorithm to implement and it has little overhead. The problem lies in its performance. You might think that this conflicts with my earlier point that even simple, low performance algorithms can be faster than others in the right situation. You also might think that bubble sort, being easy to implement, makes up for its performance short comings. This would be true, if it were not the case that there are algorithms that are equally simple to implement, require just as little overhead, and perform better in practice.

Insertion sort is one such algorithm. Like bubble sort it is an in place sort, and is just as easy to implement. Both algorithms have the same time complexity (O notation), but in practice insertion sort performs better in most cases. This being the case you may wonder why bubble sort is even around. Certainly if it is obsolete pages regarding its implementation should be torn out of books and mentioning it should be punishable by a swift slap with a keyboard. Maybe not. When I learned bubble sort it was as an example of how not to sort. In my non-expert opinion, it is equally important to understand how NOT to do things as it is important to understand how TO do them. My point? Learn bubble sort, but never use it.

[Oct 09, 2010] C++ Notes Algorithms More Bubble Sorts

Here are some additional variations on bubble sort.

Bubble Sort -- stop when no exchanges

This version of bubble sort continues making passes over the array as long as there were any exchanges. If the array is already sorted, this sort will stop after only one pass.
 void bubbleSort2(int x[], int n) {
    bool exchanges;
    do {
       exchanges = false;  // assume no exchanges
       for (int i=0; i<n-1; i++) {
          if (x[i] > x[i+1]) {
             int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
             exchanges = true;  // after exchange, must look again
          }
       }
    } while (exchanges);
 }
Disadvantage: This algorithm doesn't shorten the range each time by 1 as it could. See below.

Bubble Sort -- stop when no exchanges, shorter range each time

This version of bubble sort combines ideas from the previous versions. It stops when there are no more exchanges, and it also sorts a smaller range each time.
void bubbleSort3(int x[], int n) {
  bool exchanges;
  do {
    n--;               // make loop smaller each time.
    exchanges = false; // assume this is last pass over array
    for (int i=0; i<n; i++) {
      if (x[i] > x[i+1]) {
        int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
        exchanges = true;  // after an exchange, must look again 
      }
    }
  } while (exchanges);
}
Disadvantage: After the first pass it may not be necessary to examine the entire range of the array -- only from where the lowest exchange occurred to where the highest exchange occurred. The parts above and below must already be sorted. See below.

Bubble Sort -- Sort only necessary range

Here's a version of bubble sort that, on each pass, looks only at the region of array where more exchanges might be necessary.
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
//========================================================= bubbleSortRange
// After a pass in bubble sort, it's only necessary to sort from just 
// below the first exchange (small values may move lower)
// to just before the last exchange (largest values won't move higher). 
// Everything that wasn't exchanged must be in the correct order. 
// After each pass, the upper and lower bounds for the next pass are
// set from the positions of the first and last exchanges on prev pass.

void bubbleSortRange(int x[], int n) {
    int lowerBound = 0;    // First position to compare.
    int upperBound = n;    // First position NOT to compare.
  
    //--- Continue making passes while there is a potential exchange.
    while (lowerBound <= upperBound) {
        int firstExchange = n;  // assume impossibly high index for low end.
        int lastExchange  = -1; // assume impossibly low index for high end.
        
        //--- Make a pass over the appropriate range.
        for (int i=lowerBound; i<upperBound; i++) {
            if (x[i] > x[i+1]) {
                //--- exchange elements
                int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
                //--- Remember first and last exchange indexes.
                if (i<firstExchange) { // true only for first exchange.
                    firstExchange = i;
                }
                lastExchange = i;
            }
        }
        
        //--- Prepare limits for next pass.
        lowerBound = firstExchange-1;
        if (lowerBound < 0) {
            lowerBound = 0;
        }
        upperBound = lastExchange;
    }
}//end bubbleSortRange
The text from the above example can be selected, copied, and pasted into an editor.
Disadvantage: Notice that the largest unsorted element will always be moved all the way to its correct position in the array, but small elements are shifted down by only one place on each pass.

Other bubble sorts

Note that in all these sorts the part that is sorted grows at only one end of the array. The ability to quit early is not symmetrical. The extreme values move all the way to the end in one direction, but only one place in the other direction. The algorithm can be improved by alternately "bubbling" in opposite directions.

[Oct 09, 2010] Simple Sorting in Java Bubble Sort

Java class pornography or how not to program bubblesort ;-)
 InformIT

LISTING 3.1 The bubbleSort.java Program

// bubbleSort.java
// demonstrates bubble sort
// to run this program: C>java BubbleSortApp
////////////////////////////////////////////////////////////////
class ArrayBub
  {
  private long[] a;         // ref to array a
  private int nElems;        // number of data items
//--------------------------------------------------------------
  public ArrayBub(int max)     // constructor
   {
   a = new long[max];         // create the array
   nElems = 0;            // no items yet
   }
//--------------------------------------------------------------
  public void insert(long value)  // put element into array
   {
   a[nElems] = value;       // insert it
   nElems++;           // increment size
   }
//--------------------------------------------------------------
  public void display()       // displays array contents
   {
   for(int j=0; j<nElems; j++)    // for each element,
     System.out.print(a[j] + " "); // display it
   System.out.println("");
   }
//--------------------------------------------------------------
  public void bubbleSort()
   {
   int out, in;

   for(out=nElems-1; out>1; out--)  // outer loop (backward)
     for(in=0; in<out; in++)    // inner loop (forward)
      if( a[in] > a[in+1] )    // out of order?
        swap(in, in+1);     // swap them
   } // end bubbleSort()
//--------------------------------------------------------------
  private void swap(int one, int two)
   {
   long temp = a[one];
   a[one] = a[two];
   a[two] = temp;
   }
//--------------------------------------------------------------
  } // end class ArrayBub
////////////////////////////////////////////////////////////////
class BubbleSortApp
  {
  public static void main(String[] args)
   {
   int maxSize = 100;      // array size
   ArrayBub arr;         // reference to array
   arr = new ArrayBub(maxSize); // create the array

   arr.insert(77);        // insert 10 items
   arr.insert(99);
   arr.insert(44);
   arr.insert(55);
   arr.insert(22);
   arr.insert(88);
   arr.insert(11);
   arr.insert(00);
   arr.insert(66);
   arr.insert(33);

   arr.display();        // display items

   arr.bubbleSort();       // bubble sort them

   arr.display();        // display them again
   } // end main()
  } // end class BubbleSortApp
////////////////////////////////////////////////////////////////

The constructor and the insert() and display() methods of this class are similar to those we've seen before. However, there's a new method: bubbleSort(). When this method is invoked from main(), the contents of the array are rearranged into sorted order.

The main() routine inserts 10 items into the array in random order, displays the array, calls bubbleSort() to sort it, and then displays it again. Here's the output:

77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99

The bubbleSort() method is only four lines long. Here it is, extracted from the listing:

public void bubbleSort()
  {
  int out, in;

  for(out=nElems-1; out>1; out--)  // outer loop (backward)
   for(in=0; in<out; in++)    // inner loop (forward)
     if( a[in] > a[in+1] )    // out of order?
      swap(in, in+1);     // swap them
  } // end bubbleSort()

[Apr 10, 2009] Bubble Sort - C++, Java, Algorithm and Data Structure Tutorials by Denis Kulagin

Contains Java and C++ implementation with "swap check".
Visualizers
  1. Bubble Sort Animation (with source code line by line visualization)
  2. Bubble Sort in Java Applets Centre
  3. Animated Sorting Algorithms: Bubble Sort

Recommended Links

Softpanorama Top Visited

Softpanorama Recommended

Shaker sort
(bidirectional bubblesort)

Bubble sort (double direction)

bidirectional bubble sort

Definition: A variant of bubble sort which compares each adjacent pairs of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning until no swaps are done.

Also known as cocktail shaker sort, shaker sort, double-direction bubble sort.

See also sort.

Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.

Authors: PEB,BB

Bidirectional Bubble Sort Algorithm Demo




Etc

Society

Groupthink : Understanding Micromanagers and Control Freaks : Toxic Managers : BureaucraciesHarvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Two Party System as Polyarchy : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

Skeptical Finance : John Kenneth Galbraith : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes : Oscar Wilde : Talleyrand : Somerset Maugham : War and Peace : Marcus Aurelius : Eric Hoffer : Kurt Vonnegut : Otto Von Bismarck : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Oscar Wilde : Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 26, No.1 (January, 2013) Object-Oriented Cult : Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks: The efficient markets hypothesis : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Vol 23, No.10 (October, 2011) An observation about corporate security departments : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-MonthHow to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Haterís Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

 

The Last but not Least


Copyright © 1996-2014 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Site uses AdSense so you need to be aware of Google privacy policy. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine. This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to make a contribution, supporting hosting of this site with different providers to distribute and speed up access. Currently there are two functional mirrors: softpanorama.info (the fastest) and softpanorama.net.

Disclaimer:

The statements, views and opinions presented on this web page are those of the author and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.

Last modified: February 19, 2014