Bubble Sort

Sweep through your data swapping adjacent items if they're the wrong way around. A factor of 2 improvement can be made by having successive sweeps get shorter. Time-complexity is (n-1)*(n-2)/2 comparisons and we expect (on average) to make half that many exchanges. If you don't swap equal items, it's stable.

Comes in two basic flavors. One scans the data until it knows there can be no problems remaining (n-1 sweeps, as above), the other sets a flag if items were swapped and sweeps until the flag remains false. The latter stops early if the data were almost sorted to start with but carries a small extra cost associated with having and setting the flag.

BubbleSort is easy to understand, easy to code, but inefficient. One hypothetical Really Aggressive Optimizer automatically recognizes undergraduate implementations of bubble sort and replaces them with something better.

Separating the ideas of "finding the largest" and "moving the largest" gives InsertionSort and SelectionSort, the comparative speeds of which depend on which is more expensive, comparisons or swaps. See those pages for more details.

BubbleSort is never faster than InsertionSort, so long as the InsertionSort does not use a binary search.

BubbleSort is faster than InsertionSort on an array of 3 elements.

It is important to remember that Bubble Sort is not a 100% useless algorithm - if you have a sequence of objects that you would like to keep ordered that is occasionally perturbed by having the value of one or two objects increase or decrease, bubble sorting is a good thing. Consider Z-buffering a field of mostly-immobile objects. Say one or two objects move closer or further away from the observer - the sorting would be simply swapping a few adjacent slots, which is what Bubble Sort is ideal for. Meanwhile, the Merge Sort or Quick Sort algorithm would be inefficient. Quick sort is notoriously clumsy in cases where the list is already nearly-sorted. Of course, an insertion-sort on the perturbed objects is usually better.

Sample code in CeeLanguage

  void
  bubble_sort (int a[], int n /* the size of array */)
  {
int i;
for (i = 0; i < n - 1; i++)
{
int j;
for (j = n - 1; j > i; j--)
{
if (a[j - 1] > a[j])
{
  /* Swap a adjacent pair of items. */
  int t = a[j - 1];
  a[j - 1] = a[j];
  a[j] = t;
}
}
}
  }

This formulation obtains the advertised best-case performance of O(n). Otherwise, best-case == worse-case == average-case == O(n^2).

  void
  bubble_sort (int a[], int n /* the portion of the array that is unsorted */)
  {
int i, sorted;
do {
sorted = 1;
--n;
for (i = 0; i < n; i++)
{
if (a[i] > a[i + 1])
{
  /* Swap adjacent pair of items. */
  int t = a[i];
  a[i] = a[i + 1];
  a[i + 1] = t;
  sorted = 0;
}
}
} while (!sorted);
  }

Sample code in PythonLanguage:

 def bubble(alist):
length = len(alist)
for i in xrange(length-1):
for j in xrange(length-i-1):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]

 def bubble_flag(alist):
length = len(alist)
for i in xrange(length-1):
swapped = False
for j in xrange(length-i-1):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
swapped = True
if not swapped: return

 sort: aCollection
^aCollection size < self switchSize
ifTrue: [^self insertionSort: aCollection]
ifFalse: [^self quickSort: aCollection]

I tested a quick-coded bubble sort vs Dolphin's sort [DolphinSmalltalk?] (which I suppose is QuickSort, as most STs are, though I didn't look.) At 10 or 20 elements, the bubble was faster. At 100, the built-in sort was about 3x faster. -- RonJeffries

Care to find the break-even point, and then repeat, comparing the bubble sort with HeapSort?

I've always thought that Bubble Sort should be called Rock Sort because the in order elements actually fall to the bottom not bubble to the top. Depends purely on whether you run forwards or backwards.

-- CurtisCooley