Skip to content

Bubble Sort

This page gives a brief introduction to bubble sort.

Definition

Bubble sort is a simple sorting algorithm. It takes its name from the way smaller elements slowly "float" to the top of the sequence, like bubbles, as the algorithm runs.

Procedure

Bubble sort repeatedly examines two adjacent elements and swaps them if the earlier one and the later one satisfy the given sorting condition. Once no adjacent elements need to be swapped, the sort is finished.

After \(i\) passes, the last \(i\) entries of the sequence are its \(i\) largest, so \(n-1\) passes are enough to sort the array.

Properties

Stability

Bubble sort is a stable sorting algorithm.

Time complexity

When the sequence is already fully sorted, bubble sort makes a single pass over the array and performs no swaps, so it runs in \(O(n)\).

In the worst case, it performs \(\dfrac{(n-1)n}{2}\) swaps and runs in \(O(n^2)\).

The average-case time complexity of bubble sort is \(O(n^2)\).

Implementation

Pseudocode

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textit{flag}\gets \mathrm{True}\\ 5 & \textbf{while }\textit{flag}\\ 6 & \qquad \textit{flag}\gets \mathrm{False}\\ 7 & \qquad\textbf{for }i\gets1\textbf{ to }n-1\\ 8 & \qquad\qquad\textbf{if }A[i]>A[i + 1]\\ 9 & \qquad\qquad\qquad \textit{flag}\gets \mathrm{True}\\ 10 & \qquad\qquad\qquad \text{Swap } A[i]\text{ and }A[i + 1] \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Assume the array has size n + 1; bubble sort starts at array index 1
void bubble_sort(int *a, int n) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = 1; i < n; ++i) {
      if (a[i] > a[i + 1]) {
        flag = true;
        int t = a[i];
        a[i] = a[i + 1];
        a[i + 1] = t;
      }
    }
  }
}
1
2
3
4
5
6
7
8
def bubble_sort(a, n):
    flag = True
    while flag:
        flag = False
        for i in range(1, n):
            if a[i] > a[i + 1]:
                flag = True
                a[i], a[i + 1] = a[i + 1], a[i]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Assume the array has size n + 1; bubble sort starts at array index 1
static void bubble_sort(int[] a, int n) {
    boolean flag = true;
    while (flag) {
        flag = false;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[i + 1]) {
                flag = true;
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
            }
        }
    }
}