Quick sort

Overview

Recall questions on how quick sort works, pivots and partitioning, tracing a quick sort, best, average and worst-case complexity, choosing pivots to avoid the worst case, space complexity, recursion depth, and comparing quick sort with merge sort.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe how a quick sort works, step by step.

   Model answer

   Choose one item of the list as the pivot. Partition the rest of the list so that every item smaller than the pivot is placed on its left and every item larger is placed on its right; the pivot is then in its final correct position. Apply the same procedure recursively to the sublist on the left and the sublist on the right. A sublist of zero or one item is already sorted and ends the recursion.

2. 2

   What is a pivot?

   Model answer

   The item chosen at each stage against which every other item in the current sublist is compared, in order to split that sublist into those below it and those above it. Once the partition is complete the pivot itself is in the position it will occupy in the final sorted list and never needs to move again.

3. 3

   Trace a quick sort on the list 7, 2, 9, 4, 1, taking the first item as the pivot.

   Model answer

   The pivot is 7. Items smaller are 2, 4, 1 and items larger are 9, giving 2, 4, 1 then 7 then 9, with 7 now fixed. Sort the left sublist 2, 4, 1 with pivot 2: smaller is 1, larger is 4, giving 1, 2, 4, and each single-item sublist is done. The right sublist 9 is a single item. Reassembling gives 1, 2, 4, 7, 9.

4. 4

   After a single partition, what do you know for certain?

   Model answer

   That the pivot is in its final sorted position, and that every item to its left is smaller than it while every item to its right is larger. You know nothing about the order within either of those two groups, which is why each must be sorted in turn.

5. 5

   State quick sort's best and average time complexity, and say what has to be true for them.

   Model answer

   Both are O(n log n), and both depend on the pivot splitting the sublist into two reasonably balanced halves. Each level of partitioning costs a pass over the data, and if the data halves each time there are about log n levels.

6. 6

   State quick sort's worst-case complexity and describe exactly what input causes it.

   Model answer

   O(n squared). It occurs when the pivot is repeatedly the smallest or largest item in the sublist, so the partition produces one empty sublist and one containing everything else. If the pivot is always the first item, then a list already in sorted order, or in exactly reverse order, does this: each partition removes only one item, so there are n levels of recursion each costing a full pass, giving n multiplied by n.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.