D1 1.2 - Bubble sort and quick sort
Sorting algorithms reach an ordered list by different sequences of comparisons. You will carry out bubble sort and Pearson's middle-pivot quick sort, record complete passes, and distinguish comparisons, swaps and order of growth.
Bubble sort by adjacent comparisons
If two methods finish with the same sorted list, have they done the same work? Bubble sort only compares neighbours; quick sort partitions whole sublists around pivots. Their intermediate lists show which method was used.
You already know
An algorithm must be followed exactly, with current values and a stated stopping rule. A trace records the process, not merely the final output. Ascending order runs from smallest to largest; descending order runs from largest to smallest.
For descending bubble sort, start at the left: compare the first and second items and swap them if the second is larger. Then compare the current second and third items, swapping if the third is larger, and continue to the right-hand end. That is one pass. The smallest item has reached its final right-hand position.
Repeat on the unsorted prefix, excluding the fixed right-hand items. For ascending order, reverse the swap test: swap neighbours when the right-hand item is smaller. Stop when a complete active pass makes no swaps, or every position has been fixed.
Worked example 1: descending bubble sort
Question. Use bubble sort, starting at the left, to sort into descending order. Show each pass.
Plan. Swap a neighbouring pair whenever the right-hand value is larger, reducing the active prefix after each pass.
The first pass follows
The first comparison, with , required no swap.
| Pass | List after the pass | Comparisons | Swaps |
|---|---|---|---|
Why show the third pass? It confirms that the remaining active prefix needs no swaps; the algorithm does not stop merely because the list looks sorted to us.
Answer. , with comparisons and swaps.
Check. The list contains every original item once, in the requested descending order.
Worked example 2 changes only the requested direction. The input list and left-to-right scan stay the same.
Worked example 2: ascending bubble sort
Question. Use left-to-right bubble sort to sort into ascending order.
Plan. Swap when the right-hand neighbour is smaller, so the largest active item moves to the right.
| Pass | List after the pass | Comparisons | Swaps |
|---|---|---|---|
Why change the test rather than reverse the final list? The required algorithm must carry out the requested sort; reversing an answer afterwards hides a different sequence of comparisons.
Answer. .
Check. The largest value became fixed at the right after the first pass, as ascending bubble sort predicts.
Equal adjacent values need not be swapped. A comparison still counts when no swap occurs: these are different measures of work.
Watch out
Wrong: count only swaps as comparisons. Right: every tested pair contributes one comparison, including pairs already in the correct order.
Keep the ascending test and change the input.
Quick sort using middle pivots
Quick sort fixes a pivot's position by partitioning all other items around it, then repeats on the resulting sublists. A pivot is the middle item by position, not the middle numerical value.
Use this convention throughout: choose the middle item of an odd-length sublist and the middle-right item of an even-length sublist. For descending order, put larger values to its left and smaller values to its right, retaining their relative order within each group. Put any further copies equal to the pivot on the right consistently. A middle-left choice for even sublists is also valid if used consistently, but do not switch conventions mid-sort.
In one pass, process every unfixed sublist of length at least , each with its own pivot. A singleton is already fixed and is not chosen as a pivot in our convention. Even an already ordered two-item sublist must be processed. Vertical separators below show sublists; boxed values are fixed.
Worked example 3: processing several sublists in one pass
Question. Use quick sort to place in descending order. Identify the pivots in each pass.
Plan. Select the middle pivot in every active sublist, partition stably, and keep fixed pivots in place.
| Pass | Pivots used | Result |
|---|---|---|
For example, the right-hand sublist in Pass 1 is . Its pivot separates it into and .
Why use three pivots in Pass 3? There are three active two-item sublists. Processing only one would not complete that pass.
Answer. .
Check. After Pass 3, every unboxed group is a singleton. No further partition is needed.
Worked example 4 changes only the middle input value, from to . Choosing a middle position does not guarantee a balanced numerical split.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account