Bubble Sort — Specification¶

Algorithm Specification — Reference Standard

Source: Knuth, The Art of Computer Programming, Vol. 3 — Section 5.2.2 Source: CLRS, Introduction to Algorithms — Problem 2-2

Table of Contents¶

1. Algorithm Reference
2. API / Interface Reference
3. Core Rules and Behavioral Specification
4. Schema / Parameters Reference
5. Behavioral Specification
6. Edge Cases
7. Complexity Compatibility Matrix
8. Reference Implementations
9. Compliance & Best Practices Checklist
10. Related Documentation

1. Algorithm Reference¶

2. API / Interface Reference¶

Standard Function Signature¶

BUBBLE_SORT(A: array of T, cmp: (T, T) → int) → void
  Sorts A in place using cmp, where cmp(a, b) returns:
    < 0  if a should come before b
    = 0  if a and b are equivalent
    > 0  if a should come after b

Postcondition:
  ∀ i ∈ [0, n-2]: cmp(A[i], A[i+1]) ≤ 0
  AND A is a permutation of the original input.

Language-Specific Equivalents¶

None of the standard libraries use Bubble Sort. Bubble Sort is taught, not deployed.

3. Core Rules and Behavioral Specification¶

Rule 1: Adjacent-Pair Compare-and-Swap¶

Knuth TAOCP §5.2.2: "On each pass, compare each adjacent pair and exchange if out of order."

# ✅ Correct — adjacent pair, in-place swap
if A[j] > A[j + 1]:
    A[j], A[j + 1] = A[j + 1], A[j]

# ❌ Incorrect — non-adjacent comparison (not Bubble Sort)
if A[j] > A[k]:  # k != j+1
    A[j], A[k] = A[k], A[j]

Rule 2: Strict Greater-Than for Stability¶

Specification: Bubble Sort must use strict > (not >=) to be stable.

# ✅ Correct — stable
if A[j] > A[j + 1]:
    swap()

# ❌ Incorrect — destroys stability
if A[j] >= A[j + 1]:
    swap()

Rule 3: Shrinking Inner Loop Bound¶

Optimization: After pass i, the last i+1 elements are in final sorted positions. Inner loop must not revisit them.

# ✅ Correct
for j in range(0, n - 1 - i):
    ...

# ❌ Incorrect — wastes O(n) comparisons per pass (still correct, just slow)
for j in range(0, n - 1):
    ...

Rule 4: Early-Exit Flag¶

Optimization: If a complete pass performs no swaps, the array is sorted; terminate immediately.

# ✅ Correct — adaptive
swapped = False
for j in range(...):
    if A[j] > A[j + 1]:
        swap()
        swapped = True
if not swapped:
    break

Rule 5: Total Order Required¶

Precondition: The comparison function must define a total order — reflexive, antisymmetric, transitive, and total. Non-total orders cause undefined behavior.

4. Schema / Parameters Reference¶

Returns: void (in-place); some APIs return the array for chaining.

5. Behavioral Specification¶

Normal Operation¶

For input A of length n ≥ 2:

1. Pass 1: Compare every adjacent pair from index 0 to n-2. Swap when out of order. The maximum reaches index n-1.
2. Pass i (1 ≤ i ≤ n-2): Compare adjacent pairs from 0 to n-1-i. Swap when out of order. The i-th largest reaches index n-i.
3. Termination: When pass i performs zero swaps (early-exit) OR i = n-1.

For inputs of length 0 or 1: return immediately, no work done.

Documented Limitations¶

Error / Failure Conditions¶

6. Edge Cases¶

7. Complexity Compatibility Matrix¶

Comparator Compatibility¶

8. Reference Implementations¶

Knuth Algorithm B (TAOCP Vol. 3)¶

Algorithm B (Bubble sort).
  Records R_1, R_2, ..., R_n with keys K_1, K_2, ..., K_n.
  This algorithm rearranges them so K_1 ≤ K_2 ≤ ... ≤ K_n.

B1. [Initialize BOUND.]   BOUND ← N.
B2. [Loop on j.]          t ← 0.
                          For j = 1, 2, ..., BOUND - 1, do step B3:
B3. [Compare/exchange R_j : R_{j+1}.]
                          If K_j > K_{j+1}, then exchange R_j ↔ R_{j+1},
                          and set t ← j.
B4. [Any exchanges?]      If t = 0, terminate.
                          Otherwise BOUND ← t and go back to B2.

This is the adaptive Bubble Sort (using last-swap-position to set the next bound) — slightly more efficient than the textbook "shrink by 1 per pass" variant.

Reference: Knuth's Adaptive Variant¶

Go¶

package main

import "fmt"

// BubbleSortKnuth implements Knuth's Algorithm B from TAOCP Vol. 3 §5.2.2.
func BubbleSortKnuth(arr []int) {
    n := len(arr)
    bound := n
    for {
        t := 0
        for j := 0; j < bound-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
                t = j + 1
            }
        }
        if t == 0 {
            return
        }
        bound = t
    }
}

func main() {
    data := []int{5, 1, 4, 2, 8}
    BubbleSortKnuth(data)
    fmt.Println(data)
}

Java¶

public class BubbleSortKnuth {
    public static void sort(int[] arr) {
        int n = arr.length;
        int bound = n;
        while (true) {
            int t = 0;
            for (int j = 0; j < bound - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    t = j + 1;
                }
            }
            if (t == 0) return;
            bound = t;
        }
    }
}

Python¶

def bubble_sort_knuth(arr):
    """Knuth's Algorithm B from TAOCP Vol. 3 §5.2.2."""
    n = len(arr)
    bound = n
    while True:
        t = 0
        for j in range(bound - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                t = j + 1
        if t == 0:
            return
        bound = t

9. Compliance & Best Practices Checklist¶

• Uses strict > comparison (preserves stability)
• Implements early-exit flag (achieves O(n) on sorted input)
• Implements shrinking inner-loop bound (avoids redundant comparisons)
• Handles empty array and single element safely
• Comparator (if custom) defines a total order (transitive, antisymmetric)
• Documents in-place mutation in function comment/docstring
• Does not use Bubble Sort for n > 50 in production paths
• Includes regression test with adversarial input (reverse-sorted, all-equal, with duplicates)
• Uses language-native sort (sort.Slice, Arrays.sort, sorted) for production

10. Related Documentation¶

Specification Notes: - The "canonical" Bubble Sort is the textbook 2-loop form (CLRS Problem 2-2), but Knuth's Algorithm B (using the last-swap-position) is strictly faster on most inputs and is the recommended reference. - Standard library sorts in every major language are NOT Bubble Sort — they are O(n log n) hybrids (TimSort, Pdqsort, Dual-Pivot Quicksort). - Bubble Sort's only legitimate production niche is detecting "is this array already sorted?" in a single O(n) pass — and even there, a direct linear scan is more idiomatic.