Bubble Sort

This is probably the simplest way sort an array of objects. Unfortunately it is also the slowest way! The basic idea is to compare two neighboring objects, and to swap them if they are in the wrong order. Given an array a of numbers, with length n, here's a snippet of C code for bubble sort:
for (i=0; i<n-1; i++) {
  for (j=0; j<n-1-i; j++)
    if (a[j+1] < a[j]) {  /* compare the two neighbors */
      tmp = a[j];         /* swap a[j] and a[j+1]      */
      a[j] = a[j+1];
      a[j+1] = tmp;
  }
}
As we can see, the algorithm consists of two nested loops. The index j in the inner loop travels up the array, comparing adjacent entries in the array (at j and j+1), while the outer loop causes the inner loop to make repeated passes through the array. After the first pass, the largest element is guaranteed to be at the end of the array, after the second pass, the second largest element is in position, and so on. That is why the upper bound in the inner loop (n-1-i) decreases with each pass: we don't have to re-visit the end of the array.

Here's a demonstration of bubble sort. If you need instructions on running the demo, look here.

The algorithm starts with an array of random numbers. Each number is represented with a vertical stick. The height of the stick indicates the value of the number, and its left-right position indicates its location in the array.

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

Now let's see what happens if the numbers in the array are already sorted, but in reverse order. Notice that swapping two adjacent elements is not a very efficient way to move elements from one end of the array to the other!

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

Next we run bubble sort on an array of numbers which is already almost sorted. As you can see, there are fewer swaps this time. In fact, the array is sorted after just a few passes of the inner loop.

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***


Alejo Hausner, CS Department, Princeton University
Last modified: Thu Jul 11 12:39:17 1996