Quick Sort
Quick sort is an efficient, in-place divide-and-conquer sorting algorithm that partitions the array around a pivot.
Intuition
Pick a "leader" (pivot). Ask everyone smaller than the leader to stand on the left, and everyone taller to stand on the right. The leader is now in their exact final spot (sorted). Repeat for the groups on the left and right.
Concept
- Partitioning: The key operation. Reorders array so elements < pivot are left, elements > pivot are right.
- Divide & Conquer: Sorts the two partitions recursively.
- In-Place: Requires minimal extra memory (O(log N) stack space) compared to Merge Sort.
How it Works
Algorithm:
- Choose a Pivot (e.g., last element).
- Traverse array: if element < Pivot, swap it to the front.
- Place Pivot after the last 'smaller' element.
- Recursively apply to left and right sub-arrays.
Step-by-Step Breakdown
Watch the visualization:
- Blue bar (PIVOT): The element used for partitioning: the last element of the current range.
- Amber bars: Elements being compared with the pivot, or about to be swapped.
- Red bars: The swap that moves a smaller element to the left, or places the pivot.
- Green bars: The whole array, once the sort completes.
When to Use
- General Purpose: Fastest sorting algorithm for randomized data on average.
- Memory Constraints: Preferred over Merge Sort when O(N) extra space is not available.
- Arrays: Better locality of reference (cache-friendly) than Heap Sort.
When NOT to Use
- Worst Case O(N²): Not suitable if data is already sorted and bad pivot choice is made (can be mitigated by randomizing pivot).
- Stable Sort Required: Quick Sort is unstable.
How to Identify
"In-place sort", "Kth Largest Element (QuickSelect)".
Applying for software engineering roles? Free, no sign-up: