Study CommonsRead · reason · practise

Home / Reasoning / Sort a List: Pick the Smallest, Swap It Forward, Repeat

Reasoning & Coding · Coding

Sort a List: Pick the Smallest, Swap It Forward, Repeat

Put a list in order with a plan: find the smallest item, swap it into place, repeat. Learn the swap with temp, trace each round and debug sorting programs.

Grades 3–5 · 19 practice questions · Original material
Learning objectiveSort a list from smallest to biggest by repeating one round at a time: find the smallest item and its place, swap it into the next place using a temp variable, and stop after one fewer round than there are items; trace each round and find bugs in sorting programs.

The idea

Imagine five cards face up on a table: 7, 3, 9, 2, 5. You want them in order from smallest to biggest. A simple plan is to find the smallest card, put it first, then find the smallest of the cards that are left, put it second, and keep going. A program can sort a list with exactly this plan.

Each time you do the plan once, that is a round. In round 1, look at the whole list, find the smallest item and swap it into place 1. In round 2, place 1 is finished, so look at places 2 to the end, find the smallest and swap it into place 2. Keep going until the list is in order. (This plan is often called a selection sort.)

Finding the smallest uses the pattern from Biggest So Far, flipped. Set least to the first item you are looking at and pos to its place. For each item: If n < least [Set least to n; Set pos to i]. This time you must remember the place, pos, as well as the value, because you need to know which item to swap.

To swap two items, you need a helper variable. Set temp to a. Set a to b. Set b to temp. If you skip temp and write Set a to b and then Set b to a, the old a is erased before it was saved, and both variables hold b. This is a very common bug, and it loses a value from the list.

A list with 5 items needs only 4 rounds. After 4 items are in their final places, the last one has nowhere else to go. A round can also change nothing: if the smallest item is already in the right place, it swaps with itself.

To sort from biggest to smallest, flip the test to n > least (call the variable most) and everything else stays the same. When you test a sorting program, use a list that is already in order, a list that is backwards and a list with equal values, not just one lucky list.

Worked examples

Example 1 · Swap with temp

Set a to 3. Set b to 8. Set temp to a. Set a to b. Set b to temp. What are a and b?

  1. Trace table: temp | a | b. Start: a = 3, b = 8.
  2. Set temp to a: temp = 3. Set a to b: a = 8. Set b to temp: b = 3.
  3. The two values traded places and nothing was lost.

a is 8 and b is 3.

Example 2 · The swap bug

Set a to 3. Set b to 8. Set a to b. Set b to a. What are a and b?

  1. Set a to b: a = 8. The old 3 is gone.
  2. Set b to a: b = 8, because a is now 8.
  3. Without temp to save the 3, both variables hold 8.

Both are 8. Add temp to fix it.

Example 3 · Find the smallest and its place

Set list to [7, 3, 9, 2, 5]. Set least to the first item. Set pos to 1. Set i to 0. For each n in list [Change i by 1; If n < least [Set least to n; Set pos to i]]. say pos.

  1. Trace table: i | n | n < least? | least | pos. Start: least = 7, pos = 1.
  2. 1: 7 no (7, 1) · 2: 3 yes (3, 2) · 3: 9 no (3, 2) · 4: 2 yes (2, 4) · 5: 5 no (2, 4).
  3. Round 1 then swaps place 4 with place 1, so the list becomes [2, 3, 9, 7, 5].

It says 4: the smallest value, 2, is in place 4.

Example 4 · Sort a whole list

Sort [7, 3, 9, 2, 5] from smallest to biggest. Show the list after each round.

  1. Round 1: smallest is 2 (place 4); swap with place 1 → [2, 3, 9, 7, 5].
  2. Round 2: look at places 2–5 (3, 9, 7, 5). The smallest is 3, already in place 2 → no change.
  3. Round 3: look at places 3–5 (9, 7, 5). The smallest is 5 (place 5); swap with place 3 → [2, 3, 5, 7, 9].
  4. Round 4: look at places 4–5 (7, 9). The smallest is 7, already in place 4 → [2, 3, 5, 7, 9].

[2, 3, 5, 7, 9] after 4 rounds.

Example 5 · Biggest first

Sort [4, 1, 6, 3] from biggest to smallest by finding the largest each round.

  1. Round 1: largest is 6 (place 3); swap with place 1 → [6, 1, 4, 3].
  2. Round 2: look at places 2–4 (1, 4, 3). The largest is 4 (place 3); swap with place 2 → [6, 4, 1, 3].
  3. Round 3: look at places 3–4 (1, 3). The largest is 3; swap with place 3 → [6, 4, 3, 1].

[6, 4, 3, 1] after 3 rounds.

Common mistakes

Swapping without temp.

Why this fails: Set a to b erases the old a. Save it in temp first, or one value is lost and another is copied.

Sliding items over instead of swapping.

Why this fails: In this sort, the smallest item trades places with the item in the next place. Items between them do not slide. [5, 8, 1, 7] becomes [1, 8, 5, 7], not [1, 5, 8, 7].

Looking at the whole list again in every round.

Why this fails: Places that are finished stay finished. Each round starts one place later.

Stopping too early because the first few items look right.

Why this fails: A list with n items needs n − 1 rounds. Items at the end can still be out of order.

Remembering the value of the smallest item but not its place.

Why this fails: You cannot swap without knowing where the smallest item is. Update pos at the same time as least.

Testing with only one list.

Why this fails: A lucky list can hide a bug. Try a sorted list, a backwards list and a list with ties.

Foundation

Foundation practice

Swap two values and do round 1 of a sort.

Trace a swap

1. Set a to 3. Set b to 8. Set temp to a. Set a to b. Set b to temp. say a, then say b. What is said?

  1. 3 then 8
  2. 8 then 3
  3. 8 then 8
  4. 3 then 3
Why temp?

2. Why does a swap need the variable temp?

  1. temp makes the swap run faster.
  2. temp stores the finished sorted list.
  3. Without it, the first value is overwritten before it can be copied, so both places end up holding the same number.
  4. temp counts how many rounds have run.
Round 1

3. Set the list to [6, 2, 9, 4] and sort smallest to biggest. In round 1, which place holds the smallest value, and which place does it swap with?

  1. Place 1 stays because 6 is first
  2. Place 4 swaps with place 1
  3. Place 3 swaps with place 2
  4. Place 2 swaps with place 1
After round 1

4. Sort [5, 8, 1, 7] from smallest to biggest. What is the list after round 1?

  1. [1, 8, 5, 7]
  2. [1, 5, 8, 7]
  3. [1, 5, 7, 8]
  4. [5, 1, 8, 7]
How many rounds?

5. A list has 6 items. How many rounds does this sort need to put it in order?

  1. 6
  2. 5
  3. 3
  4. 15

Practice

Practice practice

Trace a whole sort, round by round.

After round 2

6. Sort [4, 2, 5, 1] from smallest to biggest. What is the list after round 2?

  1. [1, 2, 4, 5]
  2. [2, 1, 5, 4]
  3. [1, 4, 2, 5]
  4. [1, 2, 5, 4]
Finish the sort

7. Sort [9, 4, 7, 1, 6] from smallest to biggest. What is the final list?

  1. [1, 4, 6, 9, 7]
  2. [1, 4, 7, 9, 6]
  3. [1, 4, 6, 7, 9]
  4. [9, 7, 6, 4, 1]
Already sorted

8. Sort [1, 2, 3, 4]. There are 3 rounds. In how many rounds does the list actually change?

  1. 0
  2. 3
  3. 1
  4. 2
Biggest first

9. Sort [3, 7, 2, 5] from biggest to smallest by finding the largest each round. What is the list after round 1?

  1. [2, 3, 7, 5]
  2. [7, 3, 2, 5]
  3. [3, 2, 5, 7]
  4. [7, 5, 3, 2]
Equal values

10. Sort [5, 2, 5, 1] from smallest to biggest. What is the final list?

  1. [1, 2, 5]
  2. [5, 5, 2, 1]
  3. [1, 2, 5, 5]
  4. [1, 5, 2, 5]

Think

Think practice

Find bugs and test sorting programs.

Find the bug

11. Set list to [7, 3, 9, 2, 5]. Set least to the first item. Set pos to 1. Set i to 0. For each n in list [Change i by 1; If n < least [Set least to n]]. say pos. It says 1, but the smallest value, 2, is in place 4. Which fix makes it say 4?

  1. Inside the If, after Set least to n, add Set pos to i.
  2. After the loop, add Set pos to i.
  3. Change n < least to n > least.
  4. Set i to 1 instead of 0.
Is it sorted?

12. Ana sorts [8, 5, 9, 2, 7] and stops after 2 rounds. She says, "The first two items are in order, so the list is sorted." Is she right?

  1. Yes. The first two items are in order, so the rest must be too.
  2. No. After 2 rounds the list is [2, 5, 9, 8, 7]. The last three items are still out of order.
  3. Yes. Two rounds is half of four, which is enough.
Lucky test

13. A student tests a sort program with only [2, 1, 3, 4] and it works. Why is this a weak test? Suggest a better list to test with.

Alphabetical order

14. Sort [Mia, Ali, Zed, Bo] in alphabetical order. What is the list after round 1?

  1. [Bo, Ali, Zed, Mia]
  2. [Ali, Bo, Mia, Zed]
  3. [Zed, Mia, Bo, Ali]
  4. [Ali, Mia, Zed, Bo]
Missing item

15. A sort starts with [3, 1, 2, 4] and finishes with [1, 1, 2, 4]. What most likely went wrong?

  1. The sort stopped one round too early.
  2. A swap was written without temp, so one value was copied over another and lost.
  3. The sort looked for the largest instead of the smallest.
  4. Selection sort cannot handle equal values.

Challenge

Challenge practice

Plan a sort, count the work and reuse patterns.

Write the plan

16. Write the plan for sorting a list smallest to biggest in plain steps or blocks.

Count the looks

17. Each round looks at every item that is not yet in its final place. A list has 5 items and the sort runs 4 rounds. How many items are looked at in total?

  1. 14
  2. 15
  3. 10
  4. 20
Top three

18. Run only 3 rounds of the smallest-first sort on [9, 3, 7, 1, 8, 2]. What are the first three items, and is the whole list sorted?

Explain

19. How is finding the smallest item in each round like the Biggest So Far lesson?

Answer key

  1. 1. 8 then 3
    temp keeps the old a (3). Then a becomes 8, and b becomes the saved 3, so the two values trade places. 3 then 8 would mean nothing changed, 8 then 8 is what happens if temp is skipped, and 3 then 3 copies the wrong value.
  2. 2. Without it, the first value is overwritten before it can be copied, so both places end up holding the same number.
    Set a to b erases the old a. If it was not saved in temp first, it is gone. temp does not make the swap faster, does not hold the sorted list and does not count rounds.
  3. 3. Place 2 swaps with place 1
    The smallest value is 2, in place 2. Round 1 swaps it into place 1, giving [2, 6, 9, 4]. Place 1 holds 6, which is not the smallest, so it does not stay. Place 4 holds 4 and place 3 holds 9; neither is the smallest.
  4. 4. [1, 8, 5, 7]
    The smallest, 1, is in place 3. It swaps with the item in place 1 (5), so 5 moves to place 3: [1, 8, 5, 7]. [1, 5, 8, 7] slides the items over instead of swapping, [1, 5, 7, 8] is the finished list, and [5, 1, 8, 7] swaps 1 with its neighbour in place 2.
  5. 5. 5
    After 5 rounds, five items are in their final places, and the last item has nowhere else to go. 6 would add a useless round, 3 stops half way, and 15 counts every look instead of rounds.
  6. 6. [1, 2, 5, 4]
    Round 1 swaps 1 into place 1: [1, 2, 5, 4]. In round 2, the smallest of the rest is 2, already in place 2, so nothing changes. [1, 2, 4, 5] is the list after round 3, [2, 1, 5, 4] puts 1 in the wrong place, and [1, 4, 2, 5] slides items instead of swapping.
  7. 7. [1, 4, 6, 7, 9]
    Round 1: [1, 4, 7, 9, 6]. Round 2: 4 stays. Round 3: 6 swaps with 7, giving [1, 4, 6, 9, 7]. Round 4: 7 swaps with 9, giving [1, 4, 6, 7, 9]. [1, 4, 6, 9, 7] stops one round early, [1, 4, 7, 9, 6] stops after round 1 or 2, and [9, 7, 6, 4, 1] sorts the wrong way.
  8. 8. 0
    In every round, the smallest of the rest is already in the first spot of the rest, so it swaps with itself and nothing moves. The rounds still run, because the program does not know the list is sorted. 1, 2 and 3 all assume some swap must happen in a round.
  9. 9. [7, 3, 2, 5]
    The largest, 7, is in place 2. It swaps with place 1: [7, 3, 2, 5]. [2, 3, 7, 5] uses the smallest instead, [3, 2, 5, 7] pushes the 7 to the end, and [7, 5, 3, 2] is the finished list.
  10. 10. [1, 2, 5, 5]
    Equal values are fine: both 5s stay in the list, side by side. [1, 2, 5] loses a 5, [5, 5, 2, 1] is biggest first, and [1, 5, 2, 5] stops after round 1.
  11. 11. Inside the If, after Set least to n, add Set pos to i.
    pos must change at the same moment least changes, so the two always match. Setting pos after the loop gives 5 (the last place), changing < to > would look for the largest and still never change pos, and starting i at 1 still leaves pos unchanged.
  12. 12. No. After 2 rounds the list is [2, 5, 9, 8, 7]. The last three items are still out of order.
    Round 1 gives [2, 5, 9, 8, 7]. Round 2 finds that 5 is already in place. Two items in order does not mean the whole list is. A 5-item list needs 4 rounds.
  13. 13. One round already puts [2, 1, 3, 4] in order, so it would also pass if the program stopped after one round. A better test is [3, 4, 5, 1, 2], which needs all four rounds.
    A good test makes every round do real work. In [3, 4, 5, 1, 2], the list changes in each of the 4 rounds. Also test an already sorted list, a backwards list and a list with ties.
  14. 14. [Ali, Mia, Zed, Bo]
    Ali comes first in the alphabet and is in place 2, so it swaps with Mia in place 1. [Bo, Ali, Zed, Mia] picks the shortest name, which sorts by length, not by alphabet. [Ali, Bo, Mia, Zed] is the finished list, and [Zed, Mia, Bo, Ali] sorts backwards.
  15. 15. A swap was written without temp, so one value was copied over another and lost.
    The 3 disappeared and the 1 appeared twice: that is what happens when a swap writes over a value before saving it. Stopping early would still keep all four original numbers, sorting biggest first would not create a second 1, and the list has no ties for the sort to mishandle.
  16. 16. Example: Repeat for round 1 up to length − 1 [find the place of the smallest item from this round's place to the end; swap that item with the item in this round's place].
    A good plan finds the smallest of the unsorted part, swaps it into the next place, and repeats one fewer time than the number of items. Use temp inside the swap.
  17. 17. 14
    Round 1 looks at 5 items, round 2 at 4, round 3 at 3 and round 4 at 2: 5 + 4 + 3 + 2 = 14. 15 adds a fifth round that never runs, 10 counts only the comparisons (4 + 3 + 2 + 1), and 20 pretends every round looks at all 5 items.
  18. 18. The first three items are 1, 2, 3, the three smallest, in order. The whole list is not sorted: it is [1, 2, 3, 9, 8, 7].
    Each round fixes one more place at the front. Stopping early is useful when you only need the smallest few, such as a top three, but the rest of the list can still be out of order.
  19. 19. It is the same pattern with the test flipped to <. Each round runs it again on a shorter list, and it also remembers the place of the winner so that item can be swapped into position.
    Sorting reuses patterns you already know: a best-so-far variable inside a loop, plus a swap, repeated.

Related practice

Biggest So Far: Find the Largest Value in a ListSearch a List: Is It There, and Where?Lists: Store Many Values and Loop Through Each OneReasoning hub