Bubble Sort
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

Bubble Sort is by far the simplest and shortest of all the sorting algorithms. Here is the code for it:

( About Example C++ code )

// By convention, 'n' is usually the size of the
// array to be sorted.
void bubblesort( int array[], int n )
{
  for ( int i = 0; i < n-1; ++i )
    for ( int j = 1; j < n-i; ++j )
      if ( array[j-1] > array[j] )
        // Note the use here of swap()
        swap( array[j-1], array[j] );
}
              

You can see why we call this a short algorithm. Even though it's short, I will explain it anyway.

Basically, this algorithm goes through the entire array and compares every adjacent pair of elements in the array starting from the first and working towards the last. This cycle is repeated over and over until the entire array is sorted.

Notice that at the end of each cycle, the last element, and then the next to last element, and so on is in place. Thus, the cycle is shortened by one element each time so that we don't have to bother with the last elements which are already in place.

Let us walk through this algorithm on an example: 3 2 5 4 1. Note that n = 5.

First Iteration ( i = 0 ): We are considering the array 3 2 5 4 1.

( j = 1 ): 3 > 2, so swap() and the array is now 2 3 5 4 1.
( j = 2 ): 3 < 5, so nothing happens and the array is still 2 3 5 4 1.
( j = 3 ): 5 > 4, so swap() and the array is now 2 3 4 5 1.
( j = 4 ): 5 > 1, so swap() and the array is now 2 3 4 1 5.

j is no longer strictly less than n - i, so we are finished with the First Iteration.

Second Iteration ( i = 1 ): We are now considering the array 2 3 4 1. (Not the last one, remember? n - i = 4, so we only consider the first 4 elements.)

( j = 1 ): 2 < 3, so nothing happens and the array is still 2 3 4 1.
( j = 2 ): 3 < 4, so nothing happens and the array is still 2 3 4 1.
( j = 3 ): 4 > 1, so swap() and the array is now 2 3 1 4.

j is no longer strictly less than n - i, so we are finished with the Second Iteration.

Third Iteration ( i = 2 ): We are now considering the array 2 3 1.

( j = 1 ): 2 < 3, so nothing happens and the array is still 2 3 1.
( j = 2 ): 3 > 1, so swap() and the array is now 2 1 3.

j is no longer strictly less than n - i, so we are finished with the Third Iteration.

Fourth Iteration ( i = 3 ): We are now considering the array 2 1.

( j = 1 ): 2 > 1, so swap() and the array is now 1 2.

j is no longer strictly less than n - i, so we are finished with the Fourth Iteration.

Now i is no longer strictly less than n-1, so we are finished sorting.

Now that you have seen the entire sorting process written out, the algorithm will make more sense to you.

One of the problems with Bubble Sort is that even when the array is fully sorted, the sort continues. This problem, however, is easily remedied: just insert a boolean flag that keeps track of whether or not the sort called swap() on anything in the last iteration. If it did not, then the sort has finished early.

Still, improving the efficiency of the Bubble Sort algorithm is really quite a useless effort. If you want more efficiency, use another algorithm. The reason for using Bubble Sort is because it is easy to type, so making Bubble Sort more complex is not really all that appealing.

If you would like a usable version of the Bubble Sort algorithm, there is one below that uses templates. The only efficiency improvement to Bubble Sort is the early exit flag, since that does not add much length to the code.

Download from Source Code Repository: sorts/bubble.h