QUESTION 29 · Sorting
It preserves the original relative order of items with equal keys.
QUESTION 30 · Sorting
The three methods all sort by comparisons, but differ in how values are moved and how they behave on nearly sorted input.
Adjacent values are compared and swapped when out of order. Each pass fixes a rightmost value. With the early-stop flag used here, sorted input takes O(n); average and worst cases take O(n²). Strictly-greater adjacent swaps preserve equal-value order.
Each pass scans for the minimum remaining value and swaps it into the next leftmost position. The scan count remains quadratic even on sorted input: O(n²). It uses relatively few swaps, at most n - 1, but a distant swap can reverse equal keys, so the usual version is not stable.
Each next key is inserted into a sorted prefix by shifting larger values. It takes O(n) on already sorted input and O(n²) in the worst case. The strict comparison used here preserves equal-key order. It is often useful for small or nearly sorted lists.
All three shown implementations sort within the input array and use only a fixed number of extra variables. Their auxiliary space is O(1). This does not mean the input array takes no space; it means no extra storage proportional to n is needed.
Look at input size, order, required stability and the cost of moving a record. A comparison of only worst-case Big-O values misses practical differences. For much larger lists, other algorithms may be preferable, but they are outside these three basic syllabus methods.
| Method | Best time | Worst time | Extra space | Stable |
|---|---|---|---|---|
| Optimised bubble | O(n) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(1) | Yes |
Related questions in the bubble sort category from the supplied papers. The marks below are the printed allocations, including any combined subquestion.
Explain bubble sort with an example.
Paper P01 · page 1Explain bubble sort and mention its time complexity.
Paper P04 · page 1