Quicksort
The pivot, Lomuto partitioning, recursion on both sides, the n log n average case, the quadratic worst case and the pivot choices that avoid it, an in-place and unstable sort.
- 25 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Quicksort: what is it?
Show the answer
A sort that arranges elements around a chosen value, smaller ones on one side and larger on the other, then repeats on each side.
The work is done on the way down, in the partition: once the pivot is in its final place, there is nothing to combine when the recursion returns.
What array results from Lomuto partitioning
[7, 2, 9, 4, 5](pivot in the last cell), and at which index is the pivot?[2, 4, 5, 7, 9], pivot at index 2[2, 4, 5, 7, 9], pivot at index 4[2, 7, 9, 4, 5], pivot at index 1[7, 2, 4, 5, 9], pivot at index 3
Show the answer
[2, 4, 5, 7, 9], pivot at index 2The pivot is 5. 2 is swapped with 7, then 4 with 7 again: [2, 4, 9, 7, 5]. The pivot is finally swapped with 9, the first larger value, giving [2, 4, 5, 7, 9] with 5 in cell 2.
Quicksort costs … on average and … in the worst case.
Show the answer
Quicksort costs O(n log n) on average and O(n²) in the worst case.
If each partition splits roughly in the middle, there are log n levels of n comparisons. If it detaches a single element, there are n levels: n + (n−1) + … + 1 comparisons.
Pivot: what is it?
Show the answer
A value chosen from the array that serves as a boundary: after partitioning, elements less than or equal to it are on its left, the larger ones on its right.
A pivot near the median splits the array into equal halves; an extreme pivot detaches a single element and degrades the sort.