Bubble Sort

Idea

Bubble Sort repeatedly compares adjacent elements and “bubbles” the larger (or smaller) one toward the end, pass by pass, until fully sorted.

Algorithm

1. Scan adjacent pairs; swap if out of order.
2. Each pass bubbles the max (or min) of the unsorted part to the end.
3. Repeat for $n-1$ passes until sorted.

Pseudo-code:

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if A[j] > A[j+1]:
            swap(A[j], A[j+1])

Code Implementation

#include <stdbool.h>

void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;             // whether a swap happened in this pass
        for (int j = 0; j < n - 1 - i; j++) {
            if (A[j] > A[j + 1]) {
                int tmp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = tmp;
                flag = true;
            }
        }
        if (!flag) break;              // no swap in this pass, so it is already sorted
    }
}

Optimization Notes

The flag flag records whether any swap happened during the pass: if a pass performs no swap at all, the sequence is already sorted and the algorithm can stop early. This makes the best case (an already sorted array) take a single pass and $n-1$ comparisons, reaching $O(n)$.

Complexity

• Best: $O(n)$ (already sorted, with early-exit optimization)
• Worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: stable

Exercises

Exercise 1

Sort $A = [4, 3, 2, 1]$ with bubble sort; show each pass.

Exercise 2

What are the time and space complexities of bubble sort?