Quick Sort

Implement the quick sort algorithm using divide-and-conquer approach with pivot partitioning.

Problem Overview

The Performance Champion

Quick Sort is the go-to sorting algorithm for speed! Despite its worst-case O(n²) complexity, its average O(n log n) performance and excellent cache locality make it the default choice for most practical applications.

🧠 The Pivot Strategy:

Choose Pivot: Select an element to partition around (strategy matters!)
Partition: Rearrange so smaller elements are left, larger are right
Recursively Sort: Apply same process to left and right partitions
In-Place: Sorts with minimal extra memory usage
Three Strategic Approaches:
Classic: Simple last-element pivot - easy to understand
Randomized: Random pivot selection - avoids worst-case scenarios
Iterative: Stack-based approach - prevents recursion overflow
Real-World Applications:
System Libraries: Default sort in many programming languages (C++, Java)
Database Engines: Fast sorting for query optimization
Graphics Processing: Sorting vertices and primitives efficiently
Search Algorithms: Preprocessing data for faster searches
Competitive Programming: Fast enough for tight time constraints

💡 Learning Value:

Partition-based divide-and-conquer algorithms
Pivot selection strategies and their impact
Average vs worst-case performance analysis
In-place algorithm design principles
Randomization for algorithmic improvement

Concepts

Divide and ConquerRecursionIn-place SortingPartitioningPivot Selection

Complexity Analysis

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

Space:O(log n) average, O(n) worst case

Performance Notes:

- Time: O(n log n) average, O(n²) worst case (rare with good pivot) - Space: O(log n) average, O(n) worst case (recursion stack)

Solutions

quickSort

Time: O(n log n) average, O(n²) worst | Space: O(log n) average, O(n) worst

export function quickSort(arr: number[]): number[] {
  const result = [...arr]; // Create a copy to avoid mutating input
  quickSortHelper(result, 0, result.length - 1);
  return result;
}

// Helper function for recursive sorting
function quickSortHelper(arr: number[], low: number, high: number): void {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSortHelper(arr, low, pivotIndex - 1);
    quickSortHelper(arr, pivotIndex + 1, high);
  }
}

// Partition function using Lomuto partition scheme
function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high]; // Choose last element as pivot
  let i = low - 1; // Index of smaller element
  
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Place pivot in correct position
  return i + 1;
}

// Alternative implementation with random pivot for better average performance

Examples & Test Cases

#1Sort an array of positive integers

Input:

Output:

#2Sort a smaller array

Input:

[
  5,
  2,
  8,
  1,
  9
]

Output:

[
  1,
  2,
  5,
  8,
  9
]

#3Handle duplicate elements

Input:

[
  3,
  3,
  3,
  3
]

Output:

[
  3,
  3,
  3,
  3
]

#4Sort array with negative numbers

Input:

[
  -1,
  -5,
  2,
  0,
  3
]

Output:

[
  -5,
  -1,
  0,
  2,
  3
]

#5Single element array

Input:

[
  1
]

Output:

[
  1
]

#6Empty array

Input:[]

Output:[]