Quick Sort Implementation

Problem Statement

Sort an array using quick sort: pick a pivot, partition the array so smaller elements come before it and larger ones after, then recursively sort each side.

Example

Input:  [10, 7, 8, 9, 1, 5]
Pivot 5 -> partition -> recurse
Output: [1, 5, 7, 8, 9, 10]

Approach

The Lomuto partition uses the last element as pivot and keeps a boundary i for elements <= pivot. After partitioning, the pivot sits in its final place. Average performance is O(n log n); the O(n^2) worst case (e.g. already-sorted input with a naive pivot) is avoided in practice by randomising or using median-of-three pivots.

Complexity

• Time: O(n log n) average, O(n^2) worst
• Space: O(log n) recursion stack

Solution Code

Python

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = _partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)
    return arr

def _partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Java

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}
int partition(int[] arr, int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
    int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
    return i + 1;
}

C++

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

Key Takeaways

• Quick sort is in-place and usually the fastest comparison sort in practice.
• Randomise the pivot to avoid the O(n^2) worst case; it is not stable.
• Reference: CLRS, Ch. 7; Wikipedia, "Quicksort".