Tutorial 2

🫧

Bubble Sort

0478 IGCSE

i

It may be useful to search (CTRL + F) for "bubble sort" questions in the (combined) past papers

1

Bubble Sort

In order to sort an array in either ascending or descending order, we can use bubble sort:

  1. Assume array is unsorted and loop to the n-1 position (e.g. 1 to 4, if 5 elements) in the array on the first iteration
  2. Compare elements pair by pair - if in the wrong order (i.e. if current element bigger than next element for ascending order...or current element smaller than next for descending order), then swap them by making use of a temporary variable
  3. If elements are not sorted after looping over all pairs, then go back to the start

More detailed comments can be seen in the code

Note: when we swap, we need the temporary variable - this is since if we do a <-- b, both variables now have the same value at this point - b <-- a will be redundant - hence why we need to move one value into a temporary variable before we update it, then assign this temporary variable value to the other variable. Drawing a picture with arrows representing the assignments between 3 variables can help with understanding.

DECLARE arrayLength : INTEGER DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE targetNumber : INTEGER arrayLength <-- 5 nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 //bubble sort DECLARE temp : INTEGER DECLARE isSorted : BOOLEAN DECLARE endIndex : INTEGER endIndex <-- arrayLength - 1 //if array has 5 elements, then loop to 4, since can't compare element 5 with element 6, as there is no element 6... isSorted <-- FALSE //assume unsorted by default WHILE isSorted = FALSE DO //loop while not sorted isSorted <-- TRUE //assume is sorted, at start of each pass over all pairs - if no swaps made, then loop will terminate after this iteration FOR index <-- 1 TO endIndex //compare current with next element - if wrong order, then swap IF nums[index] > nums[index + 1] THEN //swap, using temp variable as intermediate storage temp <-- nums[index] nums[index] <-- nums[index + 1] nums[index + 1] <-- temp //since at least 1 element is not in correct order, then we need to loop again to continue sorting/check isSorted <-- FALSE ENDIF NEXT index //rightmost element sorted on 1st loop, 2nd rightmost on 2nd loop etc - hence don't need to swap these already sorted elements endIndex <-- endIndex - 1 ENDWHILE //not bubble sort - just to output FOR index <-- 1 TO arrayLength OUTPUT nums[index] NEXT index