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