AA7–AA9 - Sorting algorithms

AA7–AA9 - Sorting algorithms

Sorting puts a list into ascending or descending order while retaining every item. You will trace quick sort, apply another fully specified sort, count comparisons and swaps using its actual rules, and explain why those rules produce an ordered list.

Quick sort fixes pivots and sorts the sublists

Could an already sorted list be a worst-case input for a sorting algorithm? With a first-item pivot, quick sort can repeatedly make the most uneven possible split. Its work depends on the procedure as well as the appearance of the input.

You already know

Complexity counts a specified operation against a stated input size, usually in the worst case. Exact counts depend on the instructions. A procedure must retain its required output and terminate on its permitted inputs.

Quick sort chooses a pivot, partitions the remaining items around it, and repeats within the resulting sublists. A fixed pivot is not included in a later sublist.

Quick sort convention used here

Use the first item of every active sublist as its pivot. For ascending order, compare each other item once with that pivot: put smaller items on the left and greater-or-equal items on the right, preserving their order within each group. Put the pivot between the groups.

For descending order, put greater items on the left and less-or-equal items on the right. Thus an item equal to the pivot goes to its right in both versions. Empty sublists and singletons need no comparisons.

A pass here partitions every active sublist of length at least two once. Boxed values below are fixed pivots; square brackets mark sublists. Follow a question's stated pivot, equal-item and pass conventions if they differ. There is no single count independent of those choices.

Worked example 1: ascending order with a repeated value

Question. Quick-sort 7,3,7,1,5,9,27,3,7,1,5,9,2 into ascending order using the stated convention. Show the passes and count pivot comparisons.

Plan. Partition each active sublist, leaving fixed pivots out of later comparisons.

StageSublists and fixed pivotsComparisons in this pass
Input[7,3,7,1,5,9,2][7,3,7,1,5,9,2]—
Pass 11[3,1,5,2] 7 [7,9][3,1,5,2]\ \boxed{7}\ [7,9]66
Pass 22[1,2] 3 [5] 7 7 [9][1,2]\ \boxed{3}\ [5]\ \boxed{7}\ \boxed{7}\ [9]3+1=43+1=4
Pass 331 [2] 3 [5] 7 7 [9]\boxed{1}\ [2]\ \boxed{3}\ [5]\ \boxed{7}\ \boxed{7}\ [9]11

The first pivot 77 leaves the other 77 in the right-hand sublist. Pass 22 uses pivots 33 and that second 77. Pass 33 only needs to partition [1,2][1,2].

Why this step? Sorting each sublist separately avoids comparing its items with pivots that have already reached their final positions.

Answer. The sorted list is 1,2,3,5,7,7,91,2,3,5,7,7,9, using 6+4+1=116+4+1=11 pivot comparisons.

Check. All seven items, including both copies of 77, are retained. Every comparison is one non-pivot item against its own current pivot.

Change only the requested order to descending. The same first-pivot rule now uses the reversed partition comparison.

Worked example 2: descending order on the same input

Question. Quick-sort 7,3,7,1,5,9,27,3,7,1,5,9,2 into descending order and count comparisons.

Plan. Put greater values left of each pivot and less-or-equal values right, processing all active sublists per pass.

StageSublists and fixed pivotsComparisons in this pass
Input[7,3,7,1,5,9,2][7,3,7,1,5,9,2]—
Pass 11[9] 7 [3,7,1,5,2][9]\ \boxed{7}\ [3,7,1,5,2]66
Pass 22[9] 7 [7,5] 3 [1,2][9]\ \boxed{7}\ [7,5]\ \boxed{3}\ [1,2]44
Pass 33[9] 7 7 [5] 3 [2] 1[9]\ \boxed{7}\ \boxed{7}\ [5]\ \boxed{3}\ [2]\ \boxed{1}1+1=21+1=2

Why this step? Reversing the final ascending list would give the right output, but would not demonstrate the requested descending quick-sort process or its comparison count.

Answer. 9,7,7,5,3,2,19,7,7,5,3,2,1, using 6+4+2=126+4+2=12 comparisons.

Check. The same input and algorithm family can have different exact counts when the partition direction changes.

The method terminates because every partition removes a pivot from further work, leaving shorter sublists. Once those sublists are sorted, every left item is on the correct side of the pivot and every right item is on the other side, so concatenating left, pivot and right gives an ordered result. The argument also handles equal items under the stated convention.

[DIAGRAM: asset_name: Quick-sort passes retain fixed pivots; asset_slug: h645_b111_quick_passes; caption: Each pass partitions the remaining sublists and leaves earlier pivots fixed; description: Four rows show the ascending quick-sort input seven three seven one five nine two and its three pass results. Earlier fixed pivots are sage, next active pivots clay and other items blue. After pass one, seven is fixed in position five; after pass two, three and the second seven are also fixed; the final row is one two three five seven seven nine. Side labels show six four and one comparisons for the passes.]
Each pass partitions the remaining sublists and leaves earlier pivots fixed

The quick-sort rules and comparison counts are not in the formula booklet. This partition version does not specify in-place swaps, so it does not define a swap count. Count swaps only when an actual swapping procedure is given.

Watch out

Wrong: partition the whole list around just one new pivot each time, or compare later items with an earlier fixed pivot.

Right: keep the separate active sublists visible, use each sublist's own pivot, and retain repeated items.

Use a fresh list with another repeated pivot.

Follow the exact pass and stopping rule

Other sorting procedures will be specified. Here is one adjacent-swap procedure for ascending order: in each pass, compare positions 1,21,2, then the new positions 2,32,3, and continue to positions n−1,nn-1,n. Swap when the left item is greater than the right. Every pass visits all n−1n-1 adjacent pairs, including the final checking pass. Stop only when a complete pass makes no swaps.

This is a bubble-sort procedure with a full-length pass. It does not shorten later passes. Equal adjacent values are not swapped.

Comparison and swap counts

Count a comparison whenever the specified pair is tested, whether or not a swap follows. Count a swap only when the two entries are exchanged. A pass with no swaps can still perform comparisons and may be required to establish the stopping condition.

Record each completed pass and both counts. The output being visibly sorted does not remove a checking pass required by the instructions.

Worked example 3: include the checking pass

Question. Apply the given adjacent-swap sort to 4,1,3,24,1,3,2. Show each complete pass and count comparisons and swaps.

Plan. Make three adjacent comparisons in each pass and continue until one full pass has zero swaps.

The first pass changes the list through

(4,1,3,2)→(1,4,3,2)→(1,3,4,2)→(1,3,2,4)(4,1,3,2)\to(1,4,3,2)\to(1,3,4,2)\to(1,3,2,4)
PassList after the complete passComparisonsSwaps
111,3,2,41,3,2,43333
221,2,3,41,2,3,43311
331,2,3,41,2,3,43300

Why this step? Pass 22 creates the sorted list, but the stated stop condition is only confirmed by pass 33.

Answer. The sorted list is 1,2,3,41,2,3,4, with 99 comparisons and 44 swaps.

Check. There are three full passes, each with n−1=3n-1=3 comparisons. Their swap counts sum to 3+1+0=43+1+0=4.

Continue this lesson.

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

Create free account