Content deleted Content added
m →Specialised sorting algorithms: tone, link |
m Bot: http → https |
||
| (29 intermediate revisions by 18 users not shown) | |||
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
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.
==Offline problems==
== 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 ==
▲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
Common in current (as of 2022) C++ STL implementations is a pass of [[Heap (data structure)#Applications|heapselect]] for 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>
[[Binary heap]]s lead to an {{math|''O''(''n'' + ''k'' log ''n'')}} solution to partial sorting: partial [[heapsort]]. First "heapify", in linear time, the complete input array. Then extract the minimum of the heap {{mvar|k}} times.<ref name="aofa04slides">{{cite conference |author=Conrado Martínez |year=2004 |title=On partial sorting |url=http://www.lsi.upc.edu/~conrado/research/talks/aofa04.pdf |conference=10th Seminar on the Analysis of Algorithms}}</ref>▼
▲A [[streaming algorithm|streaming]], single-pass partial sort is also possible using heaps or other [[priority queue]] data structures. First, insert the first {{mvar|k}} elements of the input into the structure. Then make one pass over the remaining elements, add each to the structure in turn, and remove the largest element. Each insertion operation also takes {{math|''O''(log ''k'')}} time, resulting in {{math|''O''(''n'' log ''k'')}} time overall; this algorithm is practical for small values of {{mvar|k}} and in [[online algorithm|online]] settings.<ref name="aofa04slides"/>
More efficient than
▲== 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 {{mvar|k}}'th place in the final sorted array (starting from the "left" boundary). Thus, if the pivot falls in position {{mvar|k}} or later, we recurse only on the left partition:<ref>{{cite conference |last=Martínez |first=Conrado |title=Partial quicksort |conference=Proc. 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics |year=2004 |url=http://www.lsi.upc.edu/~conrado/research/reports/ALCOMFT-TR-03-50.pdf}}</ref>
The resulting algorithm is called partial quicksort and requires an ''expected'' time of only {{math|''O''(''n'' + ''k'' log ''k'')}}, and is quite efficient in practice, especially if a [[selection sort]] is used as a base case when {{mvar|k}} becomes small relative to {{mvar|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 (see {{section link|Quicksort|Choice of pivot}}) could be used to get better worst-case performance. Partial quicksort, quickselect (including the multiple variant), and quicksort can all be generalized into what is known as a ''chunksort''.<ref name="aofa04slides"/>▼
▲ '''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 < k-1
▲ partial_quicksort(A, p+1, j, k)
==Incremental sorting==
▲The resulting algorithm is called partial quicksort and requires an ''expected'' time of only {{math|''O''(''n'' + ''k'' log ''k'')}}, and is quite efficient in practice, especially if a [[selection sort]] is used as a base case when {{mvar|k}} becomes small relative to {{mvar|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.
Incremental sorting is a version of the partial sorting problem where the input is given up front but {{mvar|k}} is unknown: given a {{mvar|k}}-sorted array, it should be possible to extend the partially sorted part so that the array becomes {{math|(''k''+1)}}-sorted.{{r|paredes}}
▲[[
A different incremental sort can be obtained by modifying quickselect. The version due to Paredes and Navarro maintains a [[stack (data structure)|stack]] of pivots across calls, so that incremental sorting can be accomplished by repeatedly requesting the smallest item of an array {{mvar|A}} from the following algorithm:<ref name="paredes">{{Cite conference| doi = 10.1137/1.9781611972863.16| chapter = Optimal Incremental Sorting| title = Proc. Eighth Workshop on Algorithm Engineering and Experiments (ALENEX)| pages = 171–182| year = 2006| last1 = Paredes | first1 = Rodrigo| last2 = Navarro | first2 = Gonzalo| isbn = 978-1-61197-286-3| citeseerx = 10.1.1.218.4119}}</ref>
<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
Algorithm {{math|IQS(''A'' : array, ''i'' : integer, ''S'' : stack)}} returns the {{mvar|i}}'th smallest element in {{mvar|A}}
* If {{math|''i'' {{=}} top(''S'')}}:
** Pop {{mvar|S}}
** Return {{math|''A''[''i'']}}
* Let {{math|pivot ← random [''i'', top(''S''))}}
* Update {{math|pivot ← partition(''A''[''i'' : top(''S'')), ''A''[pivot])}}
* Push {{math|pivot}} onto {{mvar|S}}
* Return {{math|IQS(''A'', ''i'', ''S'')}}
{{frame-footer}}
</div>
The stack {{mvar|S}} is initialized to contain only the length {{mvar|n}} of {{mvar|A}}. {{mvar|k}}-sorting the array is done by calling {{math|IQS(''A'', ''i'', ''S'')}} for {{math|''i'' {{=}} 0, 1, 2, ...}}; this sequence of calls has [[average-case complexity]] {{math|''O''(''n'' + ''k'' log ''k'')}}, which is asymptotically equivalent to {{math|''O''(''n'' + ''k'' log ''n'')}}. The worst-case time is quadratic, but this can be fixed by replacing the random pivot selection by the [[median of medians]] algorithm.{{r|paredes}}
== Language/library support ==
* The [[C++]] standard specifies a library function called <code>[
* The [[Python (programming language)|Python]] standard library includes functions <code>[https://docs.python.org/library/heapq.html#heapq.nlargest nlargest]</code> and <code>[https://docs.python.org/library/heapq.html#heapq.nsmallest nsmallest]</code> in its <code>heapq</code> module.
* The [[Julia_(programming_language)|Julia]] standard library includes a <code>[https://docs.julialang.org/en/v1/base/sort/#Base.Sort.PartialQuickSort PartialQuickSort]</code> algorithm used in <code>[https://docs.julialang.org/en/v1/base/sort/#Base.Sort.partialsort! partialsort!]</code> and variants.
==References==▼
{{reflist}}▼
== See also ==
* [[Selection algorithm]]
▲==References==
▲{{reflist}}
== External links ==
Line 43 ⟶ 62:
[[Category:Sorting algorithms]]
[[Category:Online sorts]]
[[Category:Articles with example pseudocode]]
| |||