A. Programming Concepts and Skills · Arrays and SubprogramsSorting Algorithms: Selection Sort and Bubble Sort
A2.3 A1.6 A3.2 A4.4About 75 minutes
Learning goals- I can swap two elements of a list safely.
- I can explain, trace and write selection sort and bubble sort using nested loops.
- I can count the comparisons a sort makes and explain why sorting a long list takes much longer.
- I can use Python's sorted() and list.sort() and explain how they differ.
Words to know
sort
To arrange the elements of a list in order, e.g. smallest to largest (ascending) or largest to smallest (descending).
swap
To exchange the values of two elements.
pass
One complete run of a sort's inner loop through the unsorted part of the list.
selection sort
A sort that repeatedly selects the smallest remaining element and swaps it into the next position.
bubble sort
A sort that repeatedly compares neighbouring elements and swaps them if they are out of order, so large values 'bubble' to the end.
nested loop
A loop inside another loop. The inner loop runs completely for every pass of the outer loop.
Why sort?
A hockey league's standings, a class list in alphabetical order, the top 10 scores in a game: all sorted lists. Sorted data is easier for people to read, and it lets programs find things faster (you will add and remove elements in a sorted list in Inserting, Deleting and Parallel Lists). Python can sort with one call, but every computer science student learns how sorting actually works, because sorting algorithms are the classic example of nested loops working on an array. This lesson builds two of them.
Step 1: swapping two elements
To swap a[0] and a[1], you cannot just write a[0] = a[1] then a[1] = a[0]: the first line destroys the old a[0]. Save it in a temporary variable first. Python also has a one-line swap that does the same thing.
a = [5, 9]
temp = a[0]
a[0] = a[1]
a[1] = temp
print(a)
a[0], a[1] = a[1], a[0] # Python's one-line swap
print(a)
Output: [9, 5] then [5, 9] (swapped back).
Selection sort
Idea: find the smallest element and put it first. Then find the smallest of the rest and put it second. Keep going.
- For each position
start from 0 to n − 2: - Find the index of the smallest element from
start to the end (the minimum algorithm from Highest, Lowest and Linear Search). - Swap it into position
start. Now positions 0 to start are sorted and never change again.
The last element needs no pass of its own: when everything else is in place, it must be the largest.
def selection_sort(values):
"""Sort values into increasing order, in place."""
n = len(values)
for start in range(n - 1):
smallest = start
for i in range(start + 1, n):
if values[i] < values[smallest]:
smallest = i
values[start], values[smallest] = values[smallest], values[start]
data = [29, 10, 14, 37, 13]
selection_sort(data)
print(data)
Output: [10, 13, 14, 29, 37]. The outer loop chooses the position to fill; the inner loop searches the unsorted part.
Bubble sort
Idea: walk along the list comparing neighbours. Whenever a pair is in the wrong order, swap it. After one pass the largest element has "bubbled" to the end. Repeat on the shorter unsorted part.
A useful improvement: if a whole pass makes no swaps, the list is already sorted, so stop early.
def bubble_sort(values):
"""Sort values into increasing order, in place."""
n = len(values)
for p in range(n - 1):
swapped = False
for i in range(n - 1 - p):
if values[i] > values[i + 1]:
values[i], values[i + 1] = values[i + 1], values[i]
swapped = True
if not swapped:
break # no swaps: already sorted
times = [8, 3, 6, 1]
bubble_sort(times)
print(times)
Output: [1, 3, 6, 8]. The inner loop stops at n - 1 - p because the last p elements are already in place, and i + 1 must stay in bounds.
Worked exampleExample 1: Trace bubble sort completely
Trace bubble sort on [8, 3, 6, 1]. Show the list after each pass and count the comparisons.
- Pass 1 (i = 0, 1, 2; 3 comparisons): swap 8/3, swap 8/6, swap 8/1 → [3, 6, 1, 8].
- Pass 2 (i = 0, 1; 2 comparisons): 3 < 6 no swap; 6 > 1 swap → [3, 1, 6, 8].
- Pass 3 (i = 0; 1 comparison): 3 > 1 swap → [1, 3, 6, 8].
- Total comparisons: 3 + 2 + 1 = 6. For n elements the worst case is (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2. Selection sort always makes this many comparisons.
Passes give [3, 6, 1, 8], [3, 1, 6, 8], [1, 3, 6, 8]; 6 comparisons.
How long does sorting take?
n(n − 1)/2 grows quickly. For 10 elements it is 45 comparisons; for 1000 it is 499 500; for 1 000 000 it is about 500 billion. Doubling the list roughly quadruples the work. That is why these simple sorts are fine for class lists but not for huge data. Python's built-in sort uses a much faster algorithm (called Timsort), and Grade 12 computer science (ICS4U) goes on to faster sorting methods.
| n (elements) | comparisons n(n − 1)/2 |
|---|
| 5 | 10 |
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Built-in sorting
sorted(a) returns a new sorted list and leaves a unchanged.a.sort() sorts in place and returns None.- Both accept
reverse=True for descending order. Strings sort alphabetically (by character code, so all capital letters come before lower-case ones).
towns = ["Sudbury", "Barrie", "Kenora", "Ajax"]
print(sorted(towns))
print(towns)
towns.sort(reverse=True)
print(towns)
print(sorted([3, 1, 2]) == [1, 2, 3])
Output: ['Ajax', 'Barrie', 'Kenora', 'Sudbury'], then the unchanged original ['Sudbury', 'Barrie', 'Kenora', 'Ajax'], then ['Sudbury', 'Kenora', 'Barrie', 'Ajax'], then True.
Worked exampleExample 2: Sorting in descending order
Change selection_sort so it puts the largest first (descending order), e.g. for a top-scores list.
- Only the comparison changes: the inner loop should look for the largest remaining element.
- Replace
if values[i] < values[smallest]: with if values[i] > values[largest]: (renaming smallest to largest so the code still reads correctly). - Test:
[29, 10, 14, 37, 13] should become [37, 29, 14, 13, 10].
One comparison flips the order; good variable names keep the code honest.
Just for funSome sorting algorithms really have silly names: "bogosort" shuffles the list randomly and checks whether it happens to be sorted, over and over. For a deck of 52 cards, you would expect to wait far longer than the age of the universe.
Hands-on activitySort a hand of cards
You need: a deck of playing cards (use only the cards Ace to 10 of one suit, Ace = 1), a table, and a partner.
- Shuffle the 10 cards and deal them face up in a row.
- Selection sort: scan the row for the smallest card and swap it with the first card. Then scan from the second card, and so on. Your partner counts every comparison (each time you compare two cards).
- Shuffle and deal again. Bubble sort: compare cards 1 and 2, swap if needed, then 2 and 3, and so on to the end. Repeat passes until a pass has no swaps. Count comparisons again.
- Compare your counts with n(n − 1)/2 = 45. Did bubble sort stop early?
- Code both sorts in Python and add a counter variable to check your counts.
What to look for: the student explains why the left part stays sorted in selection sort, and why the right part stays sorted in bubble sort.
Your turn
1Why does a[0] = a[1] then a[1] = a[0] fail to swap?
After the first line, both elements hold the old a[1]; the old a[0] is lost. Use a temporary variable or a[0], a[1] = a[1], a[0].
2Show the list after each pass of selection sort on [5, 2, 8, 1].
Pass 1: [1, 2, 8, 5]. Pass 2: [1, 2, 8, 5] (2 is already smallest). Pass 3: [1, 2, 5, 8].
3Show the list after the first pass of bubble sort on [4, 1, 3, 2].
4/1 swap → [1, 4, 3, 2]; 4/3 swap → [1, 3, 4, 2]; 4/2 swap → [1, 3, 2, 4].
4How many comparisons does selection sort make on a list of 6 elements?
5What is the difference between sorted(a) and a.sort()?
sorted(a) returns a new list and leaves a unchanged; a.sort() changes a and returns None.
6In bubble sort, why does the inner loop use range(n - 1 - p) and not range(n)?
It compares values[i] with values[i + 1], so i can go at most to n − 2 (otherwise IndexError), and the last p elements are already in place.
More practice: warm-up
1What does "ascending order" mean?
2Which sort compares neighbouring elements?
3Which sort selects the smallest remaining element each pass?
4What does sorted([3, 1, 2], reverse=True) give?
5What does print([2, 1].sort()) show?
More practice: on your own
1Trace bubble sort with early exit on [1, 2, 4, 3]. How many passes run?
Pass 1: 4/3 swap → [1, 2, 3, 4] (a swap happened). Pass 2: no swaps → stop. 2 passes, 3 + 2 = 5 comparisons.
2Add a comparison counter to selection_sort and return it. What does it return for a 5-element list?
Put count = 0 before the loops, count += 1 just before the if in the inner loop, and return count at the end. It returns 10 (5 × 4 ÷ 2), for any 5-element list.
3Predict the output: print(sorted(["pear", "Apple", "banana"]))
['Apple', 'banana', 'pear']. Capital letters have smaller character codes than lower-case letters, so "Apple" comes first.
4A list of 2000 names takes 2 s to sort with selection sort on an old computer. Estimate the time for 4000 names.
Comparisons grow with n², so doubling n multiplies the work by about 4: roughly 8 s.
5Write a function is_sorted(values) that returns True if the list is in ascending order.
def is_sorted(values):
for i in range(len(values) - 1):
if values[i] > values[i + 1]:
return False
return True
is_sorted([1, 3, 3, 7]) is True; is_sorted([2, 1]) is False.
Challenge
1A team stores names = ["Ana", "Raj", "Kim"] and parallel times = [52.4, 49.8, 55.1]. Write a sort that orders the skaters by time and keeps names matched to their times.
n = len(times)
for start in range(n - 1):
smallest = start
for i in range(start + 1, n):
if times[i] < times[smallest]:
smallest = i
times[start], times[smallest] = times[smallest], times[start]
names[start], names[smallest] = names[smallest], names[start]
Whenever two times are swapped, the matching names are swapped too. Result: ['Raj', 'Ana', 'Kim'] with [49.8, 52.4, 55.1].
2Explain why bubble sort with early exit needs only n − 1 comparisons on a list that is already sorted, but selection sort still needs n(n − 1)/2.
Bubble sort's first pass finds no swaps and stops after n − 1 comparisons. Selection sort has no such check: each pass must look at every remaining element to be sure it has the minimum.
3Write insertion_sort(values): take each element from index 1 on and shift it left past every larger element. Trace it on [3, 1, 2].
def insertion_sort(values):
for i in range(1, len(values)):
current = values[i]
j = i - 1
while j >= 0 and values[j] > current:
values[j + 1] = values[j]
j -= 1
values[j + 1] = current
Trace: i = 1, current 1: 3 shifts right → [1, 3, 2]. i = 2, current 2: 3 shifts right, 1 does not → [1, 2, 3].
Quiz
1. After pass 1 of selection sort on [7, 2, 9, 4], what is the list?
2. After pass 1 of bubble sort on [7, 2, 9, 4], what is the list?
3. How many comparisons does selection sort make on 8 elements?
4. Which line correctly swaps a[i] and a[j] in Python?
5. What does b = sorted(a) do to a?
6. If a list gets 10 times longer, about how much more work does selection sort do?
Big idea: Sorting is the classic nested-structure array algorithm (A2.3), and it uses everything about accessing and modifying arrays (A1.6). Writing the sorts as functions practises A3.2, and tracing passes by hand is A4.4.
How to help: The card activity is the best way to understand sorting. Ask your teen to sort cards out loud, naming each comparison and swap. Then ask, "What part of the row is already sorted?"
Common difficulties:
- Losing a value when swapping without a temporary variable.
- Off-by-one bounds in the inner loop (IndexError on
values[i + 1]). - Mixing up the two algorithms: selection sort finds the minimum then swaps once per pass; bubble sort swaps neighbours many times per pass.
- Writing
a = a.sort(), which sets a to None.