Bubble sort

Put the smallest time first

• Three race times sit in an array: 14, 9, 11. The smallest should come first.
• Compare each pair of neighbours. When the left one is larger, swap them.
• That single comparison does not finish the list. The next pair is compared after it.

DECLARE Score : ARRAY[1:3] OF INTEGER
DECLARE J, Temp : INTEGER
Score[1] ← 14
Score[2] ← 9
Score[3] ← 11
FOR J ← 1 TO 2
    IF Score[J] > Score[J + 1]
      THEN
        Temp ← Score[J]
        Score[J] ← Score[J + 1]
        Score[J + 1] ← Temp
    ENDIF
NEXT J
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]

Repeat the pass

• One pass of the inner loop bubbles the largest value it sees toward the end.
• The outer loop repeats the pass. For four values, three passes are enough.
• This is the syllabus's bubble sort. A linear search, which you wrote earlier, only looks. A sort rearranges.

DECLARE Score : ARRAY[1:4] OF INTEGER
DECLARE I, J, Temp : INTEGER
Score[1] ← 4
Score[2] ← 1
Score[3] ← 3
Score[4] ← 2
FOR I ← 1 TO 3
    FOR J ← 1 TO 3
        IF Score[J] > Score[J + 1]
          THEN
            Temp ← Score[J]
            Score[J] ← Score[J + 1]
            Score[J + 1] ← Temp
        ENDIF
    NEXT J
NEXT I
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
OUTPUT Score[4]

Watch out

• Swap with a Temp variable. Score[J] ← Score[J + 1] alone deletes the left value.
• The inner NEXT names J. The outer NEXT names I.

Stop when nothing swaps

• The fixed version always makes every pass, even when the list is already in order.
• A BOOLEAN flag, Swap, remembers whether a pass swapped anything. A pass with no swap means the list is sorted, so the loop stops.
• After each pass the largest value left is in place, so Last shrinks by one.

DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE J, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
Score[1] ← 2
Score[2] ← 1
Score[3] ← 3
Score[4] ← 4
Score[5] ← 5
Last ← 4
REPEAT
    Swap ← FALSE
    FOR J ← 1 TO Last
        IF Score[J] > Score[J + 1]
          THEN
            Temp ← Score[J]
            Score[J] ← Score[J + 1]
            Score[J + 1] ← Temp
            Swap ← TRUE
        ENDIF
    NEXT J
    Last ← Last - 1
UNTIL NOT Swap OR Last = 0
FOR J ← 1 TO 5
    OUTPUT Score[J]
NEXT J

Here the first pass swaps 2 and 1, and the second pass swaps nothing, so the sort stops after two passes instead of four.

Common mistakes

• The test is "left is greater", so the smaller value moves left. The other way sorts into reverse order.
• Arrays in this course count from 1. The last pair is the cell just before the end, and the last cell.
• FOR J ← 1 TO 4 on a 4-cell array reads Score[5], which does not exist. The inner loop stops one before the end.
• Setting Swap ← FALSE once, before the REPEAT. It must be reset at the start of every pass.

Now you try

• The first task is one pass. The second is the full sort. The third reads five values and sorts them into descending order with a Swap flag. Output each value on its own line.
• Press Check answer to test it.