Bubble sort and evidence about refinement

By UK GCSE Computer Science · independent study · myAudience

Original built-in imagegen teaching raster; author inspected original and three served sizes2026-10-04. Independent derivative review pending. · Generated project artwork; no copied exam or publisher illustration. Independent rights/publication review pending.

Bubble sort and evidence about refinement

Sorting reorders values under a declared comparison rule. Our contract returns a new ascending list, preserving every value including duplicates and leaving input unchanged. Entry skills are nested loops and indexed list operations. Bubble sort compares adjacent elements and swaps a pair if out of order. After one left-to-right pass, the largest encountered value has moved to the last position. That fact allows the next pass to stop one position earlier. The generated bubble-sort visual shows each adjacent swap in the first pass, then the fixed suffix and the remaining two passes. Its six comparisons concern the working copy; the original input is preserved.

For [4,1,3,2], compare 4 and 1 and swap to [1,4,3,2]; compare 4 and 3 to obtain [1,3,4,2]; compare 4 and 2 to obtain [1,3,2,4]. The last 4 is now fixed. Pass two compares 1 with 3, then 3 with 2 to obtain [1,2,3,4]. Pass three compares 1 with 2 and makes no swap. Track both data and the shrinking unsorted boundary; recording only the final list cannot demonstrate the mechanics.

The invariant after a pass is that the sorted suffix contains the largest required values in their final positions. A strict > swap preserves the order of equal items, making this implementation stable under a key comparison. Swapping on >= can reorder ties unnecessarily. A stability requirement is important when a second sort is expected to retain an earlier ordering among equal keys, such as sorting records by zone after an earlier sort by time. For plain equal integers, identity is invisible, so record-based reasoning is needed to discuss stability meaningfully.

An early-exit refinement stops after a pass with no swaps, because every adjacent pair within the remaining prefix is already in order and the suffix is fixed. For n=4 our trace makes 3+2+1=6 comparisons. An already sorted list makes only n-1 comparisons with early exit. Reverse order still makes n(n-1)/2 comparisons; under fixed-cost comparison and swap, optional enrichment calls this quadratic worst-case growth. Do not claim bubble sort is always slow or always fast without a workload and implementation. requires qualitative time comparisons, not formal notation.

Correctness tests must check orderedness, multiplicity and input preservation. Checking only result == sorted(set(values)) would destroy duplicates while passing some cases. A multiset comparison can establish preserved counts. The function copies input before swapping; returning input itself would violate the unchanged-input promise if it then sorts in place. Repeated execution should give the same result, although determinism alone is insufficient proof. The transfer makes tie preservation visible and asks you to separate values from record identities.

Runnable original Python 3 example (also saved verbatim in examples for CLI execution):
```python
def bubble_sort(values):
"""Return ascending copy and adjacent comparison count; comparable items."""
data = list(values)
comparisons = 0
for end in range(len(data) - 1, 0, -1):
swapped = False
for index in range(end):
comparisons += 1
if data[index] > data[index + 1]:
data[index], data[index + 1] = data[index + 1], data[index]
swapped = True
if not swapped:
break
return data, comparisons

source = [4, 1, 3, 2]
assert bubble_sort(source) == ([1, 2, 3, 4], 6)
assert source == [4, 1, 3, 2]
assert bubble_sort([1, 2, 3, 4]) == ([1, 2, 3, 4], 3)
assert bubble_sort([2, 2, 1])[0] == [1, 2, 2]
```

Worked example: Show the first full pass for [4,1,3,2] and explain the fixed suffix.

Swap indices 0,1: [1,4,3,2].

Swap indices 1,2: [1,3,4,2].

Swap indices 2,3: [1,3,2,4]. The largest value has crossed every later smaller value.

Answer: [1,3,2,4]; the final 4 is fixed.

Check your understanding: Transfer: records A(key=2), B(key=1), C(key=2) must sort by key while keeping equal-key arrival order. Trace a strict-key bubble pass and explain the risk of swapping equal keys. Give a preservation test.

Answer: Strict comparisons yield B,A,C. Equal A and C are not swapped. Using >= can put C before A during a later pass. Verify both [1,2,2] key order and the identity order [B,A,C], and confirm exactly those three input records remain.

Why: The tie contract cannot be checked by keys alone. Orderedness and permutation are separate properties; stable tie order is a third property. Altering the comparison to make all pairs “move” is not a valid refinement.