Softpanorama (slightly skeptical) Open Source Software Educational Society

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

Bubblesort

This horrible bubblesort algorithm ;-). BubbleSort is an extremely simple algorithm that is often implemented incorrectly is textbooks and animations ;-).  The idea is to swap  adjacent elements, if the elements are out of order.  It terminated as soon as no swaps were performed during the pass.  But 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 of the unsorted part is found.

But it's details of the implementation that are often are incorrect :-). For example Robert Sedgewick's implementation Algorithms in Java, Third Edition, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching is definitly wrong (too primitive to be exact) and does not corresponds to 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); 
  } 

First of all, if there are no exchanges then the sorting is complete (the simplistic implementation above does not have this feature; it should generally be avoided). Here is the reimplementation of the algorithms as it was discusses 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 already sorted */       
  }//while
} // bubbleSort
 

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

One of the primary advantages of BubbleSort it is a natural algorithm to be used on lists.  It is also works very well on already sorted lists, doing just one pass on them. It is a stable sorting algorithm.  

It is possible to increase the speed of BubbleSort, but only at the cost of increased complexity of the code. See the paper by Shad Stafford BubbleSort for some opportunities. The most common of enhancement is bidirectional bubblesort know also as shaker sort. It works in both directions.  Shakersort is also pretty efficient for  "almost sorted" sequences (with small percentage of permutations).  

Notes: Those pages are written by people for whom English is not a native language. Some amount of grammar and spelling errors should be expected. This is a Spartan WHYFF (We Help You For Free) site. It cannot replace the best teachers and the best books. The site contain some obsolete pages as it develops like a living tree... Some links on older pages are broken. Please try to use Google, Open directory, etc. to find a replacement link (see HOWTO search the WEB for details). We would appreciate if you can mail us a correct link. Search Amazon by keywords:     Open directory Research Index

Recommended Links

• Bubble sort - Wikipedia, the free encyclopedia (pseudocode is incorrect)
• CIS71 Some Simple C Programs page by Giorgio Ingargiola
  • www.cis.temple.edu -- c code for bubblesort.
• The Sorting Algorithm Demo (1-0-2) -- this is an old Sun's demo.
• BubbleSort -- paper by Shad Stafford BubbleSort for some opportunities to improve bubblesort
  • BubbleSort- Sample Runs
• Colossians 317 -- animator for an incorrect implementation

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(n²) 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

Last modified: February 28, 2008