0

Lately i have been taking an course at brilliant.org, i was exploring a lesson on QuickSort algorithm, found a question.

Which of the following would provide the optimal pivot selection at each step of quicksort?

  • A. The element in the first position
  • B. The element with the smallest value
  • C. A randomly selected element
  • D. The median of the elements

The answer listed was "D"

but in real life arrays how is it going to be any of the options above?

Justification listed was

"the median value, will allow the algorithm to split the list into approximately equal parts, so the runtime will speed up."

We never know the value of a element, if we do choose a median how is it guaranteed to make the array split into 2 parts ? For all we know it may turn out of be the highest or lowest or very near to the highest or the lowest number. Which would make either of the left array or right array almost empty.

  • 3
    By the definition of median, the optimal pivot point is the median i.e. that there is equal probability of a value being above or below it. Now, it's true that it's often more expensive to find the median than to approximate it but that doesn't make the answer wrong. Just not always practical. – Alex Sep 25 '17 at 10:26
  • The chosen element divides the problem in two. You want BOTH halfs to be as small as possible to minimize the problem - that means that you should make them exactly half if you can. – Thorbjørn Ravn Andersen Sep 26 '17 at 12:05
8

You seem to be confusing the median value and the middle element.

The middle element of the unsorted array could indeed turn out to be close to the lowest or highest value.
The median value on the other hand is the value that has half the values compare as smaller and half the values compare as bigger.

The advantage of using the median value as a pivot in quicksort is that it guarantees that the two partitions are as close to equal size as possible.
The problem of using the median value is that you need to know the values of all elements to know which the median is. This makes using the median value hard to do in practice, despite it being the optimal value in theory.

  • 3
    Might be worth mentioning the common compromise over the guaranteed optimal performance of using the median versus the practical difficulty of calculating it, which is to take the median of just the first, last and middle elements of the array, which in practice is usually close to the median of the entire array for most real circumstances. – Jules Sep 25 '17 at 10:38
  • 3
    To find the real median, I don't just need to know the values of all elements, I need to sort those elements first. Which means finding the real median inside a sorting algorithm is a bit pointless. – amon Sep 25 '17 at 10:49
  • i was indeed confused between "median of an list" & "median value of a list".. thanks for clearing it up & also @amon has a valid point, i'm guessing some other technique is used & this is just one of those ideal cases. – Sujal Mandal Sep 25 '17 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.