Partial sorting: Difference between revisions

Revision as of 18:18, 10 May 2019

Revision as of 20:54, 2 December 2019

Line 13:

More efficient than the aforementioned 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>

'''function''' partial_quicksort(A, i, j, k) '''is'''

'''if''' i < j '''then'''

p ← pivot(A, i, j)

p ← partition(A, i, j, p)

partial_quicksort(A, i, p-1, k)

'''if''' p < k-1 '''then'''

partial_quicksort(A, p+1, j, k)

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.