Quick Sort

Quick Sort is a highly efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy. It works by selecting a 'pivot' element and partitioning the array around it.

Algorithm Description

1. Key Components:

   • Pivot selection

   • Partitioning around pivot

   • Recursive sorting of sub-arrays

2. Key Requirements:

   • Random access to elements (array-based)

   • In-place partitioning

   • Efficient pivot selection

Implementation in Go

Standard QuickSort

func quickSort(arr []int, low, high int) {
    if low < high {
        // Find pivot element such that
        // elements smaller than pivot are on the left
        // elements greater than pivot are on the right
        pi := partition(arr, low, high)

        // Separately sort elements before and after partition
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

func partition(arr []int, low, high int) int {
    // Choose rightmost element as pivot
    pivot := arr[high]
    
    // Index of smaller element
    i := low - 1
    
    // Compare each element with pivot
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    
    // Place pivot in its correct position
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

Random Pivot Selection

func randomizedQuickSort(arr []int, low, high int) {
    if low < high {
        // Choose random pivot
        pivotIdx := low + rand.Intn(high-low+1)
        
        // Move pivot to end
        arr[pivotIdx], arr[high] = arr[high], arr[pivotIdx]
        
        // Partition and sort
        pi := partition(arr, low, high)
        randomizedQuickSort(arr, low, pi-1)
        randomizedQuickSort(arr, pi+1, high)
    }
}

Three-Way QuickSort (for duplicates)

func threeWayQuickSort(arr []int, low, high int) {
    if low >= high {
        return
    }
    
    // Partition array into three parts
    // Elements smaller than pivot
    // Elements equal to pivot
    // Elements greater than pivot
    pivot := arr[high]
    lt := low      // Elements < pivot
    i := low       // Current element
    gt := high     // Elements > pivot
    
    for i <= gt {
        if arr[i] < pivot {
            arr[lt], arr[i] = arr[i], arr[lt]
            lt++
            i++
        } else if arr[i] > pivot {
            arr[i], arr[gt] = arr[gt], arr[i]
            gt--
        } else {
            i++
        }
    }
    
    threeWayQuickSort(arr, low, lt-1)
    threeWayQuickSort(arr, gt+1, high)
}

Time Complexity: O(n log n) average case

• Best Case: O(n log n)

• Average Case: O(n log n)

• Worst Case: O(n²)

Space Complexity: O(log n)

• Due to recursive call stack

• In-place partitioning

• Can be O(n) in worst case

Characteristics

Advantages

1. Efficient for large datasets

2. In-place sorting

3. Cache-friendly

4. Parallelizable

Disadvantages

1. Unstable sort

2. O(n²) worst case

3. Not adaptive

4. Recursive nature (stack space)

Related LeetCode Problems

Easy

1. 912. Sort an Array

   • Basic quicksort implementation

   • Various pivot selection strategies

   • Time: O(n log n), Space: O(log n)

2. 905. Sort Array By Parity

   • Partition-like approach

   • Two-pointer technique

   • Time: O(n), Space: O(1)

3. 922. Sort Array By Parity II

   • Modified partitioning

   • Even-odd indexing

   • Time: O(n), Space: O(1)

Medium

1. 75. Sort Colors

   • Dutch national flag problem

   • Three-way partitioning

   • Time: O(n), Space: O(1)

2. 215. Kth Largest Element

   • QuickSelect algorithm

   • Modified quicksort

   • Time: O(n) average, Space: O(1)

3. 324. Wiggle Sort II

   • Three-way partitioning

   • Virtual indexing

   • Time: O(n), Space: O(n)

Hard

1. 4. Median of Two Sorted Arrays

   • Modified partition approach

   • Binary search concept

   • Time: O(log(min(m,n))), Space: O(1)

2. 315. Count of Smaller Numbers After Self

   • Modified merge sort/quicksort

   • Index tracking

   • Time: O(n log n), Space: O(n)

Practice Tips

1. Master the Basics:

   • Understand partitioning

   • Choose good pivots

   • Handle duplicates

   • Consider edge cases

2. Common Patterns:

   • Two-way partitioning

   • Three-way partitioning

   • QuickSelect variant

   • Hybrid approaches

3. Optimization Techniques:

   • Random pivot selection

   • Median-of-three

   • Insertion sort for small arrays

   • Tail recursion elimination

4. Implementation Tips:

   • Handle edge cases

   • Choose pivot wisely

   • Consider stack space

   • Test with various inputs

Common Variations

1. Pivot Selection:

   • First element

   • Last element

   • Random element

   • Median-of-three

2. Partitioning Schemes:

   • Lomuto partition

   • Hoare partition

   • Three-way partition

   • Dual pivot

3. Special Cases:

   • Nearly sorted arrays

   • Many duplicates

   • Small arrays

   • Linked list quicksort

Resources

1. Quicksort Visualization

2. Sedgewick's Analysis

3. QuickSort Variants