Overview

Quick Sort is a divide-and-conquer sorting algorithm that picks a pivot element and partitions the array around the pivot. Elements smaller than the pivot are placed before it, and elements greater than the pivot are placed after it. This process is repeated recursively for the sub-arrays.

Quick Sort is one of the most widely used sorting algorithms due to its excellent average-case performance of O(n log n). However, it has a worst-case time complexity of O(n²), which occurs when the pivot is always the smallest or largest element.

How It Works

The algorithm follows these steps:

1. Choose Pivot: Select an element from the array as the pivot
2. Partition: Rearrange the array so that all elements less than the pivot come before it, and all elements greater come after it
3. Recurse: Apply the same process recursively to the sub-arrays on both sides of the pivot

The pivot selection is crucial. Common strategies include choosing the first element, last element, middle element, or a random element. The partition step ensures that after partitioning, the pivot is in its final sorted position.

Algorithm

QuickSort(arr, low, high):
    if low < high:
        pivot_index = Partition(arr, low, high)
        QuickSort(arr, low, pivot_index - 1)
        QuickSort(arr, pivot_index + 1, high)

Partition(arr, low, high):
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1
    
    for j = low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[high]
    return i + 1
                

Implementation

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)

# In-place version
def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 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
                

Complexity Analysis

• Time Complexity:
  • Best Case: O(n log n) - when pivot divides array evenly
  • Average Case: O(n log n) - expected performance
  • Worst Case: O(n²) - when pivot is always smallest/largest
• Space Complexity: O(log n) for recursion stack (average case), O(n) worst case

The worst case occurs when the array is already sorted and we always pick the first or last element as pivot. This can be avoided by using randomized pivot selection or median-of-three pivot selection.

Characteristics

• Stable: No - does not preserve relative order of equal elements
• In-place: Yes (with in-place implementation) - can be done with O(log n) extra space
• Adaptive: No - performance depends on pivot selection, not input order
• Online: No - requires the entire array to be present

When to Use Quick Sort

Quick Sort is an excellent choice when:

• Average-case performance is more important than worst-case guarantee
• You need in-place sorting with good average performance
• Stability is not required
• You can use randomized pivot selection to avoid worst-case scenarios
• General-purpose sorting where data distribution is unknown

Pivot Selection Strategies

• First/Last Element: Simple but can lead to worst-case O(n²)
• Middle Element: Better than first/last, but still can be problematic
• Random Element: Reduces probability of worst-case, good for general use
• Median-of-Three: Choose median of first, middle, and last elements - good balance

Example

Sorting [10, 7, 8, 9, 1, 5] with pivot as last element:

Initial: [10, 7, 8, 9, 1, 5]
Pivot: 5

Partition: [1, 5, 10, 7, 8, 9]
          (elements < 5) (pivot) (elements > 5)

Recurse on [1] and [10, 7, 8, 9]
[1] is sorted
[10, 7, 8, 9] with pivot 9:
  Partition: [7, 8, 9, 10]
  Recurse on [7, 8] and [10]
  Final: [1, 5, 7, 8, 9, 10]
                

Related Algorithms

Explore other sorting algorithms:

• Bubble Sort - Simple but inefficient
• Merge Sort - Guaranteed O(n log n), stable
• Heap Sort - In-place O(n log n) guarantee
• Back to Sorting Algorithms Overview