IB COMPUTER SCIENCE | B2.4.3 Bubble and Selection Sort

Lesson objective

Construct and trace bubble sort and selection sort, and evaluate their time complexity, auxiliary space, comparisons, swaps and behaviour on different datasets.

Learn

B2.4.3 | BUBBLE AND SELECTION SORT

01 | SAME DESTINATION, DIFFERENT JOURNEYS

Five quiz scores arrive in the order [5, 1, 4, 2, 3]. We want them in ascending order: [1, 2, 3, 4, 5]. A sorting algorithm must rearrange the existing items without losing any or adding extra ones.

Bubble sort repeatedly compares neighbours and swaps an out-of-order pair. Selection sort scans the remaining candidates for a minimum, then places that minimum at the next sorted position.

This SL/HL lesson constructs and traces both algorithms, then evaluates their comparisons, swaps, time complexity and extra memory. The implementation details matter, especially bubble sort’s early-stop rule.

02 | THE LANGUAGE OF A SORT

Term Meaning in this lesson
Ascending Smaller values before larger values; equals are allowed
Adjacent Next to each other, at indexes i and i + 1
Comparison A data-value order test, such as values[i] > values[i + 1]
Swap Exchange two stored items
Pass One outer-loop iteration through its current candidates
Sorted region Positions guaranteed to be in their final sorted locations

An index identifies a position; a value is stored at that position. A comparison can lead to a swap, but not every comparison requires one.

We count data-value comparisons separately from swaps. Loop-control tests and other instructions also take time, but are not included in these particular classroom counters.

03 | SWAP WITHOUT LOSING A VALUE

values = [5, 1]
temporary = values[0]
values[0] = values[1]
values[1] = temporary
print(values)

The output is [1, 5]. temporary preserves the old 5 before position 0 is overwritten. Writing values[0] = values[1] followed by values[1] = values[0] would duplicate 1 and lose 5.

Python can write the exchange as values[0], values[1] = values[1], values[0]. The right-hand values are obtained before the assignments overwrite the positions.

A swap exchanges two items. Counting one swap is different from counting every assignment involved in implementing it.

04 | BUBBLE SORT: MOVE A LARGE VALUE RIGHT

Start with [5, 1, 4, 2, 3]. Compare 5 and 1: they are in the wrong order, so swap them. The list becomes [1, 5, 4, 2, 3]. Now compare the new neighbours at indexes 1 and 2: 5 and 4.

Continue moving right, always comparing the current adjacent pair. The largest remaining value moves through the list until it reaches the rightmost active position.

Do not advance an imagined original pair after a swap. Read the list as it exists now: the moved value participates in the next adjacent comparison.

05 | ONE COMPLETE BUBBLE PASS

Pair indexes Values before comparison Action List after action
0, 1 5, 1 Swap [1, 5, 4, 2, 3]
1, 2 5, 4 Swap [1, 4, 5, 2, 3]
2, 3 5, 2 Swap [1, 4, 2, 5, 3]
3, 4 5, 3 Swap [1, 4, 2, 3, 5]

Pass 1 makes four comparisons and four swaps. The 5 is now guaranteed to be in its final position at index 4. The earlier part is not yet sorted: 4 still precedes 2 and 3.

A completed pass is not necessarily a completed sort. We repeat on the remaining active prefix.

06 | SHORTEN THE ACTIVE PART AFTER EACH PASS

Stage List after stage Guaranteed final suffix
Initial [5, 1, 4, 2, 3] None
Pass 1 [1, 4, 2, 3, 5] 5
Pass 2 [1, 2, 3, 4, 5] 4, 5
Pass 3: no swaps [1, 2, 3, 4, 5] All items; stop early

Pass 2 compares only the first four active items, making three comparisons. Pass 3 checks the first three active items, making two comparisons and no swaps. The optimized algorithm then stops. Total: 9 comparisons and 6 swaps.

The list happens to look sorted after pass 2, but the algorithm has not yet established that no more swaps are needed through its early-stop test. Trace the implemented checks rather than stopping when a human can see the answer.

07 | CONSTRUCT OPTIMIZED BUBBLE SORT

def bubble_sort(values):
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if values[index] > values[index + 1]:
                values[index], values[index + 1] = values[index + 1], values[index]
                swapped = True
        if not swapped:
            break

values = [5, 1, 4, 2, 3]
bubble_sort(values)
print(values)

The function modifies values in place and prints [1, 2, 3, 4, 5] through the caller. It has no explicit return, so Python returns None. Do not write values = bubble_sort(values) expecting a sorted list result from this interface.

end is the rightmost active index. range(end) supplies pair-start indexes 0 through end − 1, allowing safe access to index + 1 up to end.

For an empty or one-item list, the outer range is empty and no pair is accessed. Both inputs are already sorted.

08 | THE SWAPPED FLAG MUST RESET EACH PASS

swapped begins False inside the outer loop. Every actual swap sets it True. At the end of the pass, not swapped means that all checked neighbours were already in order, so the active region is sorted.

Together with the previously settled suffix, that gives a sorted whole list. The break exits the outer loop because it is placed after the inner loop, within the outer body.

If swapped is initialized only once before all passes, a swap in pass 1 can leave it True forever, preventing useful early stopping. If it is reset inside every comparison, it may forget an earlier swap and stop too soon.

09 | SELECTION SORT: FIND, THEN PLACE

For selection sort, the sorted region grows from the left. On each pass, find the smallest value in the unsorted suffix, then exchange it with the first unsorted position.

The algorithm does not immediately swap every smaller value it encounters. It remembers the index of the smallest candidate so far and waits until the scan finishes.

For [5, 1, 4, 2, 3], pass 1 finds the minimum 1 at index 1. One swap places it at index 0, producing [1, 5, 4, 2, 3].

10 | TRACE THE MINIMUM CANDIDATE

Scan action Candidate compared minimum_index after action Minimum value so far
Initialize at start = 0 No comparison 0 5
Inspect index 1 1 < 5 is True 1 1
Inspect index 2 4 < 1 is False 1 1
Inspect index 3 2 < 1 is False 1 1
Inspect index 4 3 < 1 is False 1 1

After four comparisons, minimum_index is 1. Only now does the algorithm swap indexes 0 and 1. Remember an index, not only the minimum value, because the swap needs the minimum’s location.

Updating minimum_index is not a swap: no stored list item moves during these comparisons.

11 | SELECTION PASSES GROW A SORTED PREFIX

Pass First unsorted index Chosen minimum List after final swap
1 0 1 [1, 5, 4, 2, 3]
2 1 2 [1, 2, 4, 5, 3]
3 2 3 [1, 2, 3, 5, 4]
4 3 4 [1, 2, 3, 4, 5]

After each pass, one more leftmost position is final. The last remaining item needs no separate selection pass because all other positions have been settled.

The comparison counts are 4, 3, 2 and 1, giving 10. This example makes four actual swaps. Other input orders may need fewer swaps, but the shown selection algorithm still performs the same comparisons for the same length.

12 | CONSTRUCT SELECTION SORT

def selection_sort(values):
    for start in range(len(values) - 1):
        minimum_index = start
        for index in range(start + 1, len(values)):
            if values[index] < values[minimum_index]:
                minimum_index = index
        if minimum_index != start:
            values[start], values[minimum_index] = values[minimum_index], values[start]

values = [5, 1, 4, 2, 3]
selection_sort(values)
print(values)

The function modifies the supplied list in place. start marks the next position to fill. minimum_index begins at start, and the inner loop visits the later candidates.

Only a smaller candidate changes minimum_index. After the scan, swap only when the minimum is at a different index. This avoids counting or performing an unnecessary self-swap.

Like bubble_sort, this function returns None implicitly. Its effect is the changed list, not a separate returned copy.

13 | ONE INTERACTIVE LAB, TWO ALGORITHMS

Enter up to 10 integers from −99 to 99. Each step shows one comparison, a placement swap or a pass conclusion. Snapshots show the list AFTER the described action, and the compared values before that action are stated in the explanation. Completed passes stay visible below.

Key: COMPARED = inspected this step; MIN = selection candidate; FINAL = settled region; ACTIVE = not yet guaranteed final. Text labels accompany the colours.

Try sorted, reverse-sorted, repeated and negative values. Predict whether the next action changes an item or only the remembered minimum index. Switch algorithms to compare the same original input; changes restart the trace.

14 | KEEP COMPARISONS AND SWAPS SEPARATE

For input [5, 1, 4, 2, 3] Bubble sort shown Selection sort shown
Data comparisons 9 10
Actual exchanges of different positions 6 4
First final region Largest value at right Smallest value at left
Can stop after a no-swap pass? Yes Not in this implementation

Bubble sort can exchange many adjacent pairs in one pass. Selection sort exchanges at most one pair per pass, but still scans the whole remaining suffix for its minimum.

Fewer swaps does not automatically mean fewer comparisons or a better asymptotic time class. Evaluate the operations that matter for the scenario.

15 | COUNT THE TRIANGULAR COMPARISONS

For n items, standard selection sort compares n − 1 candidates on the first pass, n − 2 on the next, then continues down to 1. The total is n(n − 1)/2.

For n = 5, the count is 4 + 3 + 2 + 1 = 10. Expanding the formula gives (n² − n)/2, whose dominant term is quadratic. Its standard time classification is O(n²).

Bubble sort without early stopping makes the same triangular number of comparisons with these shrinking bounds. Our optimized version can perform fewer comparisons when its no-swap test ends the process early.

16 | BUBBLE SORT: BEST, AVERAGE AND WORST

For an already sorted list of n ≥ 2 items, the first pass makes n − 1 comparisons and no swaps. The flag stops further passes, giving O(n) best-case time.

A reverse-sorted list of distinct values causes every comparison to swap and requires the full triangular schedule: O(n²) worst-case time and n(n − 1)/2 swaps.

Under the usual uniformly random permutation model for distinct items, average-case time is also O(n²). State the model rather than treating “average” as an unspecified convenient input.

Without the early-stop flag, the shrinking-bound bubble sort has O(n²) time even on sorted input. A complexity statement belongs to a particular algorithm version.

17 | SELECTION SORT: ORDER DOES NOT REMOVE THE SCAN

The shown selection sort always checks the remaining suffix, even if it is already sorted. Its n(n − 1)/2 comparisons give O(n²) best-, average- and worst-case time under constant-time comparisons.

The implementation avoids self-swaps, so a sorted list makes zero actual swaps. An arbitrary input makes at most n − 1 swaps. The exact number depends on input order.

Therefore selection sort can be attractive relative to bubble sort when writes or exchanges are expensive, but both still have quadratic worst-case comparison work and limited scalability.

18 | SPACE: IN PLACE DOES NOT MEAN NO MEMORY

Both shown functions rearrange the existing list using a fixed number of indexes, a flag or a minimum index, and constant-sized swap storage. Their auxiliary space is O(1) in the fixed-size-item model.

The input list itself occupies O(n) storage, but auxiliary space convention excludes that existing input. If a wrapper first copies the list to preserve it, that copy needs O(n) extra space.

The teaching visualizer stores many snapshots to explain the process. Its memory use is not the auxiliary space of the compact sorting functions. Analyse the actual program and the chosen boundary.

19 | EQUAL VALUES AND STABILITY

A stable sort preserves the original relative order of records with equal sort keys. Imagine two students with the same mark: a stable mark sort retains their previous order relative to each other.

Our bubble sort swaps only when the left key is strictly greater than the right. Equal-key neighbours never cross, so it is stable. Replacing > with >= can change that property and also trigger unnecessary swaps.

Standard swap-based selection sort is not stable. For records [2A, 2B, 1], the first pass swaps 1 with 2A, producing [1, 2B, 2A]. The equal-key records A and B have reversed order. A and B label records, not different numerical keys.

20 | JAVA: COMPLETE SORTING METHODS

import java.util.Arrays;

public class SortExample {
    static void bubbleSort(int[] values) {
        for (int end = values.length - 1; end > 0; end--) {
            boolean swapped = false;
            for (int index = 0; index < end; index++) {
                if (values[index] > values[index + 1]) {
                    int temporary = values[index];
                    values[index] = values[index + 1];
                    values[index + 1] = temporary;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }

    static void selectionSort(int[] values) {
        for (int start = 0; start < values.length - 1; start++) {
            int minimumIndex = start;
            for (int index = start + 1; index < values.length; index++) {
                if (values[index] < values[minimumIndex]) {
                    minimumIndex = index;
                }
            }
            if (minimumIndex != start) {
                int temporary = values[start];
                values[start] = values[minimumIndex];
                values[minimumIndex] = temporary;
            }
        }
    }

    public static void main(String[] args) {
        int[] first = {5, 1, 4, 2, 3};
        int[] second = {5, 1, 4, 2, 3};
        bubbleSort(first);
        selectionSort(second);
        System.out.println(Arrays.toString(first));
        System.out.println(Arrays.toString(second));
    }
}

Both outputs are [1, 2, 3, 4, 5]. The void methods mutate their supplied arrays. Separate initial arrays ensure the second algorithm does not receive the already sorted result of the first.

The loop boundaries and strict comparison rules match the Python versions. Trace indexes separately from values in either language.

21 | SORT RECORDS WITHOUT BREAKING THEIR LINKS

def bubble_sort_by_mark(records):
    for end in range(len(records) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if records[index]["mark"] > records[index + 1]["mark"]:
                records[index], records[index + 1] = records[index + 1], records[index]
                swapped = True
        if not swapped:
            break

records = [{"name": "Ada", "mark": 7},
           {"name": "Lin", "mark": 5},
           {"name": "Sam", "mark": 7}]
bubble_sort_by_mark(records)
print([record["name"] for record in records])

The output is ['Lin', 'Ada', 'Sam']. Compare marks, but exchange the whole records so names remain attached to the correct marks. Ada stays before Sam because their equal marks never swap.

Sorting only the mark fields while leaving names in their old positions would corrupt the associations. Define the key and move the complete items.

22 | DESCENDING ORDER AND THE COMPARISON RULE

To adapt bubble sort for descending order, swap neighbours when the left value is less than the right. This moves larger values toward the front and settles the smallest remaining value at the right on each left-to-right pass.

To adapt selection sort for descending order, remember the maximum in the unsorted suffix and place it at the next prefix position. Change the candidate test from < to >.

The broad time and auxiliary-space classes remain the same under these changes. The values chosen and the meaning of the final region change, so update trace explanations as well as the operator.

23 | CONSTRUCT TESTS THAT CHECK MORE THAN ORDER

Test What to check
Empty / one item No invalid neighbour access; unchanged result
Already sorted Bubble stops after one non-swapping pass for n ≥ 2
Reverse sorted Many swaps; correct final order
Duplicates Values preserved; required stability respected
Negative and zero values Numerical comparisons handle signs
Several passes needed Correct shrinking bounds and final regions

Check that the final sequence is ordered and that it contains exactly the same items with the same multiplicities. An algorithm that loses a value can produce a sorted-looking but incorrect result.

Also check the interface: these functions mutate the original and return None. A copy-returning version has a different contract and different extra-space cost.

24 | INVARIANTS AND TERMINATION

After each completed bubble pass, the largest value from that active prefix is settled at its rightmost index. The settled suffix grows and can be excluded from later comparisons.

After each completed selection pass, the prefix contains the required smallest items in their final positions. The remaining minimum is moved into the next position, preserving that property.

The finite loop ranges shrink the active region, guaranteeing termination. Bubble sort may terminate sooner through its flag. A no-swap selection pass does not prove the unsorted suffix is ordered: [1, 3, 2] needs no swap at start 0 but still requires another pass.

25 | EVALUATE THE CHOICE FOR A SCENARIO

For an already sorted or suitably favourable nearly sorted dataset, optimized bubble sort can benefit from early stopping. However, “nearly sorted” does not guarantee linear time: one small item near the end may move left only one position per pass.

Selection sort performs a predictable triangular scan and at most n − 1 exchanges, which can be useful when exchanges are costly. It cannot exploit sorted input to reduce its comparison count in this version.

Both are simple, use O(1) auxiliary space and can suit small educational examples. Both have O(n²) worst-case time, so a suitable O(n log n) sorting algorithm is usually a better scalability choice for large general datasets.

An evaluation should connect the data order, size, stability requirement, comparison/write costs and memory constraints to a justified conclusion, rather than name a universal winner.

26 | TRACE, CONSTRUCT AND EVALUATE CLEARLY

For Trace, follow the supplied version exactly: show each comparison or requested pass, mark the current state and record swaps only when they occur. For selection sort, distinguish a new candidate minimum from an actual placement swap.

For Construct, supply complete initialization, safe loop bounds, correct comparison, swap logic and the promised mutation or return behaviour. Place the bubble flag correctly and selection’s final swap after its scan.

For Evaluate, state time and auxiliary-space complexity for the version and case, then weigh the advantages against the scenario. Explain why a feature matters using because, therefore or resulting in.

MATCH THE SORTING IDEA

Terminology

Terminology

Sorting

Rearranging items into a defined order without changing their contents or multiplicities.

Ascending order

Smaller keys before larger keys; equals allowed.

Descending order

Larger keys before smaller keys; equals allowed.

Sort key

The field or value used to determine ordering.

Adjacent items

Items next to each other at indexes i and i + 1.

Comparison

An order test between data values.

Swap

An exchange of two stored items.

Pass

One outer-loop iteration over its current candidates.

Bubble sort

Repeatedly compare neighbours and swap out-of-order pairs.

Selection sort

Select the remaining minimum and place it at the next sorted position.

Active region

Items not yet guaranteed to be in their final positions.

Sorted suffix

A settled region at the end, grown by the shown bubble sort.

Sorted prefix

A settled region at the beginning, grown by selection sort.

end

The rightmost active index in the shown bubble sort.

start

The next prefix position to fill in selection sort.

minimum_index

The index of the smallest selection candidate found so far.

swapped flag

A Boolean recording whether a bubble pass performed any swap.

Early stopping

Ending before all scheduled passes when correctness is established.

In-place sorting

Rearranging the existing collection with limited extra working storage.

Auxiliary space

Extra working memory beyond the existing input under the stated convention.

Stable sorting

Preserving relative order among items with equal keys.

Unstable sorting

Not guaranteeing preservation of equal-key relative order.

Self-swap

Exchanging a position with itself, avoided in the shown selection sort.

Invariant

A property preserved as an algorithm proceeds.

Best case

The least work among inputs of a given size.

Worst case

The greatest work among inputs of a given size.

Average case

Expected work under a stated input distribution.

Quadratic time

Growth dominated by n² in the standard model.

Mutation

Changing the existing collection rather than returning a separate one.

Scalability

How effectively an approach handles growing input sizes.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe the shown bubble sort?
2. Which describe selection sort?
3. Which are correct for the first bubble pass on [5, 1, 4, 2, 3]?
4. Where should the bubble swapped flag be handled?
5. Which count expressions describe the shown selection sort?
6. Which complexity statements are correct?
7. Which statements about auxiliary space are correct?
8. Which stability statements are correct?
9. Which tests are useful?
10. Which support a justified evaluation?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Trace the first bubble pass on [4, 1, 3, 2].

2. Trace the first selection pass on [4, 1, 3, 2].

3. Construct an ascending bubble sort with early stopping.

4. Construct an ascending selection sort.

5. Explain why the bubble flag must reset before each pass.

6. Calculate selection-sort comparisons for 8 items.

7. Compare how the algorithms build their final sorted regions.

8. Explain the best-case time of the optimized bubble sort for sorted input.

9. Explain why selection sort remains quadratic on sorted input.

10. Distinguish in-place sorting from stable sorting.

11. Evaluate selection sort when exchanges are much more expensive than comparisons.

12. Explain why an apparently ordered output is not enough to prove sorting correctness.

CONSTRUCT AND EVALUATE | DESCENDING SELECTION

Construct a descending selection sort for a list of integer scores. State the final region after each pass. Then evaluate its time and auxiliary-space complexity and explain whether already descending input avoids the suffix scans.

Reveal an approach
def selection_sort_descending(values):
    for start in range(len(values) - 1):
        maximum_index = start
        for index in range(start + 1, len(values)):
            if values[index] > values[maximum_index]:
                maximum_index = index
        if maximum_index != start:
            values[start], values[maximum_index] = values[maximum_index], values[start]

The prefix contains the largest items in final descending order. The suffix scans still make n(n − 1)/2 comparisons, including on already descending input, giving O(n²) time. Auxiliary space is O(1); actual swaps are at most n − 1 and can be zero.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.4.3 Bubble and Selection Sort is coming soon. Complete the matching task and written questions in your exercise book.