tag

#order-statistics

13 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
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 › 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 ›

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 › 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 ›

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 ›

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 ›

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 ›

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 › 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