Softpanorama (slightly skeptical) Open Source Software Educational Society

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

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 definitely 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 each path the smallest element gets "bubbled" up to the top, while the largest element is sinking to the bottom.   

One of the primary advantages of BubbleSort is that it is a natural algorithm to be used on lists.  It is also works very well on already sorted lists, or list with just one permutation 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).  But this enhancement does not worth additional complexity as there are more efficient algorithms of comparable complexity which achieve the same goals (mergesort, etc).

Old News ;-)

[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

---

In case of broken links please try to use Google search. If you find the page please notify us about new location

• 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
• Bubble Sort - C++, Java, Algorithm and Data Structure Tutorials by Denis Kulagin

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