Quick Sort

Quick Sort is a popular divide and conquer sorting algorithm. It picks a pivot, partitions the array so that elements < pivot go to the left and elements > pivot go to the right, then recursively sorts both halves.

Algorithm

1. Pick a pivot.
2. Partition: Rearrange the array so elements < pivot go left and elements > pivot go right.
3. Recursively quicksort the left and right halves.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

Lomuto Partition (In-Place)

def quicksort(arr, low, high):
    if low < high:
        pivot_idx = partition(arr, low, high)
        quicksort(arr, low, pivot_idx - 1)
        quicksort(arr, pivot_idx + 1, high)

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

Hoare Partition

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1

    while True:
        i += 1
        while arr[i] < pivot:
            i += 1

        j -= 1
        while arr[j] > pivot:
            j -= 1

        if i >= j:
            return j

        arr[i], arr[j] = arr[j], arr[i]

Example

data = [10, 7, 8, 9, 1, 5]
quicksort(data, 0, len(data) - 1)
print(data)  # [1, 5, 7, 8, 9, 10]

Visualization

[10, 7, 8, 9, 1, 5]   pivot = 5
 Partition: [1, 5, 8, 9, 10, 7]  (simplified)

[1, 5] [8, 9, 10, 7]
        Partition again
[1, 5] [7, 9, 10, 8]
        [7] [8, 10, 9]
             [8] [9, 10]
                  [9] [10]

Result: [1, 5, 7, 8, 9, 10]

Time Complexity

The worst case occurs when the pivot is always the smallest/largest element (data already sorted).

Optimization

import random

def quicksort_optimized(arr, low, high):
    if low < high:
        # Random pivot to avoid the worst case
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]

        pivot_idx = partition(arr, low, high)
        quicksort_optimized(arr, low, pivot_idx - 1)
        quicksort_optimized(arr, pivot_idx + 1, high)

Quick Sort vs Merge Sort

Quick Sort is fast in practice. Insertion Sort is better for small data.