Partial sorting: Difference between revisions

Revision as of 21:18, 12 January 2014

Revision as of 21:29, 12 January 2014

Line 25:

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 we substitute selection sort 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.

Even better is if we don't require those {{mvar|k}} items to be themselves sorted. Losing that requirement means we can ignore all partitions that fall entirely before, ''or'' after the {{mvar|k}}th place. We recurse only into the partition that actually contains the {{mvar|k}}th element itself.

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

'''if''' i < j

p ← pivot(A, i, j)

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

'''if''' p > i + k ''// new condition''

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

'''if''' p < i + k

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

The resulting algorithm requires an expected time of only {{math|''O''(''n'')}}, which is the best such an algorithm can hope for.

==Tournament Algorithm==