Foundation · Module 4 · Lesson 5
Quick Sort & Quickselect
Partition around a pivot and recurse selectively.
Lesson 23 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Quick Sort
Partition around a pivot and recurse
Input size
6
Active cells
2
Fixed pivots
0
Progress
1/21
Why this step happens
8 remains in the > pivot region.
Indexes 0…-1 are ≤ 1; indexes 0…-1 are > 1.
Theory lesson · Step-by-step
Understand Quick Sort & Quickselect
Partition around a pivot and recurse selectively.
Worked approach
Trace the reasoning step by step
- 1Choose a pivot.
- 2Partition values around it.
- 3For Quick Sort, recurse into both sides.
- 4For Quickselect, recurse only into the side containing rank k.
Concrete example
Partition [4, 1, 3, 2] around pivot 3.
- 1Move values < 3 left: [1,2].
- 2Place pivot after them.
- 3Values > 3 remain right: [4].
Pivot 3 reaches its final rank; quickselect recurses into only one side.
What must remain true (Loop Invariant)
After partitioning, values left of the pivot satisfy the left condition and values right satisfy the right condition.
Cost Model
Complexity & Trade-offs
When to use it
- Creating order before searching, grouping, deduplicating, or scanning.
- Selecting records using stability, memory, and input-shape constraints.
- Turning pairwise decisions into monotonic scans.
Common mistakes
- Comparing time alone while ignoring stability and auxiliary memory.
- Breaking duplicate order when stability is required.
- Quoting average performance without worst-case behavior.
Practice prompts
- Reproduce the worked Quick Sort & Quickselect example without looking at the trace.
- Change one input condition and explain whether the Quick Sort & Quickselect invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check