All lessonsOpen Open Open Open Open
7. Sorting
Quick sort
0 of 5 activities0%
Reading 1
Pivot and partition
Quick sort picks a pivot, partitions into < pivot and > pivot, then recurses.
Average O(n log n), worst O(n^2) on bad pivots (already sorted with naive pivot). Random/median-of-three helps.
In-place-ish (log n stack). Not stable in usual form.
// partition sketch: place pivot, return indexCheck 2
Worst case
Naive quicksort on already sorted data with first/last pivot can be
Fill in 3
Key step
Try it 4
Partition example
Count how many < pivot 5.
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Count less than pivot
Read n, n ints, then pivot. Print how many elements are strictly less than pivot.
main.cpp
Loading editor…