Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Visualization
Interactive visualization for Quicksort
Animation Speed: 500ms
🟡 Yellow: Pivot | 🔵 Blue: Comparing | 🟢 Green: Sorted
Interactive visualization with step-by-step execution
Implementation
1function quickSort(arr: number[]): number[] {
2 if (arr.length <= 1) return arr;
3
4 const pivot = arr[0];
5 const left = arr.slice(1).filter(x => x <= pivot);
6 const right = arr.slice(1).filter(x => x > pivot);
7
8 return [...quickSort(left), pivot, ...quickSort(right)];
9}Deep Dive
Theoretical Foundation
Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element and partitioning the array around it. Elements smaller than the pivot move to the left, larger elements to the right. This process recursively continues on the sub-arrays until the entire array is sorted. Invented by Tony Hoare in 1959, it's widely regarded as one of the fastest sorting algorithms in practice. The key to Quick Sort's efficiency is the partition operation, which can be performed in-place with O(1) extra space. There are multiple strategies for pivot selection (first element, last element, random, or median-of-three), each with different performance characteristics. With good pivot selection, Quick Sort achieves O(n log n) average-case time complexity and is cache-friendly due to its in-place nature.
Complexity
Time
O(n log n)
O(n log n)
O(n²)
Space
O(log n)
Applications
Industry Use
Standard library sorting in C++ (std::sort), Java (Arrays.sort for primitives)
Database query optimization and indexing
Operating system task scheduling and resource allocation
Search engines for ranking results
Financial systems for transaction processing
E-commerce platforms for product sorting
Data analysis and scientific computing
Compiler optimization techniques
Use Cases
Related Algorithms
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.
Selection Sort
Selection Sort is a simple comparison-based sorting algorithm that divides the array into sorted and unsorted regions. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region. The algorithm performs the minimum number of swaps (n-1 at most), making it useful when memory writes are expensive operations.