retagged by
16,110 views
29 votes
29 votes
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 ________
retagged by

4 Answers

Best answer
47 votes
47 votes
Worst case of quicksort, if pivot element is Minimum or Maximum.

Total elements $= 25$
For worst case number of candidates $= 2$

$P = \frac{2}{25} = 0.08 $
selected by
22 votes
22 votes
Quick sort puts the pivot element in its correct place after 1st iteration. The worst place the pivot element can be placed at is extreme left or extreme right because in that case the array is divided in the ratio 1:n-1 giving complexity of O(n Square). The pivot element will come to extreme left or right after 1st iteration if it's minimum or maximum.So pivot can be either minimum or maximum.

So 2 out of 25 elements can be selected for pivot thus giving a probability of 2/25 equal to 0.08.
6 votes
6 votes
I think 2/25
2 votes
2 votes
Quicksort performed worst if the position of pivot is either first or last.

By the above discussion, I conclude that there are two worst-case positions first or the last position.

Probability = 2/25=0.04

It can also understand as if we choose a minimum or maximum element as a pivot because if we choose minimum as pivot then it will be placed at a first position or if we choose the last element as pivot then it will be placed at the last position. So the probability is= 2/25=0.04
Answer:

Related questions

35 votes
35 votes
9 answers
1
23 votes
23 votes
9 answers
2
33 votes
33 votes
4 answers
3
Arjun asked Feb 7, 2019
16,084 views
Suppose $Y$ is distributed uniformly in the open interval $(1,6)$. The probability that the polynomial $3x^2 +6xY+3Y+6$ has only real roots is (rounded off to $1$ decimal...
24 votes
24 votes
8 answers
4
Arjun asked Feb 7, 2019
17,134 views
The following C program is executed on a Unix/Linux system :#include<unistd.h int main() { int i; for(i=0; i<10; i++) if(i%2 == 0) fork(); return 0; }The total number of ...