Quick Sort

Quick sort is a divide-and-conquer algorithm that picks a pivot, partitions array around it, then recursively sorts subarrays.

Algorithm Steps

1. Choose Pivot: Select an element (first, last, random, or median)
2. Partition: Rearrange so elements < pivot are left, elements > pivot are right
3. Recurse: Recursively sort left and right partitions

Visual Example

Array: [3, 6, 8, 10, 1, 2, 1]
Pivot: 10 (last element)

Partition:
[3, 6, 8, 1, 2, 1] [10]
(< pivot)            (pivot)

Recurse on left:
[3, 6, 8, 1, 2, 1]
Pivot: 1
[1] [3, 6, 8, 2] [1]

Continue until sorted: [1, 1, 2, 3, 6, 8, 10]

Lomuto Partition Scheme

public 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 int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // Choose last element as pivot
    int i = low - 1;       // Pointer for smaller elements
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    
    swap(arr, i + 1, high);  // Place pivot in correct position
    return i + 1;
}

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

Hoare Partition Scheme

More efficient, swaps fewer elements:

public void quickSortHoare(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partitionHoare(arr, low, high);
        quickSortHoare(arr, low, pivotIndex);
        quickSortHoare(arr, pivotIndex + 1, high);
    }
}

private int partitionHoare(int[] arr, int low, int high) {
    int pivot = arr[low + (high - low) / 2];
    int i = low - 1;
    int j = high + 1;
    
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        
        if (i >= j) return j;
        swap(arr, i, j);
    }
}

Randomized Quick Sort

Avoids worst-case by random pivot selection:

private int partitionRandom(int[] arr, int low, int high) {
    int random = low + (int)(Math.random() * (high - low + 1));
    swap(arr, random, high);
    return partition(arr, low, high);
}

Complexity Analysis

Quick select is a variation of quicksort that finds the kth smallest element without fully sorting the array.

Algorithm

1. Partition around pivot
2. If pivot index equals k, return pivot
3. If k < pivot index, recurse on left partition
4. If k > pivot index, recurse on right partition

Java Implementation

public int quickSelect(int[] arr, int k) {
    return quickSelect(arr, 0, arr.length - 1, k - 1);
}

private int quickSelect(int[] arr, int low, int high, int k) {
    if (low == high) return arr[low];
    
    int pivotIndex = partition(arr, low, high);
    
    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, low, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, high, k);
    }
}

Iterative Quick Select

public int quickSelectIterative(int[] arr, int k) {
    int low = 0, high = arr.length - 1;
    
    while (low <= high) {
        int pivotIndex = partition(arr, low, high);
        
        if (pivotIndex == k) {
            return arr[k];
        } else if (pivotIndex < k) {
            low = pivotIndex + 1;
        } else {
            high = pivotIndex - 1;
        }
    }
    
    throw new IllegalArgumentException("k is out of bounds");
}

Applications of Quick Select

1. Find kth largest/smallest element
2. Median finding
3. Top k elements (with partial sort)
4. Statistics (percentiles, quartiles)

Complexity

When to Use Quick Select

• Finding single element (kth smallest/largest)
• Finding median
• Don't need full sort
• Memory is limited