Partial sorting: Difference between revisions

Revision as of 04:32, 18 March 2014

Revision as of 21:31, 31 May 2014

Line 1:

In [[computer science]], '''partial sorting''' is a [[Relaxation (approximation)|relaxed]] variant of the [[Sorting algorithm|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 algorithm|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 ''i''th 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.

== DirectSolution applicationby of the linear-timepartitioning selection algorithm ==

A further relaxation requiring only a list of the {{mvar|k}} smallest elements, but without requiring that these be ordered, makes the problem equivalent to [[Selection algorithm#Partition-based selection|partition-based selection]]; the original partial sorting problem can be solved by such a selection algorithm to obtain an array where the first {{mvar|k}} elements are the {{mvar|k}} smallest, and sorting these, at a total expected cost of {{math|''O''(''n'' + ''k'' log ''k'')}} operations.

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 ''k''th smallest element using the [[Selection algorithm#Linear general selection algorithm - Median of Medians algorithm|linear-time median-of-medians selection algorithm]]. After that, [[Quicksort#In-place_version|partition]] the array with the ''k''th smallest element as pivot. The ''k'' smallest elements will be the first ''k'' elements.

== Data structure-based solutions ==