CODEWITHSUNDEEP
algorithmsortingquicksort
Chris
Chris

Reputation: 87

Quick Sort Algorithms - Many different ways of doing the same thing?

Am I correct in saying that there would be many ways to perform a Quick Sort?

For argument sakes, lets use the first textbook's numbers: 20 47 12 53 32 84 85 96 45 18

This book says to swap the 18 and 20 (in the book the 20 is red and the 18 is blue, so I've bolded the 20).

Basically it keeps moving the blue pointer until the numbers are: 18 12 20 53 32 84 85 96 45 47

Now it says (and this is obvious to me) that all the numbers to the left of the 20 are less than and all of the numbers to the right are greater than, but it never names the 20 as a "pivot", which is how most other resources talk about it. Then as all other methods state, it does a quick sort on two sides and then we end up with (it only covers sorting the right half of the list):

47 32 45 53 96 85 84 and the book ends. Now I know from the other resources that once all of the lists are in order they are put back together. I guess I understand this but am constantly confused by the one "Cambridge approved" textbook that differs from the second one. The second one talking about finding a pivot by picking the median.

What's the best way to find a "pivot" for a list?

Upvotes: 3

Views: 1047

Answers (2)

Am_I_Helpful
Am_I_Helpful

Reputation: 19178

What is given in your textbook is similar to the pivot-based concept except that they haven't mentioned this terminology over there. But,anyways the concepts are the same.

What's the best way to find a "pivot" for a list?

There's not a fixed way of selecting pivotal-element. You can select any of the element of the array---first,second,last,etc. It can also be randomly selected for a given array.

But, scientists and mathematicians generally talk about the median element which is the middle element of the list for the symmetry based reason,thereby reducing the recursive calls.

It is almost obvious that when you'll select the first or the last element of the array, there will be more number of recursive calls --- thereby moving closer to the worst case scenario. The more number of recursive calls will be framed to separately perform quick-sort on the two partitions.

Upvotes: 2

amit
amit

Reputation: 178521

Theoretically - choosing the median element as the pivot guarantees least number of recursive calls, and guarantees Theta(nlogn) running time.
However, finding this median is done with selection algorithm - and if you want to guarantee selection takes linear time - it needs median of medians algorithm, which has poor constants.

If you chose the first (or last) element as pivot - you are guaranteed to get poor performance for sorted or almost sorted array - which is pretty likely to be your input array in many applications - so that's not a good choice either. So choosing the first/last element of the array is actually a bad idea.

A good solid solution to chose pivot - is at random. Draw a random number from r = rand([0,length(array)), and chose the r'th element as your pivot.

While there is a theoretical possibility for worst case here - it is:

  1. Very unlikely
  2. Hard for mallicious user to predict what is the worst case input, especially if the random function and/or seed is unknown to him.

Upvotes: 2

Related Questions