tag

#selection

38 pages tagged

Wiki › Algorithms › 01. Searching and Sorting ›

5. Selection and Order Statistics

5. Selection and order statistics, 35 index slug name 116 quickselect Quickselect 117 randomized-quickselect Randomized Quickselect 118 deterministic-select Deterministic Select 119 median-of-medians Median of Medians 120 introselect Introselect 121 heap-select Heap Select 122 partial-sort-selection Partial Sort Selection 123 nth-element Nth Element 124 top-k-by-heap Top K by Heap 125 top-k-by-quickselect Top K by Quickselect 126 bottom-k-selection Bottom K Selection 127 streaming-top-k Streaming Top K 128 streaming-heavy-hitters Streaming Heavy Hitters 129 misra-gries...
algorithms selection order-statistics May 6, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.11 Partial Sorting

6.11 Partial Sorting Partial sorting orders only the part of the array that the caller needs. Instead of fully sorting all n elements, the algorithm produces the smallest k elements in sorted order, or arranges the array so that the first k elements are the desired subset. This is useful when a full order is wasteful. Search results, leaderboards, nearest-neighbor candidates, and reporting queries often need only the top few...
algorithms sorting partial-sort selection May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.13 Quickselect

6.13 Quickselect Quickselect finds the element that would appear at a given index if the array were sorted. It uses the same partitioning idea as quick sort, but it recurses into only one side. This makes it useful for medians, percentiles, and top k boundaries. Problem You have an array A[0..n-1] and an index k . You want the element with rank k , using zero-based indexing, without fully sorting...
algorithms sorting quickselect selection May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.12 Top k Selection

6.12 Top k Selection Top k selection finds the largest or smallest k elements without necessarily sorting the entire input. It is closely related to partial sorting, but the emphasis is selection rather than presentation. The caller may only need the set of best candidates, not their complete internal order. Problem You have an array A[0..n-1] and an integer k . You want the largest k elements, or the smallest...
algorithms sorting selection top-k heaps May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.14 Median Selection

6.14 Median Selection Median selection finds the middle value of a collection without fully sorting it. A full sort gives the median, but it also computes much more order information than the median requires. Selection algorithms avoid that extra work. Problem You have an array A[0..n-1] . You want the median value, or one of the median values, using less work than sorting the whole array. Median Definitions For an...
algorithms sorting median selection May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Largest in Stream

Kth Largest in Stream Kth Largest in Stream maintains the k-th largest value of all values seen so far. It uses a min heap of size $k$. The heap stores the current top $k$ values. The smallest value in that heap is the k-th largest value overall. Problem Given a stream of values $$ x_1, x_2, \dots, x_n $$ support two operations: add(x): insert a new value query(): return the...
algorithms selection streaming heap
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Tournament Sort

Tournament Sort Tournament sort selects elements by organizing comparisons as a tournament. Each leaf represents an input value. Internal nodes store the winner of comparing their children. For ascending order, the winner is the smaller value. After the minimum is emitted, its leaf is replaced by infinity, and the path from that leaf to the root is recomputed. The next root gives the next smallest value. Problem Given a sequence...
algorithms sorting tournament-sort selection
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Fraction

Kth Smallest Fraction Kth Smallest Fraction selects the k-th smallest value among fractions of the form: $$ \frac{A[i]}{A[j]} $$ where the array $A$ is sorted and: $$ 0 \le i < j < n $$ This problem appears in number theory and ranking problems. Direct enumeration gives $O(n^2)$ fractions, which is too large. Problem Given a sorted array $A$ of positive integers and an integer $k$, return the k-th smallest...
algorithms selection fractions heap binary-search
Wiki › Algorithms › 01. Searching and Sorting › 1. Linear and Sequential Search ›

Second Minimum

Second Minimum Search Second minimum search finds the element that is strictly larger than the minimum and as small as possible. It extends minimum search by tracking two candidates. This is useful in ranking, selection, and tournament based algorithms. Problem Given a sequence $A$ of length $n$, find an index $i$ such that $$ A[i] = \min {, A[j] \mid A[j] > \min(A) ,} $$ If no such element exists,...
algorithms searching selection
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Nth Element

Nth Element Nth Element rearranges an array so that the element at index $k$ is exactly the element that would appear at that position in a fully sorted array. All elements before index $k$ are less than or equal to it, and all elements after are greater than or equal to it. The order within those partitions is not sorted. This is a partition based selection primitive widely used in...
algorithms selection nth-element partition
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Introselect

Introselect Introselect is a hybrid selection algorithm. It starts with Quickselect for speed and switches to a worst-case linear method when recursion becomes too deep. This design mirrors Introsort. The goal is to keep the fast average behavior of Quickselect while guaranteeing linear worst-case time. Problem Given an array $A$ and integer $k$, find the k-th smallest element with both practical efficiency and worst-case guarantees. Algorithm Run Quickselect with a...
algorithms selection introselect hybrid
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Lower Median

Lower Median Selection Lower Median Selection returns the lower median of a sequence. For even length arrays, there are two central elements. The lower median is the smaller of the two. This definition is common in discrete settings where a single representative element must be chosen. Problem Given an array $A$ of length $n$, return the element with rank: $$ k = \left\lfloor \frac{n - 1}{2} \right\rfloor $$ That is:...
algorithms selection median order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Quickselect

Top K by Quickselect Top K by Quickselect finds the $k$ largest elements by partitioning the array so that the top $k$ elements occupy one side. It uses the same idea as Quickselect, but returns a set instead of a single element. This method is faster than heap-based approaches when the data is in memory and only a single pass with partitioning is needed. Problem Given an array $A$ of...
algorithms selection top-k quickselect
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Tournament Tree Partial Sort

Tournament Tree Partial Sort Tournament tree partial sort uses a tournament tree to repeatedly extract the next smallest or largest element. It is useful when only a sorted prefix of length ( k ) is needed. You use it when you want partial sorted output with predictable comparison structure. Problem Given an array ( A ) of length ( n ) and an integer ( k ), output the smallest...
algorithms sorting selection partial-sort tournament-tree
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Heavy Hitters

Streaming Heavy Hitters Streaming Heavy Hitters finds items that occur frequently in a stream. The stream may be too large to store, so the algorithm keeps only a compact summary. The usual goal is to report all values whose frequency is above a threshold, or to estimate the most frequent values. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ find items whose frequency is large compared with $n$....
algorithms selection streaming heavy-hitters frequency
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest in Two Sorted Arrays

Kth Smallest in Two Sorted Arrays Kth Smallest in Two Sorted Arrays selects an element from the sorted union of two arrays without explicitly merging them. The main idea is to discard prefixes that cannot contain the answer. Since both arrays are sorted, comparing middle candidates lets us remove many elements at once. Problem Given two sorted arrays $A$ and $B$, and a zero-based rank $k$, return the k-th smallest...
algorithms selection sorted-arrays binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Bottom K Selection

Bottom K Selection Bottom K Selection returns the $k$ smallest elements of an array. It is symmetric to Top K selection and can be implemented with heaps or partition based methods. The result may be unordered unless explicitly sorted. Problem Given an array $A$ of length $n$ and an integer $k$, return the $k$ smallest elements. Algorithm Heap Based Maintain a max heap of size $k$. bottom_k_heap(A, k): H =...
algorithms selection bottom-k order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Pair Distance

Kth Smallest Pair Distance Kth Smallest Pair Distance finds the k-th smallest value among all absolute pair differences. For an array $A$, each pair $(i, j)$ with $i < j$ has distance: $$ |A[i] - A[j]| $$ Instead of generating all $O(n^2)$ distances, sort the array and binary search over possible distance values. Problem Given an array $A$ of length $n$ and a 1-based rank $k$, find the k-th smallest...
algorithms selection binary-search two-pointers
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Partial Sort

Partial Sort Partial sort places the smallest ( k ) elements of a sequence into sorted order at the front, while leaving the remaining elements unordered. It avoids the cost of a full sort when only a prefix of sorted data is needed. You use it when you care about top ( k ) elements rather than the entire ordering. Problem Given an array ( A ) of length (...
algorithms sorting partial-sort selection
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Sample Sort Selection

Sample Sort Selection Sample Sort Selection uses random sampling to approximate the position of the k-th element, then narrows the search to a smaller subarray. The idea is to avoid full partitioning of the entire array by first estimating where the target lies. Problem Given an array $A$ of length $n$ and an index $k$, find the k-th smallest element. Algorithm Take a random sample, sort it, and use it...
algorithms selection sampling approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Upper Median

Upper Median Selection Upper Median Selection returns the upper median of a sequence. For even length arrays, it chooses the larger of the two middle elements. This complements the lower median and is useful when tie-breaking must favor larger values. Problem Given an array $A$ of length $n$, return the element with rank: $$ k = \left\lfloor \frac{n}{2} \right\rfloor $$ That is: for odd $n$, the unique median for even...
algorithms selection median order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Sorted Matrix Selection

Selection in Sorted Matrix Selection in Sorted Matrix finds the k-th smallest value in a matrix where every row and every column is sorted in nondecreasing order. The matrix ordering gives enough structure to count how many values are less than or equal to a candidate. This allows binary search over the value range. Problem Given an $m \times n$ matrix $A$ such that: $$ A[i][j] \le A[i][j + 1]...
algorithms selection matrix binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Partial Sort Selection

Partial Sort Selection Partial Sort Selection finds the k-th smallest element by sorting only the first $k + 1$ smallest elements, rather than the entire array. This method is simple and often practical when you also need the smallest $k$ elements in sorted order. Problem Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element. Algorithm Rearrange the...
algorithms selection partial-sort order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Top K Sort

Top K Sort Top K sort finds the ( k ) smallest or largest elements and returns them in sorted order. Unlike full sorting, it avoids ordering the entire dataset. You use it when only the best ( k ) items matter, such as ranking, search results, or recommendation systems. Problem Given an array ( A ) of size ( n ) and integer ( k ), compute: the smallest...
algorithms sorting top-k selection
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Deterministic Select

Deterministic Select Deterministic Select finds the k-th smallest element with guaranteed linear time. It avoids bad pivot choices by constructing a pivot that ensures balanced partitioning. This algorithm is often called the Blum-Floyd-Pratt-Rivest-Tarjan selection algorithm. Problem Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element. Algorithm Divide the array into groups of five, find the median of...
algorithms selection deterministic order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 1. Linear and Sequential Search ›

Second Maximum

Second Maximum Search Second maximum search finds the element that is strictly smaller than the maximum and as large as possible. It mirrors second minimum search and tracks two candidates during a single scan. This is a basic selection primitive used in ranking and tournament style algorithms. Problem Given a sequence $A$ of length $n$, find an index $i$ such that $$ A[i] = \max {, A[j] \mid A[j] <...
algorithms searching selection
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Top K

Streaming Top K Streaming Top K maintains the largest $k$ elements of a data stream. The input does not need to fit in memory, and the algorithm can update the answer after each new value. The standard method keeps a min heap of size $k$. The smallest value in the heap is the current cutoff for membership in the top $k$. Problem Given a stream of values $$ x_1, x_2,...
algorithms selection streaming top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Subarray Sum

Kth Smallest Subarray Sum Kth Smallest Subarray Sum finds the k-th smallest value among all contiguous subarray sums. For nonnegative arrays, subarray sums have a monotone structure. This allows binary search on the answer and a sliding window count for how many subarrays have sum at most a candidate value. Problem Given an array $A$ of length $n$ with nonnegative values and a 1-based rank $k$, find the k-th smallest...
algorithms selection subarray-sum binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Weighted Median

Weighted Median Weighted Median generalizes the ordinary median by assigning a nonnegative weight to each element. Instead of balancing the number of elements on both sides, it balances the total weight. An element is a weighted median if the total weight of smaller elements is at most half of the total weight, and the total weight of larger elements is also at most half. Problem Given pairs $$ (x_1, w_1),...
algorithms selection weighted-median order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Order Statistic Tree Select

Order Statistic Tree Select Order Statistic Tree Select finds the element with rank $k$ in a balanced binary search tree. The tree stores one extra field at each node: the size of its subtree. With subtree sizes, selection becomes a guided walk from the root. At each node, compare $k$ with the size of the left subtree. Problem Given a binary search tree node $root$ and an integer $k$, return...
algorithms selection order-statistics trees
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Randomized Quickselect

Randomized Quickselect Randomized Quickselect improves Quickselect by choosing the pivot uniformly at random. This removes dependence on input order and avoids pathological worst cases in practice. The structure remains identical to Quickselect. Only pivot selection changes. Problem Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element. Algorithm At each step, select a random pivot, partition, and recurse...
algorithms selection randomized quickselect
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Heap Select

Heap Select Heap Select finds an order statistic by using a heap to keep only the part of the input that can still contain the answer. For the k-th smallest element, it is common to keep a max heap of size $k + 1$. The heap stores the smallest values seen so far. Whenever a new value is smaller than the heap maximum, the maximum is removed and the new...
algorithms selection heap order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Heap

Top K by Heap Top K by Heap finds the largest or smallest $k$ elements without sorting the whole input. It keeps a heap of size $k$ and discards values that cannot belong to the final answer. For the $k$ largest elements, use a min heap. The heap root is the smallest value among the current candidates. When a new value is larger than the root, replace the root. Problem...
algorithms selection top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Quickselect

Quickselect Quickselect finds the k-th smallest element in an unsorted array. It uses the same partition idea as Quicksort but only recurses into one side, which reduces work. You use it when you need a single order statistic such as median, top-k, or percentile, without fully sorting the array. Problem Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, find a value...
algorithms selection quickselect order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Multi Selection

Multi Selection Multi Selection finds several order statistics at once. Instead of running selection repeatedly for each rank, it reuses partition results to reduce total work. This is useful when you need multiple quantiles, percentiles, or split points. Problem Given an array $A$ of length $n$ and a sorted list of ranks: $$ k_1 < k_2 < \dots < k_m $$ find all corresponding elements. Algorithm Use a recursive partitioning...
algorithms selection multi-selection order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Lazy Selection Sort

Lazy Selection Sort Lazy selection sort produces sorted output incrementally. Instead of sorting the entire array, it finds the next smallest element only when requested. You use it when you need a few smallest elements or when output is consumed step by step. Problem Given an array ( A ), support an operation: next() that returns the next smallest element without sorting the entire array in advance. Idea Keep track...
algorithms sorting selection lazy partial-sort
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Median of Medians

Median of Medians Median of Medians is a pivot selection method for deterministic linear-time selection. It chooses a pivot that is good enough to discard a constant fraction of the input after partitioning. The method is most often used inside Deterministic Select. It gives worst-case guarantees, but it has larger constant factors than randomized pivot selection. Problem Given an array $A$, choose a pivot value that is close enough to...
algorithms selection median-of-medians order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Order Statistic Tree Rank

Order Statistic Tree Rank Order Statistic Tree Rank computes how many keys are smaller than a given key. It uses a binary search tree where each node stores the size of its subtree. This operation is the inverse of Order Statistic Tree Select. Select maps a rank to a key. Rank maps a key to its position in sorted order. Problem Given an order statistic tree and a key $x$,...
algorithms selection order-statistics trees