An array of 25 distinct elements is to be sorted using quick sort. Assume that…
2024
An array of 25 distinct elements is to be sorted using quick sort. 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.08
- B.
0.05
- C.
1
- D.
1.5
Attempted by 112 students.
Show answer & explanation
Correct answer: A
In quicksort, the worst-case partitioning occurs when the pivot is the smallest or largest element in the array, resulting in one subarray of size 0 and another of size n-1. For an array of 25 distinct elements, the worst-case pivot positions are the first (1) and last (25) elements.
Since the pivot is chosen uniformly at random, the probability of selecting either 1 or 25 is:
P(pivot is worst) = P(1) + P(25) = 1/25 + 1/25 = 2/25 = 0.08
Thus, the probability is 0.08 when rounded to two decimal places.