An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)

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’.

The worst case scenario is when the pivot always goes to one of the ends of the array, precise details again depend on the implementation, but sorted or reverse sorted are usually worst cases.

Leave a Comment