Bubble Sort

Basic Algorithm

This algorithm is very simple to understand and to program. It works by stepping through the unordered array and comparing all neighbouring pairs of values one at a time. If they are in the wrong order the two items are swapped around. This is done one less time than the array's length i.e. if the array is 10 entries long then performing the scan 9 times will always guarantee completion.

Example Code:

  01   for (int x=0; x < (array.length-1); x++) {
  02
  03      for (int y=0; y < (array.length-1); y++) {
  04
  05         if (array[y] > array[y+1]) {
  06            swap       = array[y];
  07            array[y]   = array[y+1];
  08            array[y+1] = swap;
  09         }
  10      }
  11   }

Improvements

Sorting may be completed before the outer loop is ! To solve this flaw a flag can be used, resetting it to zero at the start of the outer loop. When a change is made during the inner loop it is set or incremented to indicate a change has been made. The final change is to check the flag at the end of each outer loop and if it is not set to break the loop.

The action of the bubble sort causes the largest/heaviest item to drop to the bottom of the array after a single pass. Therefore the point at which we stop the inner loop creeps up by one place for every outer loop. i.e. cycle 1 finishes at item length - 2, cycle 2 finishes at item length - 3, etc.

Example Code:

  01   int finflag  = 1,
  02       endpoint = array.length;
  03
  04   for (int x=0; (x < (array.length-1)) && (finflag > 0); x++) {
  05
  06      finflag = 0;
  07      endpoint--;
  08
  09      for (int y=0; y < endpoint; y++) {
  10
  11         if (array[y] > array[y+1]) {
  12            swap       = array[y];
  13            array[y]   = array[y+1];
  14            array[y+1] = swap;
  15
  16            finflag++;
  17         }
  18      }
  19   }

A Big Improvement

One major problem with the bubble sort is that lighter items take longer to rise. If the last item in the unordered array is the lowest then a bubble sort will take the exactly length - 1 times to reorder the list even though it may be the only item out of order. To solve this the direction of the scans can be alternated (see figure below).

A Final Word

All the changes to this algorithm make it more efficient at the expense of its simplicity. There are much better methods around for sorting unordered lists but none of these will beat the bubble sort if only one item is out of sequence and the sort is done in the correct direction. Basically the only reasons for using this method are its simplicity or its speed as an insertion algorithm.