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.