Construct and trace algorithms to implement bubble sort and selection sort, evaluating their time and space complexities

Bubble Sort

How it works: Repeatedly steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element “bubbles up” to its correct position.

def bubble_sort(arr):
    n = len(arr)

    for i in range(n - 1):          # Number of passes
        swapped = False

        for j in range(n - 1 - i):  # Compare adjacent pairs
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Swap
                swapped = True

        if not swapped:             # Already sorted — early exit
            break

    return arr

Trace example:

arr = [5, 3, 8, 1, 2]

Pass 1: [5, 3, 8, 1, 2]
          3 < 5 → swap  → [3, 5, 8, 1, 2]
          8 > 5          → [3, 5, 8, 1, 2]
          1 < 8  → swap  → [3, 5, 1, 8, 2]
          2 < 8  → swap  → [3, 5, 1, 2, 8]
        Largest (8) now at the end ✅

Pass 2: [3, 5, 1, 2, 8]
          3 < 5           → [3, 5, 1, 2, 8]
          1 < 5  → swap  → [3, 1, 5, 2, 8]
          2 < 5  → swap  → [3, 1, 2, 5, 8]
        Second largest (5) in position ✅

Pass 3: [3, 1, 2, 5, 8]
          1 < 3  → swap  → [1, 3, 2, 5, 8]
          2 < 3  → swap  → [1, 2, 3, 5, 8]

Pass 4: [1, 2, 3, 5, 8]  → Sorted ✅

Complexity:

	Value	Reason
Best case	O(n)	Already sorted; one pass with no swaps
Worst case	O(n²)	Reverse sorted; every pair must be swapped
Average case	O(n²)	Random order
Space	O(1)	In-place sorting, no extra array needed

---

Selection Sort

How it works: Divides the list into a sorted region (left) and an unsorted region (right). Repeatedly finds the minimum from the unsorted region and swaps it with the first unsorted element, growing the sorted region by one each iteration.

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):              # Position to fill
        min_idx = i

        for j in range(i + 1, n):      # Scan unsorted region
            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # Swap

    return arr

Trace example:

arr = [64, 25, 12, 22, 11]

i=0: Scan [64, 25, 12, 22, 11] → minimum is 11
      Swap arr[0] and arr[4]
      [11, 25, 12, 22, 64]     ✅ 11 in position 0

i=1: Scan [25, 12, 22, 64] → minimum is 12
      Swap arr[1] and arr[2]
      [11, 12, 25, 22, 64]    ✅ 12 in position 1

i=2: Scan [25, 22, 64] → minimum is 22
      Swap arr[2] and arr[3]
      [11, 12, 22, 25, 64]    ✅ 22 in position 2

i=3: Scan [25, 64] → minimum is 25
      Swap arr[3] and arr[3] (no change)
      [11, 12, 22, 25, 64]    ✅ 25 in position 3

Result: [11, 12, 22, 25, 64]  ✅ Sorted

Complexity:

	Value	Reason
Best case	O(n²)	Still must scan all remaining elements
Worst case	O(n²)	Same as average — always full scan
Average case	O(n²)	Nested loops; (n-1)+(n-2)+…+1 = n(n-1)/2
Space	O(1)	In-place sorting

---

Bubble Sort vs Selection Sort

Property	Bubble Sort	Selection Sort
Stability	✅ Stable — equal elements never swap	❌ Unstable — equal elements may swap
Best case	O(n) — with early exit flag	O(n²)
Worst case	O(n²)	O(n²)
Average case	O(n²)	O(n²)
Swaps	Many (up to n² in worst case)	At most n−1 swaps — fewer writes
Best for	Nearly sorted data	Situations where write cost is high (e.g., flash memory)