Bubble Sort & Selection Sort

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 1 Time to complete: ~20 minutes

What "Sorting" Means Here
Bubble Sort
Bubble Sort — Complexity
Selection Sort
Selection Sort — Complexity
Stability, Explained
Why Learn These at All?
Summary & Next Steps

1. What "Sorting" Means Here

All the algorithms in this module take an array and rearrange it into ascending order using comparisons between elements. They differ in how they decide what to compare and swap, which changes their time complexity, space complexity, and stability (Section 6).

2. Bubble Sort

Repeatedly step through the array, swapping adjacent elements that are out of order. Each full pass "bubbles" the largest remaining element to its correct position at the end.

def bubble_sort(items):
    n = len(items)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:          # already sorted — stop early
            break
    return items

Pass 1 on [5, 2, 8, 1]:
  compare 5,2 → swap → [2, 5, 8, 1]
  compare 5,8 → no swap
  compare 8,1 → swap → [2, 5, 1, 8]
  (8 is now in its final position)

3. Bubble Sort — Complexity

Case	Complexity	Why
Best (already sorted)	`O(n)`	The `swapped` flag lets it exit after one pass
Average	`O(n²)`	Roughly half of all pairs need swapping
Worst (reverse sorted)	`O(n²)`	Every adjacent pair is out of order, every pass

Space: O(1) — sorts in place, no extra structures.

4. Selection Sort

Repeatedly find the minimum of the unsorted remainder and swap it into place at the front.

def selection_sort(items):
    n = len(items)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if items[j] < items[min_index]:
                min_index = j
        items[i], items[min_index] = items[min_index], items[i]
    return items

Pass 1 on [5, 2, 8, 1]:
  find minimum of [5, 2, 8, 1] → 1 at index 3
  swap with index 0 → [1, 2, 8, 5]
Pass 2 on the remainder [2, 8, 5] (index 1 onward):
  find minimum → 2 is already at index 1, no swap

5. Selection Sort — Complexity

Case	Complexity	Why
Best	`O(n²)`	Still scans the entire unsorted remainder every pass, regardless of order
Average	`O(n²)`	Same reason
Worst	`O(n²)`	Same reason

Selection sort has no best-case speedup — unlike bubble sort's early-exit, it always scans the full remainder to find the minimum, so its performance doesn't improve on nearly-sorted input. Its one advantage: it performs at most n swaps total (one per pass), which matters if writes are much more expensive than comparisons.

Space: O(1) — also sorts in place.

6. Stability, Explained

A sort is stable if elements that compare as equal keep their original relative order. This matters when sorting records by one field but wanting ties broken by original order (e.g., sorting students by grade, but two students with the same grade should stay in their original list order):

# Example: sorting (name, grade) pairs by grade
students = [("Amy", 90), ("Ben", 85), ("Cid", 90)]
# A stable sort keeps Amy before Cid (both have grade 90) because
# Amy appeared first in the original list.

Bubble sort is stable — it only swaps adjacent elements when one is strictly greater, so equal elements never swap past each other. Selection sort is NOT stable — swapping the minimum into place can jump it past an equal element, disrupting original order. This distinction becomes concretely important for merge sort (Chapter 4, stable) versus quick sort (Chapter 5, not stable by default).

7. Why Learn These at All?

Neither algorithm is used in production sorting (Python's built-in sorted() uses Timsort, covered in Chapter 6) — but both are worth internalizing because:

They build the vocabulary (passes, comparisons, swaps, in-place, stability) used to analyze every sort that follows.
Their simplicity makes the O(n²) cost visible and intuitive before tackling O(n log n) algorithms whose mechanics are less obvious.
Interviewers occasionally ask you to implement one from memory as a warm-up question.

8. Summary & Next Steps

Key Takeaways

Bubble sort repeatedly swaps adjacent out-of-order elements; it's O(n²) average/worst but O(n) best-case with an early-exit flag.
Selection sort repeatedly places the minimum of the unsorted remainder; it's always O(n²), with no best-case speedup, but performs the fewest swaps.
Stability means equal elements keep their relative order — bubble sort is stable, selection sort is not.
Both are O(1) space (in-place) and mainly serve as a foundation for understanding faster algorithms.

Concept Check

Why does bubble sort achieve O(n) on already-sorted input, but selection sort doesn't?
Why is selection sort not stable, even though bubble sort is?
When might selection sort's "fewest swaps" property actually matter in practice?

Next Chapter

→ Chapter 3: Insertion Sort

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index