Content deleted Content added
→Data structure-based solutions: rewrite |
→Solution by partitioning selection: "quickselsort" |
||
Line 4:
== Solution by partitioning selection==
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. When [[quickselect]] and [[quicksort]] are used as the building blocks in this algorithm, the result is called "quickselsort".<ref name="aofa04slides"/>
== Heap-based solutions ==
| |||