A sorting pass is one sweep through a list that compares neighbouring items and swaps them when they are in the wrong order. Questions may ask you to show the list after one pass, count swaps, or explain what a line of code does.
This lesson is part of searching, sorting and files. Check the Cambridge syllabus for your exam year to see how far sorting algorithms are expected. The tracing skill itself carries across, and it builds on tracing a linear search.
What happens in one pass?
Take the first two items. If the left one is larger, swap them.
Then move one place right and compare the next pair. Continue until the last pair.
Larger values keep getting carried to the right, like bubbles rising. That is why, after one pass, the largest value is in the last position.
How do I swap two values?
A swap needs a third place to hold one value, because assigning directly overwrites it:
Temp ← Data[I]
Data[I] ← Data[I + 1]
Data[I + 1] ← TempHere is the pass as pseudocode for a list of five items:
Swapped ← FALSE
FOR I ← 1 TO 4
IF Data[I] > Data[I + 1] THEN
Temp ← Data[I]
Data[I] ← Data[I + 1]
Data[I + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT IThe loop goes only to 4 because the last comparison is position 4 with position 5.
Worked example
Data = [6, 2, 9, 4, 1]. Trace the first pass.
| I | Pair compared | Out of order? | List afterwards | Swapped |
|---|---|---|---|---|
| Start | 6, 2, 9, 4, 1 | FALSE | ||
| 1 | 6 and 2 | Yes, swap | 2, 6, 9, 4, 1 | TRUE |
| 2 | 6 and 9 | No | 2, 6, 9, 4, 1 | TRUE |
| 3 | 9 and 4 | Yes, swap | 2, 6, 4, 9, 1 | TRUE |
| 4 | 9 and 1 | Yes, swap | 2, 6, 4, 1, 9 | TRUE |
After one pass the list is [2, 6, 4, 1, 9]. Three swaps were made. The largest value, 9, is now in position 5, but the list is not yet sorted, so another pass is needed.
A second pass gives [2, 4, 1, 6, 9]. A third gives [2, 1, 4, 6, 9]. A fourth gives [1, 2, 4, 6, 9].
A fifth pass makes no swaps, so Swapped stays FALSE and the sort stops.
The mistake to watch for
A common slip is to swap without the temporary variable:
Data[I] ← Data[I + 1]
Data[I + 1] ← Data[I]Take Data = [6, 2] with I = 1. The first line sets Data[1] to 2, giving [2, 2].
The second line then copies Data[1], which is now 2, into Data[2]. The result is [2, 2], and the 6 is lost.
The correction is to save the first value in Temp before overwriting it. When you trace a swap, write the value of Temp in its own column so the lost value is visible.
Check yourself
1. Trace one pass on [3, 1, 2]. What is the list afterwards, and how many swaps were made?
Show answer
Compare 3 and 1: swap, giving 1, 3, 2. Compare 3 and 2: swap, giving 1, 2, 3. Result [1, 2, 3] with 2 swaps.
2. One pass on [4, 5, 6] ends with Swapped = FALSE. What does that tell you?
Show answer
No pair was out of order, so the list is already sorted and no further pass is needed.
3. A = 4 and B = 9. Write three lines that swap them, then give the final values.
Show answer
Temp ← A (Temp = 4), A ← B (A = 9), B ← Temp (B = 4). Final values: A = 9, B = 4.
Where this leads next
Next, see how stored data is split into parts in reading a record without losing field boundaries. The restricted pseudocode trace trainer can step through a pass so you can compare each list state with your own table.
If swaps or the flag still trip you up, a teacher in online one-to-one Computer Science tuition can trace a few passes with you and show where the value goes missing.