An array of 25 distinct elements is to be sorted using quicksort. Assume that…
2019
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ________.
Attempted by 128 students.
Show answer & explanation
Correct answer: 0.08
Key idea: the pivot's final position after partition equals its rank among the elements.
The worst possible placements after the first partition are when the pivot is the smallest or the largest element, giving partitions of sizes 0 and 24.
There are 2 worst placements (smallest or largest) out of 25 possible pivots.
Probability = 2/25 = 0.08. Rounded to two decimal places: 0.08.
Answer: 0.08
A video solution is available for this question — log in and enroll to watch it.