Sorting

Bubble Sort

Repeatedly walk the array comparing adjacent pairs and swapping any that are out of order. After pass k, the k largest elements are in their final positions at the end. Early-exit when a pass makes zero swaps.

Algorithm

Canonical input from the lesson spec is [5, 1, 4, 2, 8]. Three passes sort the array; pass three triggers the early exit.

Basic Implementation

basic.py 
arr = [5, 1, 4, 2, 8]
n = len(arr)
for i in range(n - 1):
    swapped = False
    for j in range(n - i - 1):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            swapped = True
    if not swapped:
        break
print(arr)

Complexity

  • Time: O(n^2) worst and average, O(n) best with early exit
  • Space: O(1)
  • Stable: yes

Implementation notes

  • Python: write the two explicit loops and the swapped flag. Do not call arr.sort() or sorted(); both hide the comparison-and-swap mechanics.
  • The replay shows the compared pair on each frame and the post-swap array, matching the lesson spec's per-pass tables.
adjacent swap Swap neighbouring out-of-order pairs.
early termination A pass with zero swaps means the array is already sorted.