CODEWITHSUNDEEP
algorithmsortingdata-structuresquicksort
poorvank
poorvank

Reputation: 7602

Choice of pivot in Quick Sort Algorithm

I am learning Quick Sort. I know that Quick Sort performs badly when the pivot value does an unbalanced partition , and so first element or last element is not a good choice because if the list is almost sorted the partition would be unbalanced.

As i searched i found 2 options:

One was to choose a pivot randomly between low(lowest index) and up(highest index).It seems a safe option but random number generators are time consuming.

Second would be to take the median of all the elements. This option is costly so the median of first,last and middle element can be used as the pivot element.

Which method proves out to be the most efficient for Quick Sort?.. Is there any other method available for making the choice of pivot element?

Upvotes: 2

Views: 1254

Answers (3)

Yandong Liu
Yandong Liu

Reputation: 345

If you are really worried about worse case scenario, randomize the subarray in each recursive call and this should protect you against the worst case.

Upvotes: 0

TooTone
TooTone

Reputation: 8126

Yes, if you're worried about the array being sorted or nearly sorted, you can apply successively more effort to choosing a good pivot, as you suggest, but at the cost of slowing the algorithm down if your data is unsorted. Skienna, in The Algorithm Design Manual, has a good discussion of pivot selection and he suggests you could go as far as to randomize the array before applying quicksort, but my guess is another sorting algorithm would perform better if you're that worried.

Which method proves out to be the most efficient for Quick Sort?

The key point here is to perform performance measurements on your data.

Upvotes: 5

rob mayoff
rob mayoff

Reputation: 385580

There is no single “most efficient” choice for quicksort. Either you slow down your sort for some (many?) cases by spending extra time selecting each pivot, or you have pathological (O(N2)) behavior for some inputs. Spending more time selecting the pivot slows down sorting for some inputs while speeding up other cases. It's always a trade-off. You choose a trade-off that improves your speed for the kind of inputs you expect.

In the real world, we can prevent the pathological cases fairly cheaply using introsort. One characteristic of a pathological case is deep recursion, so introsort detects deep recursion and switches to a different (but guaranteed O(N log N)) algorithm.

Upvotes: 3

Related Questions