← WA Computer Science ATAR Unit 1

Comparing the number of comparisons in bubble and selection sort

Bubble and selection sort both make about n squared comparisons, so doubling n quadruples the work, but selection sort makes far fewer swaps.

Part of: WA Computer Science ATAR Year 11 — Standard Algorithms — Module 36

Understanding Comparing the number of comparisons in bubble and selection sort in WA Computer Science ATAR Unit 1

What it does: If a full pass makes no swaps, swapped stays FALSE and the loop ends early, so a sorted list needs only one pass. Selection sort swaps once, after finding the minimum. Bubble sort can swap on every comparison, so it makes far more swaps. Work grows with n squared. Doubling n gives 2 x 2 = 4 times as many comparisons. n is 10 times bigger, so n squared is 10 x 10 = 100 times bigger. Their comparison counts are of the same order, n squared. The big difference is the number of swaps. For n = 20, n(n-1)/2 = 190, which is about 4 times 45. Doubling only applies to a linear algorithm.

Common mistakes: Selection sort compares a[min] with the elements after position i, so the inner loop must start at i + 1. Starting at i adds a pointless comparison of an item with itself on every pass and gives the wrong comparison count. Each time bubble sort compares a[j] with a[j+1], the counter must go up by 1, so it should be comps ← comps + 1. Subtracting would make the total shrink instead of reaching about n squared.

Class: _____________________  ·  Name: _____________________  ·  Date: _________

Free printable worksheet with full answer key — or add this module to a class and your students practise it interactively.

🖨 Print worksheet + answer key Add Comparing the number of comparisons in bubble and selection sort to a class →

This module's key terms are also in a printable crossword (Modules 315–470) and word search (Modules 100–470).

Take this worksheet further — free with Cloodit

Each concept is reinforced from every angle — learned, then applied, then tested.

Learning
Duo
A list has 10 items. About how many comparisons does selection sort make?
10, one comparison per item45 (10 x 9 / 2), which is about n squared
Matches
n goes from 10 to 20, so comparisons go from 45 to 90
↓
Comparisons do not just double. They grow with n squared, so doubling n gives about four times the comparisons (45 to 190).
Applying
Meanings
Term
O(n^2)
Meaning
Bubble and selection sort both make about n squared comparisons, so doubling n quadruples the work, but selection sort makes far fewer swaps.
Practice
comparisons ← 0
Testing
Gaps
comparisons ← n * (n - 1) /
Check Answer
Spots
2FOR i ← 1 TO n - 1
3 FOR j ← i TO n

Cloodit turns curriculum-aligned coding content into journeys students work through one biome at a time.

The 'Narwhal' badge — Unicorn Coder, one of Cloodit's 106 collectible badges
Students earn collectable badges

Over 100 of them, across seven natural biomes.

Study Buddy
Students build a real study resource

Turns their work into revision material ready for Flash Cards and Exam study.

Diamond Dash — one of Cloodit's live, competitive Sprint games
Students lock in with Sprints

Live, competitive practice for the start of the lesson or a teacher-led lesson finisher.

A Cloodit certificate of achievement, ready to personalise and print
Custom printable certificates

Honour your top performers, or encourage a student who's trying hard — ready to print in seconds.

Add to class →

Quick Questions

1. A list has 10 items. About how many comparisons does selection sort make?
A. 45 (10 x 9 / 2), which is about n squared ✓
B. 10, one comparison per item
Selection sort compares every remaining item on each pass: 9 + 8 + ... + 1 = 45. That grows like n squared, not n.
2. The list size doubles from 100 to 200 items. How does the number of comparisons change in bubble or selection sort?
A. It roughly doubles
B. It roughly quadruples ✓
Work grows with n squared. Doubling n gives 2 x 2 = 4 times as many comparisons.
3. Which sort makes far fewer swaps on a random list?
A. Selection sort, at most n - 1 swaps ✓
B. Bubble sort, at most n - 1 swaps
Selection sort swaps once per pass, after finding the smallest item. Bubble sort may swap on almost every comparison, up to about n squared / 2 times.
4. Bubble sort uses a swapped flag and the list is already sorted. How many comparisons does it make?
A. n - 1, because one pass finds no swaps and it stops ✓
B. About n squared, because it always does every pass
If a full pass makes no swaps, the flag stays False and the loop ends. That is the best case for bubble sort.
5. Selection sort is given an already sorted list. What happens?
A. It stops early after one pass
B. It still makes about n squared comparisons ✓
Selection sort has no swapped flag. It must still scan the rest of the list on every pass to be sure it has the smallest item.

Match the Pairs

n * (n - 1) / 2 → The number of comparisons selection sort always makes on n items. For n = 10 that is 45 comparisons.
n: 10 -> 20 → Doubling the list size makes about four times as many comparisons: 45 becomes 190.
Bubble sort best case: on an already sorted list, the swapped flag lets it stop after one pass of n - 1 comparisons → UNTIL swapped = FALSE
Selection sort makes at most one swap per pass, so at most n - 1 swaps in total → SWAP A[i], A[min] after the inner FOR loop
n goes from 10 to 20, so comparisons go from 45 to 90 → Comparisons do not just double. They grow with n squared, so doubling n gives about four times the comparisons (45 to 190).
Selection sort comparisons ≈ n → Selection sort still makes about n squared / 2 comparisons. Its advantage over bubble sort is fewer swaps, not fewer comparisons.

Key Term

O(n^2)
Bubble and selection sort both make about n squared comparisons, so doubling n quadruples the work, but selection sort makes far fewer swaps.

Fill in the Blanks

1. comparisons ← n * (n - 1) / 2
Hint: Type the number you divide by so each pair of items is counted only once.
2. newWork ← 4 * oldWork // when n is doubled
Hint: Type the number the work is multiplied by when n doubles.
3. IF A[j] > A[j + 1] THEN SWAP A[j], A[j + 1] swapped ← TRUE
Hint: Type the Boolean value that records a swap happened in this pass.
4. swapped ← TRUE WHILE swapped = TRUE swapped ← FALSE
Hint: Type the name of the flag variable that decides if another pass is needed.
5. FOR i FROM 1 TO n - 1 min ← index of smallest in A[i..n] SWAP A[i], A[min]
Hint: Type the keyword that exchanges two values, done only once per pass in selection sort.

Spot the Error

Question 1
A comps ← 0
B FOR i ← 1 TO n - 1
C FOR j ← i TO n
D comps ← comps + 1
Line C — Selection sort compares a[min] with the elements after position i, so the inner loop must start at i + 1. Starting at i adds a pointless comparison of an item with itself on every pass and gives the wrong comparison count.
Question 2
A comps ← 0
B FOR pass ← 1 TO n - 1
C FOR j ← 1 TO n - pass
D comps ← comps - 1
E IF a[j] > a[j+1] THEN
Line D — Each time bubble sort compares a[j] with a[j+1], the counter must go up by 1, so it should be comps ← comps + 1. Subtracting would make the total shrink instead of reaching about n squared.
Question 3
A n ← 10
B before ← n * n
C n ← n + 2
D after ← n * n
E PRINT after / before
Line C — Doubling n means multiplying it by 2, so the line should be n ← n * 2. Then after is 400 and before is 100, so the program prints 4 (doubling n quadruples the work). Adding 2 would not double n.
Question 4
A n ← 100
B selSwaps ← n - 1
C bubComps ← n * (n - 1) / 2
D selComps ← n - 1
E PRINT selSwaps, selComps
Line D — Selection sort still compares about n squared / 2 items, the same as bubble sort. It is only its swaps that are limited to n - 1. The line should be selComps ← n * (n - 1) / 2.
Question 5
A swapped ← TRUE
B WHILE swapped = FALSE
C swapped ← FALSE
D FOR j ← 1 TO n - 1
E IF a[j] > a[j+1] THEN
F SWAP; swapped ← TRUE
Line B — The loop must keep running while swaps are still being made, so the condition is WHILE swapped = TRUE. With = FALSE the loop would never start because swapped begins as TRUE.

Student with a class code? Join your class →