01 | WHAT DOES SORTING DO?

Imagine arranging a set of number cards from smallest to largest. The values stay the same, but their positions change. That is sorting: putting items into a required order.

Ascending order means smallest to largest. Descending order means largest to smallest. We will use ascending numeric order throughout the worked example.

Sorting differs from searching. A search finds whether or where a target occurs. A sort rearranges the collection so that the values follow an order.

Bubble sort is a standard method in this syllabus. It repeatedly compares neighbouring items and swaps them when they are out of order. You do not need to understand the complete algorithm immediately: start with one pair.

02 | COMPARE TWO NEIGHBOURS

Adjacent means next to each other. In the list 5, 2, 4, 1, the first adjacent pair is 5 and 2. The next is 2 and 4, and the last is 4 and 1.

For ascending order, ask whether the left value is greater than the right value. If it is, swap them. If it is not, leave them as they are.

Comparing 5 and 2 gives 5 > 2, which is true, so their positions are exchanged. Comparing 2 and 4 gives false, so that pair is already in the required order.

Equal values need not be swapped. The condition uses >, not >=. Bubble sort can still order data containing repeated values.

A comparison is the check. A swap is the change made only when the check shows the pair is out of order. Counting comparisons and counting swaps are different tasks.

03 | A PASS MOVES THROUGH THE LIST

A pass is one sweep through the adjacent pairs being considered. In our full-width version, every pass checks pairs at positions 1 and 2, then 2 and 3, then 3 and 4.

The next comparison uses the current values, including any change from the previous swap. Do not continue comparing the original list after changing it.

For a list with four elements, a full-width pass contains three adjacent comparisons. With N elements, it contains N − 1 comparisons. The last left-hand position is N − 1 because its right-hand neighbour is N.

One pass does not usually finish sorting the whole list. In a left-to-right ascending pass, a largest value moves towards the right-hand end through successive swaps.

04 | WORK THROUGH THE FIRST PASS

Start with 5, 2, 4, 1. Follow the comparisons one at a time.

After the first pass, the list is 2, 4, 1, 5. Five is now at the right-hand end, but the whole list is not sorted: four still appears before one.

This explains the name “bubble sort”. A large value can move repeatedly through neighbouring positions towards the end, like a bubble rising through the list.

Do not jump from the starting list to the final sorted list in a trace. Record each comparison and resulting state so the movement can be followed.

05 | KEEP GOING THROUGH FURTHER PASSES

The second pass starts from 2, 4, 1, 5, not from the original list. Comparing 2 and 4 requires no swap. Comparing 4 and 1 swaps them, producing 2, 1, 4, 5. Comparing 4 and 5 makes no change.

The third pass starts from 2, 1, 4, 5. The first comparison swaps 2 and 1, producing 1, 2, 4, 5. The remaining pairs are already in ascending order.

The list is now sorted, but this particular algorithm checks the stopping rule by performing another pass. The fourth pass makes no swaps, confirming that every adjacent pair is in the correct order.

Different bubble-sort versions can use different stopping rules. Keep your trace consistent with the algorithm you have been given.

06 | TRY THE SORT ONE COMPARISON AT A TIME

Use the demonstration below to follow the same four-value example. The highlighted pair is the next pair to compare. Each step records whether a swap happens and shows the updated list.

Predict the result before selecting the next step. When a pass finishes, notice whether any swap occurred. A pass with no swaps is what stops this demonstration.

This is the full-width, swap-flag version used in our pseudocode. It deliberately checks all three pairs on each pass, including the final confirmation pass.

07 | WHY A SWAP NEEDS A TEMPORARY VALUE

In pseudocode, you cannot safely exchange two stored values by overwriting one and then copying the other back.

Suppose the left value is 5 and the right is 2. If you first copy the right value into the left position, the list contains 2 and 2. The original 5 has been lost from those positions.

A temporary variable preserves one value while the exchange happens.

Temp ← Values[Index]
Values[Index] ← Values[Index + 1]
Values[Index + 1] ← Temp

First save the left value in Temp. Then copy the right value into the left position. Finally copy Temp into the right position. The original pair 5, 2 becomes 2, 5 without losing either value.

Temp is working storage for the exchange. It does not represent a new item added to the array.

08 | REMEMBER WHETHER A PASS CHANGED ANYTHING

A Boolean variable called Swapped tells us whether any pair was exchanged during the current pass. Boolean values are TRUE or FALSE.

Set Swapped to FALSE at the start of each pass. Whenever a swap occurs, set it to TRUE. Leave it TRUE even if a later comparison needs no swap.

Why? The flag means at least one swap anywhere in this pass, not “the most recent comparison swapped”. Resetting it after a later no-swap comparison would lose important evidence.

At the end of the pass, if Swapped is FALSE, every checked pair was already in order. No further pass is needed. If it is TRUE, perform another pass.

The outer loop uses REPEAT UNTIL. It stops when NOT Swapped is true, meaning the last completed pass contained no swaps.

09 | READ THE COMPLETE PSEUDOCODE

The array Values uses indexes 1 to 4. Assume it already contains 5, 2, 4, 1. The algorithm changes that array into ascending order.

DECLARE Values : ARRAY[1:4] OF INTEGER
DECLARE ItemCount : INTEGER
DECLARE Index : INTEGER
DECLARE Temp : INTEGER
DECLARE Swapped : BOOLEAN

// Assume Values contains 5, 2, 4, 1
ItemCount ← 4
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO ItemCount - 1
        IF Values[Index] > Values[Index + 1]
          THEN
            Temp ← Values[Index]
            Values[Index] ← Values[Index + 1]
            Values[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
UNTIL NOT Swapped
FOR Index ← 1 TO ItemCount
    OUTPUT Values[Index]
NEXT Index

The outer REPEAT performs passes. The inner FOR moves through adjacent pairs within each pass. Values[Index + 1] is the neighbour immediately to the right.

The IF swaps only when the left value is greater. At the end of a pass, UNTIL tests whether Swapped remained FALSE.

After sorting finishes, a separate FOR loop outputs the values in order. That final output loop does not perform sorting comparisons and should not be included in the comparison count.

10 | TRACE THE FLAG AS WELL AS THE VALUES

Each pass starts with Swapped set to FALSE. The first pass has three swaps, so it ends TRUE. The second has one swap and ends TRUE. The third has one swap and ends TRUE.

The fourth pass has no swaps and ends FALSE, so NOT Swapped is true and the algorithm stops.

For this exact four-value example and this full-width version, there are 12 adjacent-element comparisons and 5 swaps. The array became ordered during pass three, but pass four verifies the no-swap stopping condition.

A correct trace should show the variant being used. A shrinking-bound version would have a different comparison count, even though it could produce the same final order.

11 | OTHER VALID VERSIONS AND EFFICIENCY

After a complete left-to-right ascending pass, a greatest remaining value is placed at the end of the unsorted part. A more efficient version can shorten the range checked on later passes because those final positions are already settled.

Another basic version performs a fixed number of passes rather than stopping with a swap flag. For N elements, N − 1 full-width passes are enough to sort them, though some may do unnecessary work.

Our swap-flag version can finish after one pass when the input is already sorted. In that case, it still checks N − 1 adjacent pairs but makes no swaps.

Bubble sort is easy to illustrate, but large unsorted collections can need many passes and comparisons. In the worst case the amount of comparison work grows roughly with the square of the number of items, rather than proportionally to the number of items.

You do not need to introduce a different sorting method to explain bubble sort. Focus on the given loop bounds, swap condition and stopping rule.

12 | TEST DUPLICATES, NEGATIVES AND DIFFERENT ORDERS

Try an already-sorted array. It should stay unchanged and, in this version, stop after one no-swap pass. Try reverse order: it needs repeated changes before the no-swap pass.

For 3, 1, 3, 2, the result should be 1, 2, 3, 3. Duplicate values are preserved; sorting does not remove one of the threes.

For −2, 4, −5, 0, the result should be −5, −2, 0, 4. Comparisons use numeric order, so −5 comes before −2 in ascending order.

Our fixed example has four items. A general-purpose design also needs clear rules for collections with one item or no items. For one item, there are no adjacent pairs to compare, so it is already ordered.

Check that the final list has the same values and number of elements as the starting list. A mistaken swap can produce a sorted-looking result that has lost data.

13 | SPOT THE COMMON MISTAKES

Comparing non-neighbours: this method compares Index and Index + 1. Jumping arbitrarily between positions describes a different approach.

Looping to ItemCount: the final adjacent comparison needs Index = ItemCount − 1. Using ItemCount as the left position attempts to read beyond the array.

Stopping after one pass: the largest value may be placed correctly while earlier values remain unordered.

Forgetting Temp: overwriting a value can lose it and duplicate another value.

Resetting Swapped inside every comparison: a later no-swap result can erase evidence of an earlier swap. Reset once at the start of the pass.

Using the wrong stopping condition: UNTIL Swapped would stop after a pass that changed the list. Our version uses UNTIL NOT Swapped.

14 | EXPLAIN THE METHOD CLEARLY

A clear description is: “Bubble sort repeatedly compares adjacent values and swaps pairs that are out of order. Passes continue until the list is sorted, using the stopping rule specified by the algorithm.”

For this swap-flag version, explain the stopping rule precisely: “Swapped is FALSE at the start of each pass and becomes TRUE if any pair is exchanged. A pass with no swaps means every adjacent pair is already in ascending order, therefore the algorithm stops.”

To sort in descending order, reverse the comparison: swap when the left value is smaller than the right. The temporary-variable exchange and repeated-pass idea remain the same.

You should now be able to trace each comparison, explain a safe swap and distinguish the array becoming ordered from the final pass that confirms it in this version.