7.1. Bubble sort

The bubble sort makes multiple passes through an array. It compares adjacent items and exchanges those that are out of order. Each pass through the array places the next largest value in its proper place. In essence, each item "bubbles" up to the location where it belongs.

Bubble sort: the first pass

Card 1: Compare 54 and 26.

These cards show the first pass of a bubble sort. Outlined items are being compared to see if they are out of order. If there are n items in the array, then there are \(n-1\) pairs of items that need to be compared on the first pass. Once the largest value in the array is part of a pair, it will continually be moved along until the pass is complete.

Since 54 is greater than 26, exchange them before moving to the next pair.

Text description

Array with 9 cells. From left to right: “54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.

“54” and “26” are highlighted.

Card 2: Compare 54 and 93.

The first exchange put 26 before 54. Since 54 is less than 93, these two values are already in order. Leave them in place.

Text description

Array with 9 cells. From left to right: “26”, “54”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.

“54” and “93” are highlighted.

Card 3: Compare 93 and 17.

Since 93 is greater than 17, exchange them. The largest value now starts moving toward the end of the array.

Text description

Array with 9 cells. From left to right: “26”, “54”, “93”, “17”, “77”, “31”, “44”, “55”, and “20”.

“93” and “17” are highlighted.

Card 4: Compare 93 and 77.

The previous exchange moved 93 one position to the right. Since 93 is greater than 77, exchange them too.

Text description

Array with 9 cells. From left to right: “26”, “54”, “17”, “93”, “77”, “31”, “44”, “55”, and “20”.

“93” and “77” are highlighted.

Card 5: Compare 93 and 31.

Since 93 is greater than 31, exchange them. Each exchange moves 93 one position closer to its final location.

Text description

Array with 9 cells. From left to right: “26”, “54”, “17”, “77”, “93”, “31”, “44”, “55”, and “20”.

“93” and “31” are highlighted.

Card 6: Compare 93 and 44.

Since 93 is greater than 44, exchange them and continue to the next adjacent pair.

Text description

Array with 9 cells. From left to right: “26”, “54”, “17”, “77”, “31”, “93”, “44”, “55”, and “20”.

“93” and “44” are highlighted.

Card 7: Compare 93 and 55.

Since 93 is greater than 55, exchange them. Only one pair remains to be compared on this pass.

Text description

Array with 9 cells. From left to right: “26”, “54”, “17”, “77”, “31”, “44”, “93”, “55”, and “20”.

“93” and “55” are highlighted.

Card 8: Compare 93 and 20.

Since 93 is greater than 20, exchange this final pair to complete the first pass.

Text description

Array with 9 cells. From left to right: “26”, “54”, “17”, “77”, “31”, “44”, “55”, “93”, and “20”.

“93” and “20” are highlighted.

Card 9: The first pass is complete; 93 is in its final position.

Eight comparisons have placed the largest value, 93, at the end. The outlined final cell will not be compared again. The remaining eight values still need to be sorted.

Text description

Array with 9 cells. From left to right: “26”, “54”, “17”, “77”, “31”, “44”, “55”, “20”, and “93”.

“93” is highlighted.

Starting with the array above, what will the second pass of bubble sort do?

Make eight adjacent comparisons and place 93 at the end again.

The first pass already placed 93 in its final position. The second pass only compares pairs within the first eight cells, so it needs seven comparisons.

Make seven adjacent comparisons and place 77 immediately before 93.

The largest value among the remaining eight items is 77. Seven comparisons move it to the end of that unsorted portion, while 93 stays in its final position.

Make seven adjacent comparisons and place 17 at the start.

A pass from left to right places the largest remaining value at the right end. Smaller values can move left by only one position per pass. Here, 17 moves to the second cell.

Make seven adjacent comparisons and finish sorting the array.

The second pass places 77 in its final position, but the array becomes [26, 17, 54, 31, 44, 55, 20, 77, 93]. The first seven values still need to be sorted.

Check answer

Bubble sort

At the start of the second pass, the largest value is now in place. There are \(n-1\) items left to sort, meaning that there will be \(n-2\) pairs. Since each pass places the next largest value in place, the total number of passes necessary will be \(n-1\). After completing the \(n-1\) passes, the smallest item must be in the correct position with no further processing required. The 'Run It' tab shows the complete bubble_sort function. It takes the array as a parameter, and modifies it by swapping items as necessary.

Typically, swapping two elements in an array requires a temporary storage location (an additional memory location). A code fragment such as

temp = alist[i];
alist[i] = alist[j];
alist[j] = temp;

will exchange the ith and jth items in the array. Without the temporary storage, one of the values would be overwritten.

Note

This exchange is referred to as the swap idiom and occurs frequently.

std::swap is part of the standard library and many swap specializations are defined to make swap efficient for standard library types.

Run it

The Bubble Sort

#include <iostream>
#include <vector>
using std::vector;

// function goes through list sorting adjacent values as it bubbles
// the largest value to the top.
vector<int> bubble_sort(vector<int> data) {
  for (int passnum = data.size()-1; passnum > 0; --passnum) {
    for (int i = 0; i < passnum; ++i) {
      if (data[i] > data[i+1]) {
        // could be replaced with std::swap
        int temp = data[i];
        data[i] = data[i+1];
        data[i+1] = temp;
      }
    }
  }
  return data;
}

int main() {
  vector<int> data = {54,26,93,17,77,31,44,55,20};

  for (const auto& value: bubble_sort(data)) {
    std::cout << value << ' ';
  }
  return 0;
}

The following animation shows bubble sort in action. The values being sorted are bars of various heights. When bar colors change to red, this indicates these are the two values compared by bubble sort. Bars shown in gray have already reached their final position.

Average case

Open video

Bubble sort on a deterministic shuffled input.

Best case

Open video

Bubble sort on an already sorted input.

Worst case

Open video

Bubble sort on a reverse sorted input.

7.1.1. Bubble sort analysis

To analyze the bubble sort, we should note that regardless of how the items are arranged in the initial array, \(n-1\) passes will be made to sort an array of size n. Table 1 shows the number of comparisons for each pass. The total number of comparisons is the sum of the first \(n-1\) integers. Recall that the sum of the first n integers is \(\frac{1}{2}n^{2} + \frac{1}{2}n\). The sum of the first \(n-1\) integers is \(\frac{1}{2}n^{2} + \frac{1}{2}n - n\), which is \(\frac{1}{2}n^{2} - \frac{1}{2}n\). This is still \(O(n^{2})\) comparisons. In the best case, if the array is already ordered, no exchanges will be made. However, in the worst case, every comparison will cause an exchange. On average, we exchange half of the time.

Table 1: Comparisons for Each Pass of Bubble Sort

Pass	Comparisons
1	\(n-1\)
2	\(n-2\)
3	\(n-3\)
...	...
\(n-1\)	\(1\)

Short Bubble

A bubble sort is often considered the most inefficient sorting method since it must exchange items before the final location is known. These "wasted" exchange operations are very costly. However, because the bubble sort makes passes through the entire unsorted portion of the array, it has the capability to do something most sorting algorithms cannot. In particular, if during a pass there are no exchanges, then we know that the array must be sorted. A bubble sort can be modified to stop early if it finds that the array has become sorted. This means that for arrays that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted array and stop. This modification is often referred to as the short bubble.

Run It

The 'Short' Bubble Sort

#include <iostream>
#include <utility>
#include <vector>
using std::vector;

vector<int> short_bubble(vector<int> data) {
  bool exchanges = true;
  int passnum = data.size();
  while (passnum > 0 && exchanges) {
    exchanges = false;
    for (int i = 0; i < passnum; ++i) {
      if (data[i] > data[i+1]) {
        std::swap(data[i], data[i+1]);
      }
    }
    // decrement passnum variable so that the next pass is one less
    // than the previous: the largest value has already 'bubbled' all the way up.
    --passnum;
  }

  return data;
}

int main() {
  vector<int> data = {20,30,40,90,50,60,70,80,110,100};

  for (const auto& value: short_bubble(data)) {
    std::cout << value << ' ';
  }
  return 0;
}

Self Check

Q1

Suppose you have the following array of numbers to sort: [19, 1, 9, 7, 3, 10, 13, 15, 8, 12] which array represents the partially sorted list after three complete passes of bubble sort?

[1, 9, 19, 7, 3, 10, 13, 15, 8, 12]

This answer represents three swaps. A pass means that you continue swapping all the way to the end of the list.

[1, 3, 7, 9, 10, 8, 12, 13, 15, 19]

Very Good

[1, 7, 3, 9, 10, 13, 8, 12, 15, 19]

A bubble sort continues to swap numbers up to index position passnum. But remember that passnum starts at the length of the list - 1.

[1, 9, 19, 7, 3, 10, 13, 15, 8, 12]

You have been doing an insertion sort, not a bubble sort.

Check answer

More to Explore

• Bubble Sort visualization

• OpenDSA: Bubble Sort

• Bubble sort

Acknowledgements

This section is adapted from Problem Solving with Algorithms and Data Structures using C++, by Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College released under the CC BY-NC-SA 4.0, and Open Data Structures (OpenDSA) by Ville Karavirta and Cliff Shaffer which is distributed under the MIT License.