tag

#quicksort

15 pages tagged

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.5 Quick Sort

6.5 Quick Sort Quick sort is a divide and conquer sorting algorithm based on partitioning. It chooses a pivot, rearranges the array so that smaller elements go to one side and larger elements go to the other side, and then recursively sorts the two partitions. Unlike merge sort, quick sort does most of its work before the recursive calls. Problem You have an array A[0..n-1] . You want an in-place...
algorithms sorting quicksort divide-and-conquer May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Lomuto Partition Quicksort

Lomuto Partition Quicksort Lomuto partition quicksort uses a simple partition scheme based on a single boundary index. It scans the array once, moving elements smaller than the pivot to the left. It is easier to implement and reason about than Hoare partition, though it performs more swaps and comparisons in practice. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le...
algorithms sorting quicksort partition
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Quicksort

Parallel Quicksort Parallel quicksort follows the same partition based divide and conquer structure as quicksort, but executes recursive calls concurrently. The key idea is that once the partition step finishes, the left and right subarrays become independent and can be processed in parallel. Compared to parallel merge sort, this method avoids the cost of merging but introduces challenges in load balancing and pivot quality. Problem Given an array $A$ of...
algorithms sorting parallel quicksort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Pattern Defeating Quicksort

Pattern Defeating Quicksort Pattern Defeating Quicksort, often called pdqsort, is a modern quicksort variant designed to handle structured and adversarial inputs efficiently. It improves on classical quicksort by detecting patterns that lead to bad partitions and adapting its behavior. It combines fast partitioning, smart pivot selection, and fallback strategies. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$...
algorithms sorting pdqsort quicksort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Three Way String Quicksort

Three Way String Quicksort Three way string quicksort is a refinement of multikey quicksort that uses three-way partitioning to efficiently handle repeated characters. It splits the array into less than, equal to, and greater than partitions based on the character at a given position. It is one of the most practical general-purpose string sorting algorithms. Problem Given an array $A$ of strings, sort them in lexicographic order. For string $s$,...
algorithms sorting string-sorting quicksort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Block Quicksort

Block Quicksort Block quicksort is a refinement of quicksort that improves partitioning performance by operating on blocks of elements instead of one element at a time. It reduces branch misprediction and improves cache locality, which are critical for modern CPUs. The algorithm keeps the same divide and conquer structure as quicksort but replaces the standard partition step with a block based approach. Problem Given an array $A$ of length $n$,...
algorithms sorting quicksort block-partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Three Way Quicksort

Three Way Quicksort Three way quicksort extends quicksort by handling duplicate keys efficiently. Instead of partitioning into two parts, it splits the array into three regions: elements less than the pivot elements equal to the pivot elements greater than the pivot This reduces unnecessary comparisons when many elements are equal. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1]...
algorithms sorting quicksort three-way-partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Randomized Quicksort

Randomized Quicksort Randomized quicksort modifies quicksort by choosing the pivot at random. This removes dependence on input order and prevents consistently bad partitions. The algorithm retains the same structure as quicksort but replaces deterministic pivot selection with a random choice. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ Idea Instead of always choosing a fixed pivot position,...
algorithms sorting quicksort randomized
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Stable Quicksort

Stable Quicksort Stable quicksort modifies the standard quicksort to preserve the relative order of equal elements. Standard quicksort is not stable because partitioning swaps elements arbitrarily. To achieve stability, the algorithm avoids in-place swaps and instead builds ordered partitions. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ and for any equal elements $A[i] = A[j]$ with $i...
algorithms sorting quicksort stable-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Dual Pivot Quicksort

Dual Pivot Quicksort Dual pivot quicksort extends quicksort by using two pivots instead of one. It partitions the array into three regions in a single pass: elements less than the first pivot elements between the two pivots elements greater than the second pivot This approach reduces comparisons in practice and improves performance on modern hardware. It is used in standard library implementations such as Java for primitive arrays. Problem Given...
algorithms sorting quicksort dual-pivot
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Hoare Partition Quicksort

Hoare Partition Quicksort Hoare partition quicksort uses the original two pointer partition scheme introduced by Tony Hoare. It scans from both ends of the range, swaps misplaced elements, and returns a split point. Compared with Lomuto partition, Hoare partition usually performs fewer swaps and handles many inputs more efficiently. Its return value is a boundary, not necessarily the final position of the pivot. Problem Given an array $A$ of length...
algorithms sorting quicksort partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort

Quicksort Quicksort is a divide and conquer sorting algorithm. It chooses a pivot value, partitions the array so that smaller elements go before the pivot and larger elements go after it, then recursively sorts both sides. It is one of the most important practical sorting algorithms because it is fast in memory, has good cache behavior, and usually needs only logarithmic stack space. Its main weakness is that bad pivot...
algorithms sorting quicksort divide-and-conquer
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort Median of Three

Quicksort Median of Three Quicksort median of three improves pivot selection by choosing the median value among the first, middle, and last elements of the current range. This avoids some common bad cases, such as already sorted or reverse sorted arrays, where choosing the first or last element as pivot can produce highly unbalanced partitions. The algorithm keeps the same recursive structure as quicksort. Only the pivot selection step changes....
algorithms sorting quicksort pivot-selection
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Multikey Quicksort

Multikey Quicksort Multikey quicksort is a string sorting algorithm that combines quicksort partitioning with radix-style character inspection. Instead of comparing whole strings each time, it partitions strings by the character at a current depth. It is especially effective for strings with shared prefixes because it avoids repeatedly comparing characters that are already known to be equal. Problem Given an array $A$ of strings, sort the strings in lexicographic order. For...
algorithms sorting string-sorting quicksort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort Ninther

Quicksort Ninther Quicksort ninther improves pivot selection by using a stronger sampling strategy called Tukey's ninther. Instead of taking the median of three elements, it takes the median of three medians, each computed from three elements. This increases the likelihood of selecting a pivot close to the true median, which leads to more balanced partitions. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le...
algorithms sorting quicksort pivot-selection