Partial sorting

In computer science, partial sorting is a relaxed variant of the sorting problem. Total sorting is the problem of returning a list of items such that its elements all appear in order, while partial sorting is returning a list of the k smallest (or k largest) elements in order. The other elements (above the k smallest ones) may also be stored, as in an in-place partial sort, or may be discarded, which is common in streaming partial sorts. A common practical example of partial sorting is computing the "Top 100" of some list. A further relaxation only requires returning a list of the k smallest elements, but without requiring that these be ordered. This latter form is quite close to the selection problem, and a solution to one problem can be easily converted to a solution to the other.

In terms of indices, in a partially sorted list, for every index i from 1 to k, the ith element is in the same place as it would be in the fully sorted list: element i of the partially sorted list contains order statistic i of the input list.

Direct application of the linear-time selection algorithm

The linear-time selection algorithm described above can be used to find the k smallest or the k largest elements in worst-case linear time O(n). To find the k smallest elements, find the kth smallest element using the linear-time median-of-medians selection algorithm. After that, partition the array with the kth smallest element as pivot. The k smallest elements will be the first k elements.

Data structure-based solutions

Another simple method is to add each element of the list into a priority queue data structure, such as a heap or self-balancing binary search tree, with at most k elements. Whenever the data structure has more than k elements, we remove the largest element, which can be done in O(log k) time. Each insertion operation also takes O(log k) time, resulting in O(n log k) time overall.

It is possible to transform the list into a binary heap in Θ(n) time, and then traverse the heap using a modified breadth-first search algorithm that places the elements in a priority queue^{[clarification needed]} (instead of the ordinary queue that is normally used in a BFS), and terminate the scan after traversing exactly k elements. As the queue size remains O(k) throughout the traversal, it would require O(k log k) time to complete, leading to a time bound of O(n + k log k) on this algorithm.^{[citation needed]}

Specialised sorting algorithms

More efficient than any of these are specialized partial sorting algorithms based on mergesort and quicksort. In the quicksort variant, there is no need to recursively sort partitions which only contain elements that would fall after the $k$ 'th place in the final sorted array (starting from the "left" boundary). Thus, if the pivot falls in position $k$ or later, we recurse only on the left partition:^[1]

 function partial_quicksort(A, i, j, k)
     if i < j
         p ← pivot(A, i, j)
         p ← partition(A, i, j, p)
         partial_quicksort(A, i, p-1, k)
         if p < j + k
             partial_quicksort(A, p+1, j, k)

The resulting algorithm requires an expected time of only $O (n + k log k)$ , and is quite efficient in practice, especially if we substitute selection sort when $k$ becomes small relative to $n$ . However, the worst-case time complexity is still very bad, in the case of a bad pivot selection. Pivot selection along the lines of the worst-case linear time selection algorithm could be used to get better worst-case performance.

Even better is if we don't require those $k$ items to be themselves sorted. Losing that requirement means we can ignore all partitions that fall entirely before, or after the $k$ th place. We recurse only into the partition that actually contains the $k$ th element itself.

 function partial_quicksort(A, i, j, k)
     if i < j
         p ← pivot(A, i, j)
         p ← partition(A, i, j, p)
         if p > i + k  // new condition
             partial_quicksort(A, i, p-1, k)
         if p < i + k
             partial_quicksort(A, p+1, j, k+i-p-1)

The resulting algorithm requires an expected time of only $O (n)$ , which is the best such an algorithm can hope for.

Tournament Algorithm

Another method is the tournament algorithm. The idea is to conduct a knockout minimal round tournament to decide the ranks. It first organises the games (comparisons) between adjacent pairs and moves the winners to next round until championship (the first best) is decided. It also constructs the tournament tree along the way. Now the second best element must be among the direct losers to winner and these losers can be found out by walking in the binary tree in O(log n) time. It organises another tournament to decide the second best among these potential elements. The third best must be one among the losers of the second best in either of the two tournament trees. The approach continues until we find k elements. This algorithm takes O(n + k log n) complexity, which for any fixed k independent of n is O(n).

Language/library support

The C++ standard specifies a library function called std::partial_sort.
The Python standard library includes functions nlargest and nsmallest in its heapq module.

References

^ Martínez, Conrado (2004). Partial quicksort (PDF). Proc. 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics.

External links

J.M. Chambers (1971). Partial sorting. CACM 14(5):357–358.

[1] Martínez, Conrado (2004). Partial quicksort (PDF). Proc. 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics.

[1]