GATE CSE 2019 | Question: 20

Question

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 ________

Comments

@Shoaib_Ahmed it means the paritions are created in a way that 1 half contains no element and the other half have all the remaining elements.

---

worst case then either the max or the min is selected as pivot.
thus 2 out of 25 .

---

I feel doubtful about this approach because in the last step we are saying that the probability of (1/25)*(2/25) applies to all the 25 elements hence 25*(1/25)*(2/25) but the question states "in the first round of partitioning". All the 25 elements cannot be the worst pick in the first round

Answer 1

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 $

Comments

n-3 is not because it will have 2 element on left hand side and to sort them we will need to call recursive function

okay so if question was about told about asymptotic then the case which I told will come under worst case or not ??

---

In quick sort if the recursive equation is

T(n) = T(n-k) + T(k) + n where k is constant

then it will be asymptotically worst case

---

@srestha worst case location means -→ last or first location→ which divide the array into 1|n-1 element..

so, if maximum or minimum is first pivot element then it should be palced in location 1^st or last respectively..

therefore probability should be 2/25=0.08

thank you..

Answer 2

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.

Comments

thanks for this explaination :)

Answer 3

I think 2/25

Comments

2/25

---

not 1/25 :(

---

Even I am not sure but if pivot element is first or last element then it can be worst case let's wait for answer key!!

---

the paper seemed easy
but so many silly things :( :/

Answer 4

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.08

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

Comments

Small Correction:

Probability = 2/25 = 0.08

Answer 5

In the worst case, the pivot element should be either the first or last element (either maximum or minimum).

A

or 

B

Required Probability=2/25=0.08.

Answer 6

2 choice

 1st one is when pivot element get in 1 poistion and all n-1 element remains

 2 nd when pivot get in last position and n-1 element remains

so , P(E) = no . of favourable events / total no of events

therfore , P(E) = 2/25 = 0.08

Comments

Why not 3/25 we can put in middle which also leads to worst case (??