Quick Sort
Quick sort is a highly efficient, in-place, divide-and-conquer sorting algorithm. It works by selecting a "pivot" element and partitioning the array so that elements less than or equal to the pivot go to the left and elements greater go to the right. It then recursively sorts each partition. With O(n log n) average-case performance and minimal memory overhead, quicksort is often the fastest general-purpose sort in practice.
How Quick Sort Works
Quick sort also follows the divide-and-conquer paradigm, but unlike merge sort, the heavy work happens in the partition step rather than the merge step. Once the array is correctly partitioned around a pivot, combining is trivial because the elements are already in their correct relative positions.
Step-by-step process:
- Choose a pivot: Select an element from the array to serve as the pivot. Common strategies include picking the last element (Lomuto partition), the first element, a random element, or the median of three. The choice of pivot affects performance on different input distributions.
- Partition: Rearrange the array so that all elements less than or equal to the pivot are on the left, and all elements greater than the pivot are on the right. The pivot is then placed in its final sorted position. This is the core operation that does O(n) work per call.
- Recurse: Apply quick sort recursively to the left partition (elements before the pivot) and the right partition (elements after the pivot).
- Base case: When a subarray has zero or one element, it is already sorted, and the recursion stops.
Quick sort's main advantage is that it sorts in-place, requiring only O(log n) stack space on average. Its average-case time complexity is O(n log n), but the worst case is O(n²) when the pivot consistently divides the array into one element and the rest (e.g., when the array is already sorted and the last element is always chosen as pivot). Randomized pivot selection or median-of-three strategies mitigate this risk in practice.
Interactive Visualization
Watch how quick sort partitions the array around a pivot element. Purple bars indicate the pivot, yellow bars show elements already placed in the left partition, orange bars highlight the element being scanned, and green bars are in their final sorted position. Dimmed bars are outside the current active partition.
Code Implementation
Below is a standard quick sort implementation using the Lomuto partition scheme (pivot is the last element). The partition function rearranges elements and returns the pivot's final index.
def quick_sort(arr, low=0, high=None):
"""In-place quick sort using Lomuto partition scheme."""
if high is None:
high = len(arr) - 1
if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
return arr
def partition(arr, low, high):
"""Lomuto partition: pivot is the last element."""
pivot = arr[high]
i = low # partition boundary
for j in range(low, high):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
# Place pivot in its correct position
arr[i], arr[high] = arr[high], arr[i]
return i
# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90, 45]
print("Unsorted:", numbers)
print("Sorted: ", quick_sort(numbers))
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Lomuto: pivot is last element
int i = low; // partition boundary
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
// Place pivot in correct position
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
public static void main(String[] args) {
int[] numbers = {64, 34, 25, 12, 22, 11, 90, 45};
System.out.print("Unsorted: ");
printArray(numbers);
quickSort(numbers, 0, numbers.length - 1);
System.out.print("Sorted: ");
printArray(numbers);
}
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) System.out.print(", ");
}
System.out.println();
}
}
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // Lomuto: pivot is last element
int i = low; // partition boundary
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[high]); // Place pivot in correct position
return i;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
void printArray(const vector<int>& arr) {
for (int i = 0; i < (int)arr.size(); i++) {
cout << arr[i];
if (i < (int)arr.size() - 1) cout << ", ";
}
cout << endl;
}
int main() {
vector<int> numbers = {64, 34, 25, 12, 22, 11, 90, 45};
cout << "Unsorted: ";
printArray(numbers);
quickSort(numbers, 0, numbers.size() - 1);
cout << "Sorted: ";
printArray(numbers);
return 0;
}
Complexity Analysis
Quick sort's performance depends heavily on pivot selection. With good pivots that split the array roughly in half, it achieves O(n log n). With poor pivots (e.g., always picking the minimum or maximum), it degrades to O(n²). Randomized pivot selection makes the worst case extremely unlikely in practice.
| Metric | Complexity | Notes |
|---|---|---|
| Best Case Time | O(n log n) | Pivot always divides the array into two equal halves |
| Average Case Time | O(n log n) | Expected performance with random data |
| Worst Case Time | O(n²) | Pivot is always the smallest or largest element (e.g., sorted input with last-element pivot) |
| Space Complexity | O(log n) | In-place partitioning; space is for the recursion stack (O(n) in worst case) |
| Stable | No | Partitioning can change the relative order of equal elements |
Quiz
Test your understanding of quick sort with these questions.
Q1. What is the worst-case time complexity of quick sort?
Q2. Which pivot selection strategy helps avoid the worst case?
Q3. Is quick sort a stable sorting algorithm?
Q4. What is the average-case space complexity of quick sort?
Q5. After one complete partition of [64, 34, 25, 12, 22, 11, 90, 45] using Lomuto (pivot = 45), what is the pivot's final index?