Selection

Kth Smallest Subarray Sum

Find the k-th smallest sum among all contiguous subarrays, usually for nonnegative arrays.

Kth Smallest Pair Distance

Find the k-th smallest absolute difference among all pairs in an array.

Selection in Sorted Matrix

Select the k-th smallest element from a matrix whose rows and columns are sorted.

5. Selection and Order Statistics

Selection and order-statistics: quickselect, median-of-medians, streaming top-k, heavy hitters, reservoir sampling, and quantile summaries.

Lazy Selection Sort

Select the next smallest element on demand, avoiding full sorting until all elements are requested.

Tournament Tree Partial Sort

Use a tournament tree to extract the smallest or largest k elements in sorted order without fully sorting the input.

Top K Sort

Extract and sort the top k elements (smallest or largest) from a sequence without fully sorting it.

Partial Sort

Rearrange a sequence so that the smallest k elements appear in sorted order, without fully sorting the entire sequence.

Tournament Sort

Sort by repeatedly selecting the minimum element using a tournament tree.

Sample Sort Selection

Use sampling to approximate order statistics and refine selection efficiently.

Kth Largest in Stream

Maintain the k-th largest value while values arrive one at a time.

Kth Smallest Fraction

Select the k-th smallest fraction formed by pairs from a sorted array using heap or binary search.

Kth Smallest in Two Sorted Arrays

Select the k-th smallest element from two sorted arrays without merging them.

Multi Selection

Select multiple order statistics in one pass more efficiently than repeated selection.

Upper Median Selection

Select the upper median, the element at index floor(n/2), using selection or partitioning.

Lower Median Selection

Select the lower median, the element at index floor((n-1)/2), using selection or partitioning.

Weighted Median

Select an element whose total weight on each side is at most half of the total weight.

Order Statistic Tree Rank

Compute the sorted-order rank of a key in a search tree augmented with subtree sizes.

Order Statistic Tree Select

Select the element with a given rank from a balanced search tree augmented with subtree sizes.

Quickselect

Select the k-th smallest element in an unsorted array using partitioning.

Streaming Heavy Hitters

Find frequent items in a stream using bounded memory.

Streaming Top K

Maintain the k largest elements while values arrive one at a time.

Bottom K Selection

Select the k smallest elements using bounded structures or partitioning.

Top K by Quickselect

Find the k largest elements using partition-based selection in linear time.

Top K by Heap

Find the k largest or k smallest elements by maintaining a bounded heap.

Nth Element

Rearrange an array so that the element at position k is the same as in sorted order, with partition guarantees.

Partial Sort Selection

Select the k-th element by partially sorting only the needed prefix of the array.

Heap Select

Select the k-th smallest or largest element by maintaining a heap of candidate values.

Introselect

Hybrid selection algorithm that combines Quickselect with worst-case fallback.

Median of Medians

Choose a pivot with guaranteed quality by taking the median of group medians.

Deterministic Select

Selection algorithm with guaranteed linear time using structured pivot choice.

Randomized Quickselect

Quickselect with random pivot selection to achieve robust expected linear time.

Second Maximum Search

Find the second largest element in a sequence.

Second Minimum Search

Find the second smallest element in a sequence.

6.14 Median Selection

Find the middle value of a collection in linear time using selection algorithms, without the overhead of a full sort.

6.13 Quickselect

Find the element at a given rank using quicksort's partition step but recursing into only one side, achieving expected linear time.

6.12 Top k Selection

Find the largest or smallest k elements without sorting the full input, using a heap or partition-based approach.

6.11 Partial Sorting

Produce only the smallest k elements in sorted order rather than sorting the entire array, reducing unnecessary work when the full order is not needed.