COMP5112 Chap.8 Elementary Sorting and Stability
Elementary Sorting and Stability
Quadratic algorithms still make different promises
Selection, bubble and insertion sort share familiar quadratic worst cases but build order differently. The chapter traces the sorted region for each method, distinguishes comparisons from swaps and shifts, and uses labelled equal keys to test stability.
Best and worst inputs are tied to the exact algorithm variant and cost measure rather than assumed from the name alone.
Selection sort scans the unsorted suffix to find its minimum and moves that key into the next front position. After pass i, the prefix through i contains the smallest keys in final order. The scan pattern remains essentially fixed even for sorted input, so comparisons do not improve with existing order.
Its small number of swaps can still matter when writes are expensive, showing why one cost measure cannot describe every workload.
Bubble sort compares adjacent pairs and exchanges inversions. A complete pass moves an extreme key to the boundary of the active range, creating a sorted suffix for an ascending version. An early-stop flag can make the method adaptive by ending after a pass with no swaps.
Without that feature, a best-case claim of linear time is unsupported. Trace the exact variant printed in the question.
Insertion sort treats an initial prefix as sorted. It saves the next key, shifts larger prefix elements right, and writes the saved key into the resulting gap. Nearly sorted input requires few shifts, while reverse order creates many.
The invariant states that the prefix is sorted and contains exactly the processed records. Marking the saved key separately prevents a shift trace from appearing to overwrite data.
Stability asks whether records with equal keys retain their original relative order. Labels such as 7a and 7b are necessary evidence because bare equal numbers hide identity.
Insertion sort remains stable when it shifts strictly greater keys, and bubble sort remains stable when it does not swap equals. Ordinary selection sort may move a distant minimum across an equal record and is generally unstable.
Counting should distinguish comparisons, swaps and moves. Two methods can share quadratic worst-case comparisons while performing very different data movement.
Best-case inputs must be paired with the operation counted and the implementation details. Loop-condition tests may also be counted under some conventions, so state the convention once and use it consistently rather than mixing totals from different sources.
When given intermediate arrays, identify what becomes final.
A growing sorted prefix with shifts suggests insertion sort; a new minimum fixed at the front suggests selection; adjacent exchanges moving a large key to the end suggest bubble. Confirm the guess against another pass and its invariant. Finish comparisons with workload conditions, such as small nearly sorted stable records or a limit on writes, instead of announcing an unconditional winner.
What this chapter covers
- 01
Selection-sort minimum placement
- 02
Bubble-sort adjacent inversions
- 03
Insertion-sort sorted prefixes
- 04
Comparison and movement counts
- 05
Best and worst arrangements
- 06
Stable equal-key ordering
Worked example · free
Trace insertion sort
- 2Insert 3 into the first prefix.
- 3Insert 6 with one shift.
- 3Insert 4 and verify the invariant.
Key terms
- Sorted Prefix
- The front region already ordered and final relative to processed items.
- Inversion
- A pair of items appearing in the opposite order from the target ordering.
- Stable Sort
- A sort that preserves the original order of equal-key records.
- Adaptive Sort
- A sort whose work can decrease when the input already contains order.
Elementary Sorting and Stability FAQ
Why does selection sort not improve much on sorted input?
Its inner search still compares the remaining items to locate the minimum. It may avoid an unnecessary self-swap, but the comparison count remains quadratic under the standard implementation.
How can one comparison sign change stability?
Insertion sort preserves equal order when it shifts only strictly greater keys. Shifting greater-than-or-equal keys can move a later equal record ahead of an earlier one in the output.
How can I identify a sorting algorithm from a trace?
Look for the region made final: one minimum fixed at the front suggests selection, adjacent swaps settling a maximum suggests bubble, and shifts into a growing prefix suggest insertion sort.
Exam move
Trace records with identities such as 7a and 7b, not just numbers. Count comparisons and data moves separately so best-case claims have a named measure. Use sorted, reverse and nearly sorted inputs against the exact pseudocode variants. After each pass, circle the region guaranteed final and write its invariant.
Build a comparison matrix for stability, adaptiveness, auxiliary space, comparisons and writes, then make a recommendation for a stated workload rather than naming an unconditional winner.
Working through Elementary Sorting and Stability in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Elementary Sorting and Stability question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
