GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 2

Answer 1

If the median value gets picked as the pivot, the array will be in sorted order after only a single pivot. If the smallest or largest gets picked, we're not quite done.

Probability of choosing median $= 1/3$ since there are just three types of values in equal proportion.

Comments

@Deepak Poonia yes sir it will be multiple of 3 but sir any way we do there will be two partition, then how sir three partition possible?

---

@samarpita

It has been corrected.

---

@Deepak Poonia@GO Classes If partition algorithm is applied, even if we pick the median as our pivot, it won't guarantee that our array is sorted. Let's say the left of the pivot is <= pivot and the right of the pivot is strictly greater as there are N/3 elements this will not guarantee that the left part of the pivot is sorted.

Let's say it's not partition algorithm, even then there are other cases to the considered other than the case mentioned in the answer, even if you take the elements other than the median there will be cases which result in a sorted array…the probability must depend on N.