tag

#partial-sort

5 pages tagged

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

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 ›

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