Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

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

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...