An array of 25 distinct elements is to be sorted using quicksort. Assume that…
2021
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:
- A.
0.5
- B.
0.7
- C.
0.9
- D.
0.08
- E.
Question not attempted
Attempted by 207 students.
Show answer & explanation
Correct answer: D
In quicksort, the worst possible location for a pivot is when it is placed at either the first or last position of the array, resulting in the most unbalanced partition. For an array of 25 distinct elements, there are 2 such positions (index 0 or index 24). Since the pivot is chosen uniformly at random, the probability of selecting one of these two positions is: Probability = 2 / 25 = 0.08 Thus, the probability is 0.08 (rounded to 2 decimal places).