2

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?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
poorvank
  • 7,524
  • 19
  • 60
  • 102
  • check this link, www.cs.utexas.edu/~lavender/courses/EE360C/lectures/lecture-22.pdf‎ – Mayank Tiwari Jun 20 '13 at 06:00
  • if this does not give u answer, then you MUST choose the base paper for the same.. it will give you complete concepts of quick sort – Mayank Tiwari Jun 20 '13 at 06:00
  • 3
    This might help, http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot – PythonIITD Jun 20 '13 at 06:01
  • Since the wrong pivot is most catastrophic in the early stages, you can probably afford to invest (relatively) more time worrying about it in early passes, and when the length falls below some threshold, drop back to a simpler algorithm. As everyone is saying, it all depends on your data. – sh1 Jun 22 '13 at 00:33

3 Answers3

5

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.

TooTone
  • 7,129
  • 5
  • 34
  • 60
3

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.

rob mayoff
  • 375,296
  • 67
  • 796
  • 848
0

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.

Yandong Liu
  • 335
  • 4
  • 13