{"title":"Quick Sort","description":"","content":"Quick Sort is one of the most widely used sorting algorithms. It follows a divide-and-conquer approach, but instead of splitting the array evenly, it selects a pivot and partitions the array into elements smaller and larger than the pivot.\n\nWhen implemented well, Quick Sort achieves an average time complexity of O(n log n) and is fast in practice due to good cache locality. Its performance depends on pivot selection: poor choices can lead to O(n^2) time in the worst case.\n\n\n\n\n\nThis chapter covers how Quick Sort works, how partitioning is performed, how to choose pivots effectively, and how to implement the algorithm.\n\n---\n\n# What Is Quick Sort?\n\nQuick Sort is a divide-and-conquer sorting algorithm. Its core operation is **partitioning**:\n\n1. Pick an element from the array. Call it the **pivot**.\n2. Rearrange the array so that all elements smaller than the pivot are on the left, and all elements greater than the pivot are on the right. The pivot ends up in its correct sorted position.\n3. Recursively apply the same process to the left and right sub-arrays.\n\nAfter each partition, the pivot is in its final position and will never move again. Each recursive call places more pivots in their correct positions until the entire array is sorted.\n\n\n```mermaid\nflowchart TD\n A[\"Unsorted Array
[10, 7, 8, 9, 1, 5]\"]:::primary\n B[\"Choose Pivot: 5\"]:::secondary\n C[\"Partition Around 5\"]:::teal\n D[\"Left: [1]
All < 5\"]:::green\n E[\"Pivot: [5]
In correct position\"]:::secondary\n F[\"Right: [7, 8, 9, 10]
All > 5\"]:::red\n G[\"Recursively Sort Left\"]:::primary\n H[\"Recursively Sort Right\"]:::primary\n I[\"Sorted: [1, 5, 7, 8, 9, 10]\"]:::green\n\n A --> B\n B --> C\n C --> D\n C --> E\n C --> F\n D --> G\n F --> H\n G --> I\n H --> I\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe diagram above captures the entire algorithm: pick a pivot, partition, then recurse on each half.\n\nMerge Sort does most of its work in the merge step that combines two sorted halves. Quick Sort does most of its work in the partition step. By the time the recursion reaches its base case (sub-arrays of size 0 or 1), the array is already sorted. There is nothing left to combine.\n\n---\n\n# How It Works\n\nThe algorithm has two main components: the partition operation and the recursive driver.\n\n### The Partition Operation\n\nPartitioning is the heart of Quick Sort. There are two classic partition schemes:\n\n**Lomuto Partition Scheme** (simpler, easier to understand):\n\n- Uses the last element as the pivot\n- Maintains a boundary index `i` that tracks where the \"smaller than pivot\" region ends\n- Scans from left to right, swapping elements smaller than the pivot to the front\n- At the end, swaps the pivot into its correct position\n\n**Hoare Partition Scheme** (more efficient):\n\n- Uses the first element as the pivot\n- Uses two pointers starting from opposite ends\n- Pointers move toward each other, swapping elements that are on the wrong side\n- Performs fewer swaps on average (about three times fewer than Lomuto)\n\nThe implementation below uses Lomuto because it is easier to follow and less error-prone to implement. Hoare's scheme performs fewer swaps but is trickier to implement correctly.\n\n### Step-by-Step Process\n\nThe full Quick Sort algorithm using Lomuto partition:\n\n1. If the sub-array has fewer than 2 elements, return (base case).\n2. Select the last element as the pivot.\n3. Initialize a boundary index `i` to `low - 1`.\n4. Scan elements from `low` to `high - 1`. For each element, if it is less than or equal to the pivot, increment `i` and swap the current element with the element at index `i`.\n5. After the scan, swap the pivot (at `high`) with the element at `i + 1`.\n6. The pivot is now at index `i + 1`, which is its final sorted position.\n7. Recursively sort the sub-array to the left of the pivot.\n8. Recursively sort the sub-array to the right of the pivot.\n\n\n```mermaid\nflowchart TD\n A[\"quickSort(arr, low, high)\"]:::primary\n B{\"low < high?\"}:::secondary\n C[\"pivotIndex = partition(arr, low, high)\"]:::teal\n D[\"quickSort(arr, low, pivotIndex - 1)\"]:::primary\n E[\"quickSort(arr, pivotIndex + 1, high)\"]:::primary\n F[\"Return
(base case)\"]:::green\n\n A --> B\n B -->|Yes| C\n B -->|No| F\n C --> D\n C --> E\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe recursion tree fans out like a binary tree. In the best case (balanced partitions), the tree has log n levels, and each level does O(n) work during partitioning. That gives us O(n log n) total.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class QuickSort {\n\n public static void quickSort(int[] arr, int low, int high) {\n if (low < high) {\n int pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n }\n\n private static int partition(int[] arr, int low, int high) {\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n }\n\n int temp = arr[i + 1];\n arr[i + 1] = arr[high];\n arr[high] = temp;\n\n return i + 1;\n }\n\n public static void main(String[] args) {\n int[] arr = {10, 7, 8, 9, 1, 5};\n quickSort(arr, 0, arr.length - 1);\n System.out.println(java.util.Arrays.toString(arr));\n // Output: [1, 5, 7, 8, 9, 10]\n }\n}\n```\n\n```python\ndef quick_sort(arr, low, high):\n if low < high:\n pivot_index = partition(arr, low, high)\n quick_sort(arr, low, pivot_index - 1)\n quick_sort(arr, pivot_index + 1, high)\n\ndef partition(arr, low, high):\n pivot = arr[high]\n i = low - 1\n\n for j in range(low, high):\n if arr[j] <= pivot:\n i += 1\n arr[i], arr[j] = arr[j], arr[i]\n\n arr[i + 1], arr[high] = arr[high], arr[i + 1]\n return i + 1\n\nif __name__ == \"__main__\":\n arr = [10, 7, 8, 9, 1, 5]\n quick_sort(arr, 0, len(arr) - 1)\n print(arr)\n # Output: [1, 5, 7, 8, 9, 10]\n```\n\n```cpp\n#include \n#include \nusing namespace std;\n\nint partition(vector& arr, int low, int high) {\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n swap(arr[i], arr[j]);\n }\n }\n\n swap(arr[i + 1], arr[high]);\n return i + 1;\n}\n\nvoid quickSort(vector& arr, int low, int high) {\n if (low < high) {\n int pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n}\n\nint main() {\n vector arr = {10, 7, 8, 9, 1, 5};\n quickSort(arr, 0, arr.size() - 1);\n for (int x : arr) cout << x << \" \";\n // Output: 1 5 7 8 9 10\n return 0;\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\nfunc quickSort(arr []int, low int, high int) {\n\tif low < high {\n\t\tpivotIndex := partition(arr, low, high)\n\t\tquickSort(arr, low, pivotIndex-1)\n\t\tquickSort(arr, pivotIndex+1, high)\n\t}\n}\n\nfunc partition(arr []int, low int, high int) int {\n\tpivot := arr[high]\n\ti := low - 1\n\n\tfor j := low; j < high; j++ {\n\t\tif arr[j] <= pivot {\n\t\t\ti++\n\t\t\tarr[i], arr[j] = arr[j], arr[i]\n\t\t}\n\t}\n\n\tarr[i+1], arr[high] = arr[high], arr[i+1]\n\treturn i + 1\n}\n\nfunc main() {\n\tarr := []int{10, 7, 8, 9, 1, 5}\n\tquickSort(arr, 0, len(arr)-1)\n\tfmt.Println(arr)\n\t// Output: [1, 5, 7, 8, 9, 10]\n}\n```\n\n```csharp\nusing System;\n\npublic class QuickSort\n{\n public static void Sort(int[] arr, int low, int high)\n {\n if (low < high)\n {\n int pivotIndex = Partition(arr, low, high);\n Sort(arr, low, pivotIndex - 1);\n Sort(arr, pivotIndex + 1, high);\n }\n }\n\n private static int Partition(int[] arr, int low, int high)\n {\n int pivot = arr[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++)\n {\n if (arr[j] <= pivot)\n {\n i++;\n (arr[i], arr[j]) = (arr[j], arr[i]);\n }\n }\n\n (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);\n return i + 1;\n }\n\n public static void Main()\n {\n int[] arr = { 10, 7, 8, 9, 1, 5 };\n Sort(arr, 0, arr.Length - 1);\n Console.WriteLine(string.Join(\", \", arr));\n // Output: 1, 5, 7, 8, 9, 10\n }\n}\n```\n\n```rust\npub struct QuickSort;\n\nimpl QuickSort {\n pub fn quick_sort(arr: &mut Vec, low: i32, high: i32) {\n if low < high {\n let pivot_index = Self::partition(arr, low, high);\n Self::quick_sort(arr, low, pivot_index - 1);\n Self::quick_sort(arr, pivot_index + 1, high);\n }\n }\n\n fn partition(arr: &mut Vec, low: i32, high: i32) -> i32 {\n let pivot = arr[high as usize];\n let mut i = low - 1;\n\n for j in low..high {\n if arr[j as usize] <= pivot {\n i += 1;\n arr.swap(i as usize, j as usize);\n }\n }\n\n arr.swap((i + 1) as usize, high as usize);\n i + 1\n }\n}\n\nfn main() {\n let mut arr = vec![10, 7, 8, 9, 1, 5];\n let len = arr.len() as i32;\n QuickSort::quick_sort(&mut arr, 0, len - 1);\n println!(\"{:?}\", arr);\n // Output: [1, 5, 7, 8, 9, 10]\n}\n```\n\n```javascript\nfunction quickSort(arr, low, high) {\n if (low < high) {\n const pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n}\n\nfunction partition(arr, low, high) {\n const pivot = arr[high];\n let i = low - 1;\n\n for (let j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n }\n\n [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];\n return i + 1;\n}\n\nconst arr = [10, 7, 8, 9, 1, 5];\nquickSort(arr, 0, arr.length - 1);\nconsole.log(arr);\n// Output: [1, 5, 7, 8, 9, 10]\n```\n\n```typescript\nfunction quickSort(arr: number[], low: number, high: number): void {\n if (low < high) {\n const pivotIndex = partition(arr, low, high);\n quickSort(arr, low, pivotIndex - 1);\n quickSort(arr, pivotIndex + 1, high);\n }\n}\n\nfunction partition(arr: number[], low: number, high: number): number {\n const pivot = arr[high];\n let i = low - 1;\n\n for (let j = low; j < high; j++) {\n if (arr[j] <= pivot) {\n i++;\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n }\n\n [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];\n return i + 1;\n}\n\nconst arr: number[] = [10, 7, 8, 9, 1, 5];\nquickSort(arr, 0, arr.length - 1);\nconsole.log(arr);\n// Output: [1, 5, 7, 8, 9, 10]\n```\n\n\nThe partition function does the real work: it places the pivot in its correct position and returns that index. The quickSort function handles the recursion.\n\n---\n\n# Example Walkthrough\n\nTrace Quick Sort on the array `[10, 7, 8, 9, 1, 5]`.\n\n### First Call: quickSort(arr, 0, 5)\n\nThe pivot is `arr[5] = 5`. The Lomuto partition runs with `i = -1`.\n\n\n```shell\nInitial: [10, 7, 8, 9, 1, 5] pivot = 5, i = -1\n\nj=0: arr[0]=10 > 5 -> skip i=-1\nj=1: arr[1]=7 > 5 -> skip i=-1\nj=2: arr[2]=8 > 5 -> skip i=-1\nj=3: arr[3]=9 > 5 -> skip i=-1\nj=4: arr[4]=1 <= 5 -> i=0, swap arr[0] and arr[4] i=0\n Array: [1, 7, 8, 9, 10, 5]\n\nSwap pivot into position: swap arr[1] and arr[5]\n Array: [1, 5, 8, 9, 10, 7]\n Pivot index = 1\n```\n\n\nAfter partition, `5` is in its correct sorted position at index 1. Everything to its left (`[1]`) is smaller, and everything to its right (`[8, 9, 10, 7]`) is larger.\n\n### Second Call: quickSort(arr, 0, 0)\n\nThe left sub-array is `[1]`. A single element is already sorted. Base case, return.\n\n### Third Call: quickSort(arr, 2, 5)\n\nThe sub-array is `[8, 9, 10, 7]`. The pivot is `arr[5] = 7`.\n\n\n```shell\nSub-array indices 2-5: [8, 9, 10, 7] pivot = 7, i = 1\n\nj=2: arr[2]=8 > 7 -> skip i=1\nj=3: arr[3]=9 > 7 -> skip i=1\nj=4: arr[4]=10 > 7 -> skip i=1\n\nSwap pivot into position: swap arr[2] and arr[5]\n Array: [1, 5, 7, 9, 10, 8]\n Pivot index = 2\n```\n\n\nNow `7` is in its correct position at index 2.\n\n### Fourth Call: quickSort(arr, 3, 5)\n\nThe sub-array is `[9, 10, 8]`. The pivot is `arr[5] = 8`.\n\n\n```shell\nSub-array indices 3-5: [9, 10, 8] pivot = 8, i = 2\n\nj=3: arr[3]=9 > 8 -> skip i=2\nj=4: arr[4]=10 > 8 -> skip i=2\n\nSwap pivot into position: swap arr[3] and arr[5]\n Array: [1, 5, 7, 8, 10, 9]\n Pivot index = 3\n```\n\n\nNow `8` is at index 3.\n\n### Fifth Call: quickSort(arr, 4, 5)\n\nThe sub-array is `[10, 9]`. The pivot is `arr[5] = 9`.\n\n\n```shell\nSub-array indices 4-5: [10, 9] pivot = 9, i = 3\n\nj=4: arr[4]=10 > 9 -> skip i=3\n\nSwap pivot into position: swap arr[4] and arr[5]\n Array: [1, 5, 7, 8, 9, 10]\n Pivot index = 4\n```\n\n\nBoth remaining sub-arrays (`[]` and `[10]`) are base cases.\n\n**Final sorted array: **`[1, 5, 7, 8, 9, 10]`\n\nEach partition places exactly one element (the pivot) in its final position. After enough partitions, every element has been placed correctly.\n\n\n```mermaid\nflowchart TD\n A[\"[10, 7, 8, 9, 1, 5]
pivot = 5\"]:::primary\n B[\"[1]\"]:::green\n C[\"[5]\"]:::secondary\n D[\"[8, 9, 10, 7]
pivot = 7\"]:::primary\n E[\"[]\"]:::green\n F[\"[7]\"]:::secondary\n G[\"[9, 10, 8]
pivot = 8\"]:::primary\n H[\"[]\"]:::green\n I[\"[8]\"]:::secondary\n J[\"[10, 9]
pivot = 9\"]:::primary\n K[\"[10]\"]:::green\n L[\"[9]\"]:::secondary\n\n A --> B\n A --> C\n A --> D\n D --> E\n D --> F\n D --> G\n G --> H\n G --> I\n G --> J\n J --> K\n J --> L\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram shows the recursion tree. Orange nodes are pivots that have been placed in their final positions. Green nodes are base cases. Blue nodes are sub-arrays that still need sorting.\n\n---\n\n# Complexity Analysis\n\n\n| Case | Time Complexity | Space Complexity | Explanation |\n|------|----------------|------------------|-------------|\n| **Best** | O(n log n) | O(log n) | Pivot always splits array into two equal halves |\n| **Average** | O(n log n) | O(log n) | Expected performance with random input |\n| **Worst** | O(n^2) | O(n) | Pivot is consistently the smallest or largest element (for example, last-element pivot on a sorted array) |\n\n\n### Why O(n log n) on Average?\n\nEach partition step does O(n) work, scanning through the sub-array once. The key question is: how many levels of recursion are there?\n\nWhen the pivot splits the array roughly in half each time, the recursion depth is log n. Each level does a total of O(n) work across all partitions at that level. So the total work is O(n) * O(log n) = O(n log n).\n\n### Why O(n^2) in the Worst Case?\n\nThe worst case happens when the partition is maximally unbalanced. If the pivot is always the smallest or largest element, one partition gets n-1 elements and the other gets 0 elements. This creates n levels of recursion instead of log n, and each level still does O(n) work. The total becomes O(n) * O(n) = O(n^2).\n\nWhen does this happen? The classic scenario: the array is already sorted (ascending or descending), and you always pick the first or last element as the pivot. Every partition produces the worst possible split.\n\n### Space Complexity\n\nQuick Sort sorts in-place, so it does not allocate extra arrays. However, it uses the call stack for recursion. In the best case, the recursion depth is O(log n). In the worst case, it is O(n), which can cause a stack overflow on very large sorted arrays.\n\n### Stability\n\nQuick Sort is **not stable**. The partition step swaps elements across long distances, and an equal element can be moved past another equal element that originally appeared before it.\n\nFor example, with the array `[3a, 1, 3b, 2]` and pivot `2` (Lomuto, last element), the partition first moves `1` to the front, then swaps the pivot `2` into position, producing `[1, 2, 3b, 3a]`. The original `3a, 3b` order is reversed.\n\nA stable variant is possible by partitioning into separate buffers and concatenating them, but this gives up the O(1) auxiliary-space property. Production implementations that need stability use merge sort or TimSort instead.\n\n\n```mermaid\nflowchart LR\n subgraph Best[\"Best Case: O(log n) depth\"]\n direction TB\n A1[\"n\"]:::primary\n A2[\"n/2\"]:::primary\n A3[\"n/2\"]:::primary\n A4[\"n/4\"]:::teal\n A5[\"n/4\"]:::teal\n A1 --> A2\n A1 --> A3\n A2 --> A4\n A2 --> A5\n end\n\n subgraph Worst[\"Worst Case: O(n) depth\"]\n direction TB\n B1[\"n\"]:::red\n B2[\"n-1\"]:::red\n B3[\"n-2\"]:::red\n B4[\"n-3\"]:::red\n B1 --> B2\n B2 --> B3\n B3 --> B4\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe left tree shows balanced partitions (best case), where the depth is log n. The right tree shows unbalanced partitions (worst case), where the depth is n. Pivot selection determines which shape the recursion takes.\n\n---\n\n# When to Use Quick Sort\n\n### Good Fit\n\n- **General-purpose sorting**: With no specific constraints, Quick Sort is a reasonable default.\n- **Memory-constrained environments**: Quick Sort works in-place with O(log n) stack space, unlike Merge Sort which needs O(n) extra memory.\n- **Cache-friendly workloads**: Quick Sort operates on contiguous memory, which benefits from CPU cache locality. This is a major reason it outperforms Merge Sort in practice despite both being O(n log n).\n- **Average case performance matters more than worst case**: With non-adversarial data and randomized pivot selection, the average case dominates.\n\n### Not Ideal For\n\n- **Worst case sensitive applications**: For real-time systems or adversarial inputs where O(n^2) is unacceptable, use Merge Sort or Heap Sort, which guarantee O(n log n).\n- **Stability required**: Quick Sort is not stable. Use Merge Sort when equal elements must preserve their original order.\n- **Linked lists**: Quick Sort's advantage comes from in-place array operations and cache locality. On linked lists, these advantages vanish. Merge Sort is the better choice for linked lists because it does not need random access.\n- **Small arrays**: For very small arrays (less than 10-20 elements), Insertion Sort is faster due to lower overhead. Optimized Quick Sort implementations switch to Insertion Sort for small sub-arrays.\n\n### Pivot Selection Strategies\n\nPivot selection has a large effect on performance. A poorly chosen pivot leads to O(n^2), while a well chosen one keeps the algorithm at O(n log n).\n\n**1. Last or First Element (Naive)** Simple to implement, but it degrades to O(n^2) on sorted or nearly sorted data, which is a common input shape.\n\n**2. Random Pivot** Pick a random element and swap it with the last element before partitioning. This makes the worst case very unlikely, though not impossible. The expected time complexity is O(n log n) regardless of input order.\n\n**3. Median-of-Three** Pick the median of the first, middle, and last elements. This avoids the worst case on sorted data and performs well in practice. The C++ STL `std::sort` (introsort) uses median-of-three for pivot selection.\n\nThe table below summarizes the trade-offs:\n\n\n| Strategy | Worst Case Input | Implementation Effort | Used In Practice |\n|----------|-----------------|----------------------|------------------|\n| First/Last element | Sorted arrays | Trivial | Rarely |\n| Random pivot | Very unlikely | Easy | Often |\n| Median-of-three | Very unlikely | Moderate | Standard libraries |\n\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium