Partial sorting: Difference between revisions

Revision as of 06:40, 23 November 2022

Revision as of 06:41, 23 November 2022

Line 10:

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 cost of {{math|''O''(''n'' + ''k'' log ''k'')}} operations. A popular choice to implement this algorithm scheme is to combine [[quickselect]] and [[quicksort]]; the result is sometimes called "quickselsort".<ref name="aofa04slides"/>

Common in current (as of 2022) C++ STL implementations is a pass of [[Heap (data structure)#Applications|heapselect]] for an ''unsorted''a list of ''k'' elements, followed by a [[heapsort]] for the final result.<ref>{{cite web |title=std::partial_sort |url=https://en.cppreference.com/w/cpp/algorithm/partial_sort |website=en.cppreference.com}}</ref>

==={{anchor|Partial quicksort}} Specialised sorting algorithms===