Self Doubt

Question

Please explain me the difference between the following questions and their answers. All seems similar to me with different answers.

https://gateoverflow.in/2048/gate2014-3-14

https://gateoverflow.in/1830/gate2006-52

https://gateoverflow.in/25209/tifr2012-b-14

Comments

First question is different from rest two as in first que talks about pivot as central element and as explained by Arjun Sir that there exists possibility that the partition in this case can be 1 and n-1 this leads to worst case scenario of n^2 if pivot is taken from a fixed location.

In case of median,it's not based on position but it will always be the mid of the sorted values thus each partition will be of size n/2 and n/2 giving complexity as theat(nlogn)

---

Thanks, I tried going through them again. It's clear now.

Answer 1

MEDIAN means the middle element in the sorted array. Consider the below example.

[2,5,3,4,1] if median is selected as pivot i.e '3'  then after partition algo. is applied if will placed in middle i.e [2,1]{3}[4,5}. so it will divide the array in two halves everytime since always median is selected as pivot. so Time complexity will be O(nlogn).

Whereas middle/central element means the middle element of input. so it is possible that in input middle element is smallest/largest there partiton algo will place it at first/last hence performing best case of quicksort i.e O(n^2).