Selection algorithm: Difference between revisions

Revision as of 00:18, 25 May 2005

Revision as of 23:06, 9 June 2005

Line 62:

'''return''' storeIndex

In quicksort, we recursively sort both branches, leading to best-case [[Big-O notation|Ω]](''n'' log ''n'') time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in sorted order preceding it and all those following it in sorted order following it. Thus a single recursive call locates the desired element in the correct partition:

'''function''' select(a, k, left, right)