Content deleted Content added
→Selecting k smallest or largest elements: L3 → L2 section, remove lede that’s been merged into article lede |
convert solution to and fro |
||
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.
| |||