AIOJ

This page briefly introduces bubble sort.

Definition

Bubble sort (English: Bubble sort) is a simple sorting algorithm. Since, during its execution, smaller elements slowly “float” to the top of the sequence like bubbles, it is called bubble sort.

Process

It works by checking 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, sorting is complete.

After $i$ scans, the final $i$ elements of the sequence must be the largest $i$ elements. Therefore, bubble sort needs to scan the array at most $n-1$ times to complete sorting.

Properties

Stability

Bubble sort is a stable sorting algorithm.

Time complexity

When the sequence is already completely sorted, bubble sort only needs to traverse the array once and does not perform any swaps, so its time complexity is $O(n)$ .

In the worst case, bubble sort performs $\frac{(n-1)n}{2}$ swaps, so its time complexity is $O(n^2)$ .

The average 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 & 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}

C++

// Assume that the array size is n + 1 and 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;
      }
    }
  }
}

Python

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]

Java

// Assume that the array size is n + 1 and 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;
            }
        }
    }
}

Bubble Sort