DAA 15_quick_sort Divide & Conquer

Quick Sort — Classic & Randomised (One Page)

Quick Sort picks a pivot, partitions the array into ≤ pivot and > pivot, then recursively sorts both sides. Typical time is O(n log n), but worst-case is O(n²) (often due to bad deterministic pivot choices).

Visualizer
Step: 0 / 0
Smaller ms = faster (e.g., 120 fast, 1000 slow).
Classic: pivot strategy can be chosen (may cause worst-case on some inputs).
In Randomised variant, pivot is forced to Random for every recursion call.
Legend Active Range pivot i = storeIndex j = scanner fixed pivot
Ops: 0
l, r
—
pivot (idx:value)
—
i, j
—
comp / swaps
0 / 0
Explain
Enter an array, pick Variant, then Start. Use Step to walk through partitioning and recursion.
Pseudocode (Classic Quick Sort)
Highlighted line matches the current step.
Note: partition(A, l, r) is treated as a black box here. It rearranges the subarray so that values ≤ pivot go left, values > pivot go right, and returns the final pivot index k. (Detailed partition steps are covered in the Partition module.)
Time & Space (Quick Look)
Best / Avg: O(n log n)
Balanced partitions (typical case)
Worst: O(n²)
Can occur if partitions are highly unbalanced
Space: O(log n) avg, O(n) worst
Recursion depth
Tip: Try an already sorted array with pivot = last to observe deep recursion (worst-case for some deterministic choices).
Why Randomised Quick Sort Helps
When randomisation is better
  • Bad input patterns for deterministic pivots: already sorted, reverse sorted, nearly sorted, or repeated patterns.
  • Adversarial inputs: when data order might be crafted to trigger worst-case partitions.
  • Unknown / unpredictable distributions: random pivots reduce dependency on input order.
Key takeaway
Randomised Quick Sort keeps the same worst-case O(n²) in theory, but makes it very unlikely in practice. The expected running time becomes Θ(n log n) because partitions are balanced on average.