Bubble Sort: The Algorithm

Now that you've seen the code and have done a tracing activity, please work out the following exercises.

Exercise Explain the bubble sort algorithm (at high-level). Supply your explanation with a concise pseudocode.

Demo

The following slides assist in building an intuition for the answer:

Solution

The idea of Selection Sort is that we repeatedly find the smallest element in the list and bring it to the left side.

for i gets the values from last index to 1
  for j gets the values from 0 to i-1
    if val[j] > val[j+1]
      swap val[j] & val[j+1]
  • The pseudocode does not have the "stop early if no swaps" optimization.

Exercise Analyze the running time of the bubble sort algorithm. In particular, think about where comparisons and swaps are being made and how many of them occur in each pass through the collection to be sorted.

Solution

The algorithm has a quadratic running time, i.e., $O(n^2)$.

Looking at the pseudocode:

  • Each inner pass has a comparison for each neighboring pair in the unsorted part of the array. Thus, swaps occur any time a neighboring pair is "out of order."

  • In the worst case, every comparison would result in a swap when one has an array in descending order. There would then be $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$ comparisons and swaps, where $n$ is the number of elements; the time complexity of the worst case is $O(n^2)$.

Bubble sort requires $O(n)$ space: $O(n)$ input and $O(1)$ auxiliary space.

Resources