Content deleted Content added
copyedit, rewrite pseudocode, formal reference |
→Specialised sorting algorithms: correct pseudocode, name |
||
Line 21:
p ← partition(A, i, j, p)
partial_quicksort(A, i, p-1, k)
'''if''' p <
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 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.
| |||