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.

adjacent swap Swap neighbouring out-of-order pairs.
early termination A pass with zero swaps means the array is already sorted.

Basic Implementation

basic.py
Replay: real traced execution (multi-file project)
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)

  1. arr ← [5, 1, 4, 2, 8]

    1arr = [5, 1, 4, 2, 8]2n = len(arr)
    values this step[5, 1, 4, 2, 8]arr

  2. n ← 5

    1arr = [5, 1, 4, 2, 8]2n = len(arr)3for i in range(n - 1):
    values this step5n[5, 1, 4, 2, 8]arr

  3. swapped ← False

    3for i in range(n - 1):4    swapped = False5    for j in range(n - i - 1):
    values this stepFalseswapped

  4. arr[j] > arr[j+1] ← True

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepTruearr[j] > arr[j+1][5, 1, 4, 2, 8]arr0j5arr[j]1arr[j+1]

  5. arr ← [1, 5, 4, 2, 8], swapped ← True

    6if arr[j] > arr[j + 1]:7    arr[j], arr[j + 1] = arr[j + 1], arr[j]8    swapped = True
    values this step[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]arrTrueswapped

  6. arr[j] > arr[j+1] ← True

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepTruearr[j] > arr[j+1][1, 5, 4, 2, 8]arr1j5arr[j]4arr[j+1]

  7. arr ← [1, 4, 5, 2, 8], swapped ← True

    6if arr[j] > arr[j + 1]:7    arr[j], arr[j + 1] = arr[j + 1], arr[j]8    swapped = True
    values this step[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]arrTrueswapped

  8. arr[j] > arr[j+1] ← True

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepTruearr[j] > arr[j+1][1, 4, 5, 2, 8]arr2j5arr[j]2arr[j+1]

  9. arr ← [1, 4, 2, 5, 8], swapped ← True

    6if arr[j] > arr[j + 1]:7    arr[j], arr[j + 1] = arr[j + 1], arr[j]8    swapped = True
    values this step[1, 4, 5, 2, 8] → [1, 4, 2, 5, 8]arrTrueswapped

  10. arr[j] > arr[j+1] ← False

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepFalsearr[j] > arr[j+1][1, 4, 2, 5, 8]arr3j5arr[j]8arr[j+1]

  11. swapped ← False

    3for i in range(n - 1):4    swapped = False5    for j in range(n - i - 1):
    values this stepFalseswapped

  12. arr[j] > arr[j+1] ← False

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepFalsearr[j] > arr[j+1][1, 4, 2, 5, 8]arr0j1arr[j]4arr[j+1]

  13. arr[j] > arr[j+1] ← True

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepTruearr[j] > arr[j+1][1, 4, 2, 5, 8]arr1j4arr[j]2arr[j+1]

  14. arr ← [1, 2, 4, 5, 8], swapped ← True

    6if arr[j] > arr[j + 1]:7    arr[j], arr[j + 1] = arr[j + 1], arr[j]8    swapped = True
    values this step[1, 4, 2, 5, 8] → [1, 2, 4, 5, 8]arrTrueswapped

  15. arr[j] > arr[j+1] ← False

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepFalsearr[j] > arr[j+1][1, 2, 4, 5, 8]arr2j4arr[j]5arr[j+1]

  16. swapped ← False

    3for i in range(n - 1):4    swapped = False5    for j in range(n - i - 1):
    values this stepFalseswapped

  17. arr[j] > arr[j+1] ← False

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepFalsearr[j] > arr[j+1][1, 2, 4, 5, 8]arr0j1arr[j]2arr[j+1]

  18. arr[j] > arr[j+1] ← False

    5for j in range(n - i - 1):6    if arr[j] > arr[j + 1]:7        arr[j], arr[j + 1] = arr[j + 1], arr[j]
    values this stepFalsearr[j] > arr[j+1][1, 2, 4, 5, 8]arr1j2arr[j]4arr[j+1]

  19. loop ← break

    8        swapped = True9if not swapped:10    break
    values this stepbreakloopFalseswapped

  20. stdout ← [1, 2, 4, 5, 8]

    10        break11print(arr)
    values this step[1, 2, 4, 5, 8]stdout[1, 2, 4, 5, 8]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.