5.4.1. Bubble Sort¶

Our next sorting algorithm is called Bubble Sort. Bubble Sort is often taught to novice programmers in introductory computer science courses. This is unfortunate, because Bubble Sort has no redeeming features whatsoever. It is rather slow, even compared to the other \(\Theta(n^2)\) sorts that are commonly known. It is not particularly intutitive -- nobody is going to come naturally to Bubble Sort as a way to sort their Bridge hand or their pile of bills like they might with Insertion Sort or Selection Sort. However, Bubble Sort can viewed as a close relative of Selection Sort.

Like Insertion Sort, Bubble Sort consists of a simple double for loop. The inner for loop moves through the record array from left to right, comparing adjacent keys. If a record's key value is greater than the key of its right neighbor, then the two records are swapped. Once the record with the largest key value is encountered, this process will cause it to "bubble" up to the right of the array (which is where Bubble Sort gets its name). The second pass through the array repeats this process. However, because we know that the record with the largest value already reached the right of the array on the first pass, there is no need to compare the rightmost two records on the second pass. Likewise, each succeeding pass through the array compares adjacent records, looking at one less record toward the end than did the preceding pass. Here is an implementation.

static <T extends Comparable<T>> void bubblesort(T[] A) {
  for (int i=0; i<A.length-1; i++) // Insert i'th record
    for (int j=1; j<A.length-i; j++)
      if (A[j-1].compareTo(A[j]) > 0)
        Swap.swap(A, j-1, j);
}

void bubblesort(Comparable* A[], int n) {
  for (int i = 0; i < n-1; i++) // Insert i'th record
    for (int j = 0; j < n-i; j++) 
      if (*A[j] > *A[j+1]) 
        swap(A, j, j+1);
}

Settings

Saving...
Server Error
Resubmit

Now we continue with the second pass. However, since the largest record has "bubbled" to the very right, we will not need to look at it again.

Settings

Saving...
Server Error
Resubmit

Bubble Sort continues in this way until the entire array is sorted.

The following visualization shows the complete Bubble Sort. You can input your own data if you like.

Now try for yourself to see if you understand how Bubble Sort works.

5.4.2. Bubble Sort Analysis¶

The following visualization illustrates the running time analysis of Bubble Sort.

Settings

Saving...
Server Error
Resubmit

Thus, Bubble Sort's running time is roughly the same in the best, average, and worst cases.

The number of swaps required depends on how often a record's value is less than that of the record immediately preceding it in the array. We can expect this to occur for about half the comparisons in the average case, leading to \(\Theta(n^2)\) for the expected number of swaps. The actual number of swaps performed by Bubble Sort will be identical to that performed by Insertion Sort.

Here are some review questions to check your understanding of Bubble Sort.