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

What is the probability if the question is asking after first partitioning instead of in the first round of partitioning?

---

What is the meaning of "worst position" in this question ??

---

Worst possible locations are a[0] and a[24] i.e. either first or last position of the array.

P = favorable locations/total locations

P = 2/25=0.08

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

Comments

Small Correction:

Probability = 2/25 = 0.08