Skip to content

Bubble Sort

This page provides a brief introduction to bubble sort.

Definition

Bubble sort is a simple sorting algorithm. During the execution of the algorithm, smaller elements gradually "float" to the top of the sequence like bubbles, hence the name bubble sort.

Process

Its working principle is to check two adjacent elements each time. If the preceding element and the following element satisfy the given sorting condition, the two adjacent elements are swapped. When no adjacent elements need to be swapped, the sorting is complete.

After \(i\) scans, the last \(i\) elements of the sequence must be the largest \(i\) elements. Therefore, bubble sort requires at most \(n-1\) scans of the array to complete the sorting.

Properties

Stability

Bubble sort is a stable sorting algorithm.

Time Complexity

When the sequence is completely sorted, bubble sort only needs to traverse the array once without performing any swap operations, with a time complexity of \(O(n)\).

In the worst case, bubble sort performs \(\frac{(n-1)n}{2}\) swap operations, with a time complexity of \(O(n^2)\).

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

Code 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 & flag\gets True\\ 5 & \textbf{while }flag\\ 6 & \qquad flag\gets 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 flag\gets 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
// Assuming the array size is n + 1, bubble sort starts from 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 size is n + 1, bubble sort starts from 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;
            }
        }
    }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用