3.50 Quick Sort Array

3.50.1 Problem Metadata

3.50.2 Description

Sort an integer array in ascending order using the quick sort algorithm.

3.50.3 Examples

Input: [10,7,8,9,1,5]
Output: [1,5,7,8,9,10]

3.50.4 Constraints

  • 1 <= n <= 10^5
  • Elements fit in 32-bit signed integers

3.50.5 Solution - Lomuto Partitioning

3.50.5.1 Walkthrough

Quick sort picks a pivot (last element), partitions the array so values smaller than the pivot appear to its left, and recurses on both subarrays. The Lomuto partition scheme swaps each value less than the pivot into the correct region and finally places the pivot at its final index.

3.50.5.2 Analysis

  • Time Complexity: Average O(n log n); worst-case O(n^2) when pivot choices are poor
  • Space Complexity: O(log n) recursion stack

3.50.5.3 Implementation Steps

  1. Recursively sort the subarray [lo, hi].
  2. Choose arr[hi] as the pivot, partition so pivotIndex is the final pivot position.
  3. Recursively quick sort [lo, pivotIndex - 1] and [pivotIndex + 1, hi].
  4. Base case when lo >= hi.

3.50.5.4 Code - Java

public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int pivotIndex = partition(arr, lo, hi);
    quickSort(arr, lo, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, hi);
}

private int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, hi);
    return i;
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}