Quick Sort Pattern
What is the Quick Sort Pattern?
The Quick Sort pattern is a divide and conquer approach that partitions the data around a pivot element, then recursively sorts the partitions.
It's characterized by its efficient partitioning step, which divides the data into elements less than the pivot and elements greater than the pivot.
Key Steps
- Choose a Pivot: Select an element from the array as the pivot
- Partition: Rearrange the array so that elements less than the pivot come before it, and elements greater than the pivot come after it
- Recursively Sort: Apply the same process to the subarrays on the left and right of the pivot
Quick Sort Implementation
Here's an implementation of the classic quick sort algorithm:
Time and Space Complexity
Time Complexity:
Average Case: O(n log n)
Worst Case: O(n²) when the array is already sorted or nearly sorted
Best Case: O(n log n)
Space Complexity:
O(log n) for the recursion stack in the average case, O(n) in the worst case.
Application: Quick Select
The quick sort pattern can be adapted to find the kth smallest element in an array in O(n) average time:
Pattern 2: Quick Sort
Learn the partition-based pattern of divide and conquer through the quick sort algorithm and its applications.
What is the Quick Sort Pattern?
The Quick Sort pattern is a divide and conquer approach that partitions the data around a pivot element, then recursively sorts the partitions.
It's characterized by its efficient partitioning step, which divides the data into elements less than the pivot and elements greater than the pivot.
Example:
Input: [10, 7, 8, 9, 1, 5]
Choose Pivot: 5 (last element)
Partition: [1] + [5] + [10, 7, 8, 9]
Recursively Sort: Sort [1] and [10, 7, 8, 9]
Final Result: [1, 5, 7, 8, 9, 10]
Key Characteristics
In-Place Sorting
Sorts the array with minimal extra space, making it memory-efficient.
Unstable Sorting
Does not preserve the relative order of equal elements, unlike merge sort.
Pivot Selection
Performance heavily depends on the choice of pivot. Poor pivot selection can lead to worst-case performance.
Cache Efficiency
Good cache performance due to in-place operations and locality of reference.
The Three Steps of Quick Sort
1Choose a Pivot
Select an element from the array as the pivot. Common choices include the first element, the last element, the middle element, or a random element.
2Partition
Rearrange the array so that elements less than the pivot come before it, and elements greater than the pivot come after it. The pivot is now in its final sorted position.
3Recursively Sort
Apply the same process to the subarrays on the left and right of the pivot. If a subarray has only one element or is empty, it's already sorted (base case).
Quick Sort Implementation
Here's an implementation of the classic quick sort algorithm:
123456789101112131415161718192021222324252627282930313233343536373839function quickSort(arr, low = 0, high = arr.length - 1) { if (low < high) { // Partition the array and get the pivot index const pivotIndex = partition(arr, low, high); // Recursively sort the subarrays quickSort(arr, low, pivotIndex - 1); // Sort left subarray quickSort(arr, pivotIndex + 1, high); // Sort right subarray } return arr;} function partition(arr, low, high) { // Choose the rightmost element as the pivot const pivot = arr[high]; // Index of the smaller element let i = low - 1; // Traverse through all elements // compare each element with the pivot for (let j = low; j < high; j++) { // If current element is smaller than or equal to the pivot if (arr[j] <= pivot) { // Increment index of smaller element i++; // Swap elements [arr[i], arr[j]] = [arr[j], arr[i]]; } } // Swap the pivot element with the element at (i + 1) // This puts the pivot in its correct sorted position [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Return the pivot's index return i + 1;}Key Insight: The partition function is the heart of the algorithm. It rearranges the array so that elements less than the pivot come before it, and elements greater than the pivot come after it. The pivot is then placed in its final sorted position.
Time and Space Complexity
Time Complexity
Average Case: O(n log n)
Worst Case: O(n²) when the array is already sorted or nearly sorted
Best Case: O(n log n)
Explanation: In the average case, the pivot divides the array roughly in half, leading to O(log n) levels of recursion with O(n) work at each level. In the worst case, if the pivot is always the smallest or largest element, there will be O(n) levels of recursion.
Space Complexity
O(log n) for the recursion stack in the average case, O(n) in the worst case.
Explanation: The space complexity is determined by the depth of the recursion stack. In the average case, the recursion depth is O(log n), but in the worst case, it can be O(n).
Advantages and Disadvantages
Advantages
- In-place sorting (minimal extra space)
- Good cache performance due to locality of reference
- Often faster than merge sort in practice
- Can be optimized with various pivot selection strategies
Disadvantages
- Unstable sorting algorithm (doesn't preserve order of equal elements)
- O(n²) worst-case time complexity
- Performance depends heavily on pivot selection
- Not as predictable as merge sort
Application: Quick Select
The quick sort pattern can be adapted to find the kth smallest element in an array in O(n) average time. This algorithm is called Quick Select.
1234567891011121314151617181920212223242526272829303132333435363738394041424344function quickSelect(arr, k) { // Find the kth smallest element (0-indexed) return quickSelectHelper(arr, 0, arr.length - 1, k);} function quickSelectHelper(arr, low, high, k) { // If the array contains only one element, return that element if (low === high) { return arr[low]; } // Partition the array and get the pivot index const pivotIndex = partition(arr, low, high); // If the pivot is the kth element, return it if (pivotIndex === k) { return arr[pivotIndex]; } // If k is less than the pivot index, search in the left subarray if (k < pivotIndex) { return quickSelectHelper(arr, low, pivotIndex - 1, k); } // If k is greater than the pivot index, search in the right subarray return quickSelectHelper(arr, pivotIndex + 1, high, k);} function partition(arr, low, high) { // Same partition function as in quickSort const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1;}How it works: Quick Select uses the same partitioning strategy as Quick Sort, but instead of recursively processing both sides, it only recurses into one side—the side that contains the kth element. This reduces the average time complexity from O(n log n) to O(n).