B2.4 · Sorting · Current focus

Bubble sort & selection sort

Follow how each pass moves values towards their final positions, then implement and compare two sorts.

55 minutes

For this lesson

Open student handout (PDF) Class activities ↓ Open Python playground → Homework · due 12 Oct 2026 Homework · due 7 Oct 2026

Animations: Bubble sort Selection sort Insertion sort · extension

Python · step by step

Bubble sort

Example

Watch the list change while following the actual Python execution.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1def bubble_sort(items):2    for end in range(len(items) - 1, 0, -1):3        swapped = False4        for j in range(end):5            if items[j] > items[j + 1]:6                items[j], items[j + 1] = items[j + 1], items[j]7                swapped = True8        if not swapped:9            break10    return items

Speed

Execution progress

The suffix beyond end is sorted. An early-exit flag gives O(n) best-case time; average and worst cases are O(n²). This in-place implementation uses O(1) auxiliary space.

Python · step by step

Selection sort

Example

Watch the list change while following the actual Python execution.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1def selection_sort(items):2    for start in range(len(items) - 1):3        smallest = start4        for j in range(start + 1, len(items)):5            if items[j] < items[smallest]:6                smallest = j7        items[start], items[smallest] = items[smallest], items[start]8    return items

Speed

Execution progress

Find the smallest remaining item, then swap it into place. The prefix before start is sorted. Comparisons take O(n²) even for sorted input. Auxiliary space is O(1).

By the end of this lesson

Trace bubble and selection sort pass by pass.
Distinguish comparisons from swaps.
Test empty, sorted, reversed and duplicate-containing lists.

Work through the lesson

01 · 5 minutes

Retrieve

Explain why sorted data makes binary search possible. Predict whether sorting first is worthwhile for a single small search.

02 · 15 minutes

Trace bubble sort

Use [7, 2, 5, 1]. Compare adjacent values and swap when necessary. Record the list after each pass and explain what is now in its final position.

03 · 15 minutes

Trace selection sort

Use the same starting list. Find the smallest remaining value and swap it into the next position. Record comparisons and swaps separately.

04 · 15 minutes

Implement and test

Implement one sort without sorted() or list.sort(). Test [], [4], an already sorted list, a reversed list and repeated values.

05 · 5 minutes

Compare

Explain a difference between the two algorithms using your traces as evidence.

Space complexity: what are we counting?

Auxiliary space means the extra working memory an algorithm needs, beyond the input it has already been given. Think of it as scratch space: counters, a running total, new lists and the memory used by active function calls.

In the summation example on textbook page 361, numbers is the supplied input list. The algorithm keeps a running total in sum and uses a fixed number of extra variables. Whether the list has 10 items or 10,000, it still needs only those few variables: O(1) auxiliary space.

The textbook’s O(n) space statement counts the input list too: storing n items takes memory that grows with n. That is total space, including the input. Both descriptions can be correct; they count different things.

A larger value in sum does not mean we keep more totals. For this classroom analysis, we treat each number as one fixed-size value. Creating a new copy of all n items, or saving every intermediate total, would instead need O(n) auxiliary space.

When explaining an answer, state your convention: “O(1) auxiliary space; O(n) total space including the input list.” Time is a separate question: visiting every item still takes O(n) time.

Before you leave

Exit question

Which work is repeated on every pass, and how does that change as the list grows?

Homework for this topic

Due 12 Oct 2026 · Questions 3–7 · Assigned

Holiday homework: finish questions 3–7

Finish the unfinished work in questions 3–7 of the B2.4 Algorithms student handout over the holiday. Questions 1 and 2 are already complete.

Due 7 Oct 2026 · Q9(a) + Q10 (bubble sort only) · Assigned

Bubble sort: Q9(a) and the bubble-sort part of Q10

Complete Q9(a) on printed page 11 and only the bubble-sort part of Q10 on printed page 12 of the B2.4 Algorithms student handout. Due 7 October 2026.