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

Question

Using a list of 15 numbers, I need to give a list representing the best and worst case scenario. It says "q.s. uses the first item in the list as the pivot item". I'm not sure if I pick the first item as pivot every time, but that's what I'm assuming....

For best case scenario.. I came up with (bold for pivot, italic for bigger and smaller than markers):

8 1 3 2 6 5 7 4 12 9 11 10 14 13 15

4 1 3 2 6 5 7--8--12 9 11 10 14 13 15

2 1 3 --4--6 5 7........8........10 9 11--12--14 13 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Hope someone can here can verify my work and if it's wrong, point out to me how and why.

Answer 1

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.