Does anyone know the full technical vocabulary to describe all the various versions of quicksort?
The one I know is "fat pivot"[A] (where all items matching the pivot placed in the middle of the subarray and excluded from further sorting).
The ones I'd like to know are when one element (the pivot) is placed in the middle and excluded from sorting[B] and where zero elements are placed in the middle[C].
Here examples of partitioning for each of these:
input subarray is 5,3,2,9,5,7
[A] gives [3,2],5,5,[9,7]
[B] gives [3,2],5,[9,5,7]
[C] gives [3,2,5],[9,5,7]
From stackoverflow
-
Um, quicksort?
Here is some information on Quicksort variations.
paperhorse : If you're saying normal quicksort, I kind of suspect you're right. The wikipedia page seems to describe case B where a single element is placed. I believe the original STL sort (and the current quicksort portions of the introsort) follow case C.
0 comments:
Post a Comment