Quick Sort
Problem
Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
Examples:
Example 1:
Input: arr = [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]
Explanation: Quick Sort first partitions the array around a pivot (e.g., 5), then recursively sorts the subarrays [1] and [7, 8, 9, 10].
Example 2:
Input: arr = [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]
Explanation: Quick Sort efficiently sorts the array by partitioning and recursively sorting the subarrays.
Solution
Intuition
- Quick Sort is based on the divide-and-conquer paradigm, where we divide the problem into smaller subproblems, solve them independently, and then combine their solutions.
- The key process in Quick Sort is the partitioning step, where we choose a pivot element and rearrange the array so that all elements less than the pivot are to its left, and all elements greater than the pivot are to its right.
- After partitioning, the pivot is in its final sorted position, and we recursively apply the same process to the subarrays on the left and right of the pivot.
- The choice of pivot can significantly affect the algorithm's performance. Common strategies include choosing the first element, the last element, the middle element, or a random element as the pivot.
Approach
- Choose a pivot element from the array.
- Partition the array around the pivot, such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
- Recursively apply the above steps to the subarrays on the left and right of the pivot.
- The base case of the recursion is when the subarray has 0 or 1 element, which is already sorted.
Complexity Analysis
- Time Complexity: O(n log n) on average, O(n²) in the worst case (when the array is already sorted or reverse sorted and the pivot is chosen as the first or last element).
- Space Complexity: O(log n) for the recursive call stack.
Implementation
CPP
Run your code to see output here