Quick Sort Algorithm

Quick sort is a highly efficient, cache-friendly sorting algorithm that uses a partition-based divide and conquer approach. It achieves excellent average-case performance of O(n log n) with in-place sorting, making it one of the most widely used sorting algorithms in practice.

Interactive Visualization

Quick Sort Visualization

Speed: 800ms

Array Visualization

Current Focus: Subarray [0, 0]

Legend:

Normal

Pivot

Left Pointer

Right Pointer

Swapping

Partitioned

Sorted

Out of Focus

How Quick Sort Works:

• Choose Pivot: Select an element as the pivot (here: first element, Hoare scheme)

• Partition: Use two pointers from ends to rearrange elements around pivot

• Recursive Sort: Apply quick sort to left and right partitions

• In-Place: No additional arrays needed, swaps elements within original array

• Time Complexity: O(n log n) average, O(n²) worst case

• Space Complexity: O(log n) average due to recursion stack

• Not Stable: May change relative order of equal elements

• Divide & Conquer: Breaks problem into smaller subproblems

Partition-Based Strategy

Quick sort employs a partition-based strategy that selects a pivot element and rearranges the array so that elements smaller than the pivot come before it, and larger elements come after it. This partitioning creates the foundation for recursive sorting.

1. Choose Pivot

Select a pivot element (commonly the first element in the Hoare scheme)

2. Partition

Use two pointers to rearrange elements: smaller than pivot on left, larger on right

3. Recursively Sort

Apply quick sort to the left and right partitions independently

Key Insight: Hoare Partition Behavior

Unlike the Lomuto scheme, the Hoare partition does not necessarily place the pivot in its final sorted position. Instead, it guarantees that the pivot is somewhere between two partitions where all elements to the left are ≤ pivot and all elements to the right are ≥ pivot. This affects the recursive calls, which are quickSort(arr, low, p) and quickSort(arr, p + 1, high).

How Quick Sort Works

Step-by-Step Process

Base Case: If subarray has 1 or 0 elements, it's already sorted

Select Pivot: Choose an element as the pivot (first element in Hoare scheme)

Partition: Rearrange array around pivot using two-pointer technique from both ends

Divide: Recursively apply quick sort to left and right partitions

Combine: No explicit combine step needed - array is sorted in-place

The Partition Process (Hoare Scheme)

Initialize: Set left pointer i = low - 1, right pointer j = high + 1

Move Left Pointer: Increment i until arr[i] ≥ pivot

Move Right Pointer: Decrement j until arr[j] ≤ pivot

Check Crossing: If i ≥ j, return j as partition index

Swap & Continue: Otherwise, swap arr[i] with arr[j] and repeat

Example: Sorting [3, 6, 8, 10, 1, 2, 1]

Initial: [3, 6, 8, 10, 1, 2, 1] pivot = 3

Partition: [1, 2, 1, 3, 6, 8, 10] partition index = 2

Left: [1, 2, 1] includes index 2

Right: [6, 8, 10] from index 3

Continue recursively...

Pseudocode

ALGORITHM QuickSort(arr[], low, high)
BEGIN
    // Base case: single element or empty subarray
    IF low < high THEN
        // Partition the array and get partition index
        p = HoarePartition(arr, low, high)
        
        // Recursively sort left and right subarrays
        QuickSort(arr, low, p)        // Left partition (includes p)
        QuickSort(arr, p + 1, high)   // Right partition
    END IF
END

ALGORITHM HoarePartition(arr[], low, high)
BEGIN
    // Choose the leftmost element as pivot
    pivot = arr[low]
    
    // Initialize pointers
    i = low - 1
    j = high + 1
    
    WHILE true DO
        // Move left pointer until element >= pivot
        DO
            i = i + 1
        WHILE arr[i] < pivot
        
        // Move right pointer until element <= pivot
        DO
            j = j - 1
        WHILE arr[j] > pivot
        
        // If pointers crossed, partition is complete
        IF i >= j THEN
            RETURN j
        END IF
        
        // Swap elements and continue
        SWAP arr[i] WITH arr[j]
    END WHILE
END

// Alternative: Randomized Quick Sort for better average performance
ALGORITHM RandomizedQuickSort(arr[], low, high)
BEGIN
    IF low < high THEN
        // Randomly select pivot and swap with first element
        randomIndex = RANDOM(low, high)
        SWAP arr[randomIndex] WITH arr[low]
        
        // Continue with normal quicksort
        p = HoarePartition(arr, low, high)
        RandomizedQuickSort(arr, low, p)
        RandomizedQuickSort(arr, p + 1, high)
    END IF
END

Complexity Analysis

Case	Time Complexity	Space Complexity	Explanation
Best Case	O(n log n)	O(log n)	Pivot divides array into equal halves each time
Average Case	O(n log n)	O(log n)	Random pivot selection leads to balanced partitions on average
Worst Case	O(n²)	O(n)	Pivot is always smallest/largest element (poor partitioning)

Why O(n log n) Average?

• Balanced Partitions: Pivot typically divides array into reasonably equal parts
• Logarithmic Depth: On average, recursion depth is O(log n)
• Linear Partitioning: Each partition step takes O(n) time
• Mathematical Expectation: Random pivot selection ensures good average performance

Why O(n²) Worst Case?

• Unbalanced Partitions: Pivot is always the minimum or maximum element
• Linear Depth: Recursion depth becomes O(n) instead of O(log n)
• Sorted Arrays: Already sorted or reverse sorted arrays trigger worst case
• Poor Pivot Choice: Deterministic pivot selection can be exploited

Pivot Selection Impact

First Element (Hoare):
Easy to implement
Poor performance on sorted data
Used in basic implementations

Random Element:
Excellent average performance
Eliminates worst-case on sorted data
Recommended approach

Median-of-Three:
Good balance of simplicity and performance
Better than random for small arrays
Production quality

Code Examples

Here are implementations of quick sort in different programming languages. Each version uses the Hoare partition scheme with the first element as pivot, demonstrating the classic efficient in-place sorting approach.

 def partition(arr, low, high):
    """
    Partition function using Hoare partition scheme
    Returns an index such that all elements to the left are <= pivot
    and all elements to the right are >= pivot
    """
    # Choose the leftmost element as pivot
    pivot = arr[low]
    i = low - 1
    j = high + 1
    
    while True:
        # Find element greater than or equal to pivot from left
        i += 1
        while arr[i] < pivot:
            i += 1
            
        # Find element smaller than or equal to pivot from right
        j -= 1
        while arr[j] > pivot:
            j -= 1
            
        # If pointers crossed, partition is complete
        if i >= j:
            return j
            
        # Swap elements
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort(arr, low, high):
    """
    Main quick sort function using divide and conquer approach
    Time Complexity: O(n²) worst case, O(n log n) average case
    Space Complexity: O(log n) due to recursion stack
    """
    if low < high:
        # Partition the array and get the partition index
        p = partition(arr, low, high)
        
        # Recursively sort elements before and after partition
        quick_sort(arr, low, p)      # Left subarray (includes partition index)
        quick_sort(arr, p + 1, high)  # Right subarray

def quick_sort_wrapper(arr):
    """Convenience function to sort entire array"""
    if len(arr) <= 1:
        return arr
    
    # Create a copy to avoid modifying the original array
    arr_copy = arr.copy()
    quick_sort(arr_copy, 0, len(arr_copy) - 1)
    return arr_copy

def print_array(arr):
    """Helper function to print the array"""
    print(" ".join(map(str, arr)))

# Example usage
if __name__ == "__main__":
    numbers = [3, 6, 8, 10, 1, 2, 1]
    
    print("Original array:", end=" ")
    print_array(numbers)
    
    sorted_array = quick_sort_wrapper(numbers)
    
    print("Sorted array:", end=" ")
    print_array(sorted_array) 
 import java.util.Arrays;

public class QuickSort {
    
    /**
     * Partition function using Hoare partition scheme
     * Returns an index such that all elements to the left are <= pivot
     * and all elements to the right are >= pivot
     */
    public static int partition(int[] arr, int low, int high) {
        // Choose the leftmost element as pivot
        int pivot = arr[low];
        int i = low - 1;
        int j = high + 1;
        
        while (true) {
            // Find element greater than or equal to pivot from left
            do {
                i++;
            } while (arr[i] < pivot);
            
            // Find element smaller than or equal to pivot from right
            do {
                j--;
            } while (arr[j] > pivot);
            
            // If pointers crossed, partition is complete
            if (i >= j) {
                return j;
            }
            
            // Swap elements
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    /**
     * Main quick sort function using divide and conquer approach
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the partition index
            int p = partition(arr, low, high);
            
            // Recursively sort elements before and after partition
            quickSort(arr, low, p);        // Left subarray (includes partition index)
            quickSort(arr, p + 1, high);   // Right subarray
        }
    }
    
    /**
     * Convenience method to sort entire array
     */
    public static void quickSort(int[] arr) {
        if (arr.length > 1) {
            quickSort(arr, 0, arr.length - 1);
        }
    }
    
    /**
     * Helper method to print an array
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] numbers = {3, 6, 8, 10, 1, 2, 1};
        
        System.out.print("Original array: ");
        printArray(numbers);
        
        quickSort(numbers);
        
        System.out.print("Sorted array: ");
        printArray(numbers);
    }
} 
 #include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

/**
 * Partition function using Hoare partition scheme
 * @param arr The vector to partition
 * @param low Starting index
 * @param high Ending index
 * @return An index such that all elements to the left are <= pivot
 *         and all elements to the right are >= pivot
 */
int partition(vector<int>& arr, int low, int high) {
    // Choose the leftmost element as pivot
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    
    while (true) {
        // Find element greater than or equal to pivot from left
        do {
            i++;
        } while (arr[i] < pivot);
        
        // Find element smaller than or equal to pivot from right
        do {
            j--;
        } while (arr[j] > pivot);
        
        // If pointers crossed, partition is complete
        if (i >= j) {
            return j;
        }
        
        // Swap elements
        swap(arr[i], arr[j]);
    }
}

/**
 * Main quick sort function (Divide and Conquer approach)
 * @param arr The vector to be sorted
 * @param low Starting index
 * @param high Ending index
 */
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // Partition the array and get the partition index
        int p = partition(arr, low, high);
        
        // Recursively sort elements before and after partition
        quickSort(arr, low, p);        // Left subarray (includes partition index)
        quickSort(arr, p + 1, high);   // Right subarray
    }
}

/**
 * Convenience function to sort entire vector
 */
void quickSort(vector<int>& arr) {
    if (arr.size() > 1) {
        quickSort(arr, 0, arr.size() - 1);
    }
}

/**
 * Helper function to print a vector
 */
void printArray(const vector<int>& arr) {
    for (int value : arr) {
        cout << value << " ";
    }
    cout << endl;
}

int main() {
    vector<int> numbers = {3, 6, 8, 10, 1, 2, 1};
    
    cout << "Original array: ";
    printArray(numbers);
    
    quickSort(numbers);
    
    cout << "Sorted array: ";
    printArray(numbers);
    
    return 0;
} 

Practical Applications

Perfect For

• General-Purpose Sorting: Excellent average performance for most datasets
• In-Place Sorting: Minimal memory overhead with O(log n) space
• Cache-Efficient: Good locality of reference improves performance
• Large Random Datasets: Shines with unsorted, random data
• Standard Libraries: Used in many system sort implementations
• Hybrid Algorithms: Combined with insertion sort for small subarrays

Consider Alternatives When

• Worst-Case Guarantees: When O(n²) performance is unacceptable
• Stability Required: Quick sort is not stable (equal elements may be reordered)
• Already Sorted Data: Without randomization, performs poorly
• Small Arrays: Overhead may not be justified for tiny datasets
• Recursive Depth Limits: Deep recursion may cause stack overflow

Real-World Applications

Standard Libraries: C++ std::sort, Java Arrays.sort (for primitive types), .NET QuickSort, numerous database engines, operating system utilities, compiler optimizations

Optimized Variants: Introsort (introspective sort), 3-way partitioning for duplicate elements, dual-pivot quicksort, parallel quicksort implementations, quickselect for finding k-th element