If a sorted list in asending order
1 2 3 4 5 6
a sorted list in desending order
6 5 4 3 2 1
and a list contains same elements : 6 6 6 6 6 6
all are worst case scenerio for quik sort than which type of series act as a best case in Quik Sort and how?
1 Like
A condition for the best case for Quicksort is that the pivot always goes right smack in the middle (except perhaps in the very last stages), so much is definitely correct. On top of that you want as few swaps as possible, the precise configurations for that depend on the implementation details.
One common implementation is to first swap the pivot into the last place, then arrange the others so that the elements smaller than (or equal to) the pivot come before the larger elements and finally swap the pivot (from last place) with the first of the larger elements (then recur).
Another method is to put the pivot into the first slot before arranging and swap it with the last not exceeding the pivot after.
For the absolute best case, these strategies require different configurations. For example,
4 1 3 5 6 7 2
is a best case scenario for the ‘swap pivot into last place’ variant, while
4 1 3 2 6 5 7
is a best case for ‘pivot stays put’.
1 Like