2.5 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 Θ(n2)\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.

function bubbleSort(A):
    N = A.size()
    for i = 0 to N-2:
        // Bubble up the i'th element
        for j = 1 to N-i-1:
            if A[j-1] > A[j]:
                swap(A, j-1, j)

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.

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.

2.5.1 Bubble Sort Analysis

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

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 Θ(n2)\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.

2.5.2 Review questions: Bubble sort

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

Answer TRUE or FALSE.

Bubble Sort (as the code is written in this module) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

  • Remember that: Bubble Sort consists of a simple double for loop.
  • The first iteration of the inner for loop moves through the record array from bottom to top, comparing adjacent keys.
  • If the lower-indexed keys value is greater than its higher-indexed neighbor, then the two values are swapped.

In which cases are the time complexities the same for Bubble Sort (as the algorithm is presented in this module)?

  • Does Bubble Sort’s cost vary according to the order of the array input values?
  • No, it does not matter what order the input values have.

The order of the input records has what impact on the number of comparisons required by Bubble Sort (as presented in this module)?

  • Does Bubble Sort change when it make a comparison according to the order of the array input values?
  • No, it does not matter what order the input values have.

What is the worst-case time for Bubble Sort (as the algorithm is presented in this module) to sort an array of nn records?

  • Does Bubble Sort’s number of comparisons depend on the particular order of the input array?
  • No, it does not.

What is the running time of Bubble Sort when the input is an array where all record values are equal?

  • Each comparison test in the inner for loop will fail because the value at position ii is never less than the value at position i−1i-1.
  • However, this observation does not affect the number of comparisons to be made, it only affects the number of swaps.

What is the running time for Bubble Sort when the input array has values that are in reverse sort order?

  • On each iteration, the iith record will have to move to the start of the array.
  • This is the worst case.

What is the running time of Bubble Sort (as the algorithm is presented in this module) when the input is an array that has already been sorted?

  • Each test in the inner for loop will fail because the value at position ii is never less than the value at position i−1i-1.

When is Bubble Sort a good choice for sorting an array?

  • Does Bubble Sort’s cost vary with how much the input is out of order?
  • Bubble Sort always does a lot of work, as compared to other sorting algorithms.

In the worst case, the total number of comparisons for Bubble Sort is closest to:

  • Bubble Sort’s implementation is made up of two nested for loops.
  • The outer for loop is executed n−1n-1 times.
  • The inner for loop is executed ii times.
  • The total cost is the sum of ii’s for ii goes from 1 to nn.