Previous Topic

What Is Bubble Sort?

Bubble Sort is a basic sorting algorithm that orders elements by repeatedly comparing and swapping adjacent pairs that are out of order. After each full pass through the list, the largest remaining element “bubbles up” to its correct position at the end. The process continues until the list is sorted.

How It Works

• Start at the beginning of the list.
• Compare the current element with the next element.
• If they are out of order (e.g., current > next for ascending sort), swap them.
• Move one position forward and repeat until the end of the unsorted portion.
• Repeat passes until a full pass occurs with no swaps (the list is sorted).

Pseudocode (Optimized with Early Exit)

function bubble_sort(A):
    n = length(A)
    repeat
        swapped = false
        for i from 0 to n - 2:
            if A[i] > A[i + 1]:
                swap(A[i], A[i + 1])
                swapped = true
        n = n - 1        # largest element is now at position n
    until not swapped
    return A

Example

Given A = [5, 1, 4, 2, 8]

1. Pass 1 comparisons and swaps: [5,1] → swap → [1,5,4,2,8]; [5,4] → swap → [1,4,5,2,8]; [5,2] → swap → [1,4,2,5,8]; [5,8] → no swap. Largest (8) placed at the end.
2. Pass 2 works up to the second-to-last position; repeat until no swaps occur.

Complexity and Properties

• Time complexity: best O(n) with early exit on already-sorted input; average and worst O(n^2).
• Space complexity: O(1) extra space (in-place).
• Stability: stable (equal elements keep their relative order when swapping only adjacent elements).
• Deterministic: always produces the same result for the same input and ordering rule.

Pros

• Simple to implement and understand.
• In-place and stable by default.
• Early-exit optimization makes it efficient on already or nearly sorted data.

Cons

• Quadratic time on average and in the worst case; poor for large datasets.
• Generally outperformed by insertion sort and more advanced algorithms like merge sort and quicksort.

Common Variants and Optimizations

• Early Exit (Swapped Flag): Stop if a pass makes no swaps.
• Shrinking Boundary: After each pass, reduce the inner loop range since the last element of that pass is in correct position.
• Last-Swap Index: Track the index of the last swap to further reduce the next pass’s boundary.
• Cocktail Shaker Sort: A bidirectional version that bubbles both the largest and smallest elements in alternating passes.

When to Use

• Educational settings to illustrate comparison, swapping, and algorithmic reasoning.
• Very small arrays where implementation simplicity outweighs performance concerns.
• Inputs that are already or nearly sorted, combined with early exit.

Implementation Tips

• Do not swap equal elements; this preserves stability.
• Use a boolean swapped flag to detect early completion.
• Carefully manage loop bounds to avoid out-of-range access.
• If using a custom comparator, consistently define order (e.g., ascending or descending) and handle edge cases like NaN values in floating-point lists.

Related Concepts

• Comparison-based sorting
• Stable vs. unstable sorting
• In-place algorithms
• Time and space complexity; Big-O notation

Practice

1. Implement bubble sort with and without an early-exit optimization.
2. Modify bubble sort to sort in descending order.
3. Instrument your implementation to count comparisons and swaps on random vs. nearly sorted input.
4. Implement the last-swap index optimization and compare pass counts.

Next Topic