7.03j, 7.03k - Sorting algorithms | OCR A-Level Further Mathematics A

Sorting is more than writing the final ordered list: the route matters. You will carry out OCR's bubble, shuttle and quick sorts, show the correct passes and stopping points, and explain how the input and the choice of pivot affect the work required.

Bubble sort and its stopping pass

Can a list already in increasing order be a bad input for quick sort? It can, even though it is an excellent input for bubble sort. To understand why, follow the stated instructions rather than the everyday meaning of “quick”.

You already know

A comparison tests values; a swap exchanges them; a pass is one specified stage of an algorithm. Compare efficiency using the measure requested. A sum such as $1+2+\cdots+(n-1)$ equals $n(n-1)/2$ and has quadratic order.

For increasing order, begin at the left unless told otherwise. Compare the first two entries and swap if the left one is larger. Compare the new second entry with the third, then continue to the end of the active list. A large entry can move several places right during a pass; a small one moves only one place left.

Bubble sort

After each left-to-right pass, fix the final entry of the active list and repeat on the remaining prefix. Stop either after a pass with no swaps or when the active list has length $1$ . In decreasing order, reverse the comparison so that smaller entries move towards the right.

The complete bubble-sort instructions are in the formula booklet. For increasing order, the largest unfixed entry reaches the right-hand end on each pass, which explains why that end can be fixed. An entry looking correctly placed before its fixing pass is not a reason to shorten the active list further.

Worked example 1: sorting, then certifying the finish

Question. Use bubble sort from the left to put $4,1,5,2,6,3$ into increasing order. Show every pass and count the comparisons.

Plan. Compare neighbouring entries, shorten the active prefix by one each pass and retain a no-swap pass if needed.

The first pass has these changes:

\begin{aligned} 4,1,5,2,6,3&\longrightarrow1,4,5,2,6,3 && \text{swap }4,1\\ &\longrightarrow1,4,2,5,6,3 && \text{swap }5,2\\ &\longrightarrow1,4,2,5,3,6 && \text{swap }6,3 \end{aligned}

The other two comparisons in that pass need no swap.

Pass	List at its end	Comparisons	Swaps
$1$	$1,4,2,5,3,6$	$5$	$3$
$2$	$1,2,4,3,5,6$	$4$	$2$
$3$	$1,2,3,4,5,6$	$3$	$1$
$4$	$1,2,3,4,5,6$	$2$	$0$

Why this step? Pass $3$ makes the list look sorted but contains a swap. The stated algorithm discovers that it can stop only after pass $4$ makes no swaps.

Answer. The ordered list is $1,2,3,4,5,6$ ; the algorithm takes $4$ passes and $5+4+3+2=14$ comparisons.

Check. The list has all six original entries, and every adjacent pair is increasing. The fixed suffix grows by one entry after each pass.

Worked example 2 changes only the positions of the final two input entries. That reduces the work, but you must still check the stopping rule.

Worked example 2: a shorter run

Question. Apply the same bubble sort to $4,1,5,2,3,6$ . Show every pass and count comparisons.

Plan. Start with the full list even though its final entry is already the largest.

Pass	List at its end	Comparisons	Swaps
$1$	$1,4,2,3,5,6$	$5$	$3$
$2$	$1,2,3,4,5,6$	$4$	$2$
$3$	$1,2,3,4,5,6$	$3$	$0$

The first pass moves $4$ past $1$ , then moves $5$ past $2$ and $3$ . The second moves $4$ past $2$ and $3$ . The third tests the remaining prefix without a swap.

Why this step? Seeing $6$ at the end initially does not alter the given algorithm: its first pass still includes the comparison with that entry.

Answer. $3$ passes and $5+4+3=12$ comparisons.

Check. Moving the $3$ one place earlier in the input reduces the number of required passes by one here; the final ordered list is unchanged.

In the worst case, all active lengths down to $2$ are used, giving $(n-1)+(n-2)+\cdots+1=n(n-1)/2$ comparisons and $O(n^2)$ . An already ordered input needs only $n-1$ comparisons in its first, no-swap pass: best-case order $O(n)$ . These counts are not separate printed formulae in the booklet; derive them from the supplied instructions.

Watch out

Wrong: $p$ passes on $n$ entries always use $p(n-1)$ comparisons. Right: the active list shrinks, so the comparison counts begin $n-1,n-2,n-3,\ldots$ . Include a terminating no-swap pass when the rule requires one.

The next input reaches its ordered state before the algorithm is entitled to stop.

Shuttle sort and an ordered prefix

Shuttle sort grows an ordered prefix at the left, inserting one new entry into it during each pass.

On pass $1$ , compare the second entry with the first. On pass $2$ , begin with the third entry and compare it with the second. If it swaps, shuttle left and compare the moved entry with its new neighbour. Stop shuttling when a comparison needs no swap or the entry reaches the left-hand end.

Shuttle sort

Pass $r$ inserts the entry initially in position $r+1$ into the ordered first $r$ entries, using adjacent comparisons and swaps from right to left within that prefix. For a list of length $n$ , carry out $n-1$ passes. Start from the left unless specified otherwise.

The instructions are in the formula booklet. A no-swap comparison finishes the current pass; it does not end the whole sort, because later entries have not yet been inserted.

Worked example 3: increasing order

Question. Use shuttle sort to put $5,2,4,1,3$ into increasing order. Show each pass and count comparisons.

Plan. Insert the next entry into the growing ordered prefix; count the final unsuccessful comparison as well as those causing swaps.

Pass	Entry inserted	List at its end	Comparisons	Swaps
$1$	$2$	$2,5,4,1,3$	$1$	$1$
$2$	$4$	$2,4,5,1,3$	$2$	$1$
$3$	$1$	$1,2,4,5,3$	$3$	$3$
$4$	$3$	$1,2,3,4,5$	$3$	$2$

For pass $4$ , $3$ swaps past $5$ , then $4$ , then is compared with $2$ . That last comparison needs no swap.

Why this step? Count the comparison that discovers the entry is in the right place; a comparison need not cause a swap.

Answer. The ordered list is $1,2,3,4,5$ , using $4$ passes, $9$ comparisons and $7$ swaps.

Check. The prefix lengths after successive passes are $2,3,4,5$ , and each is in increasing order.

Worked example 4 changes only the requested order. Now a newly inserted entry moves left while it is larger than its neighbour.

Worked example 4: decreasing order

Question. Use shuttle sort to put the same list $5,2,4,1,3$ into decreasing order, showing every pass and counting comparisons.

Plan. Retain the pass structure but reverse the condition for a swap.

Pass	List at its end	Comparisons	Swaps
$1$	$5,2,4,1,3$	$1$	$0$
$2$	$5,4,2,1,3$	$2$	$1$
$3$	$5,4,2,1,3$	$1$	$0$
$4$	$5,4,3,2,1$	$3$	$2$

For pass $2$ , $4$ passes $2$ but stops after comparison with $5$ . For pass $4$ , $3$ passes $1$ and $2$ , then stops after comparison with $4$ .

Why this step? A pass with no swaps, such as pass $1$ , has dealt with only the next entry; shuttle sort must continue with the untouched entries.

Answer. $4$ passes, $7$ comparisons and $3$ swaps.

Check. Every adjacent pair in the final list is decreasing, and $1+2+1+3=7$ .

The worst input for inserting into increasing order is reverse order: pass $r$ needs $r$ comparisons and $r$ swaps. The total is $n(n-1)/2$ , giving $O(n^2)$ . An increasing input needs one comparison in each of the $n-1$ passes, so its best-case order is $O(n)$ . These exact counts are derived, rather than printed separately in the booklet.

Watch out

Wrong: stop shuttle sort after a pass with no swaps, as in bubble sort. Right: finish all $n-1$ insertions. Only the current shuttle stops at the first comparison that needs no swap.

An unchanged end-of-pass list can therefore be a necessary line of working.

Quick sort and simultaneous sublists

Quick sort fixes a pivot in its final place, then applies the same rule to the two sides: it is a recursive algorithm.

For increasing order, choose the first value in each active sublist unless the question specifies a different pivot. Scan that sublist from left to right, writing entries smaller than the pivot in their existing relative order, then the pivot, then entries not smaller than it, also in their existing relative order.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.03j, 7.03k - Sorting algorithms

Bubble sort and its stopping pass

Shuttle sort and an ordered prefix

Quick sort and simultaneous sublists

Continue this lesson.

Learn faster with Nova