Gate1997_2.15

Quick-sort is run on two inputs shown below to sort in ascending order
(i) 1,2,3 ….n
(ii) n, n – 1, n – 2, …. 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
(a) C1 < C2
(b) C1 > C2
(c) C1 = C2
(d) we cannot say anything for arbitrary n.

Answer :-(C)
Exp:-
Quick-sort is run on two inputs shown below to sort in ascending order
(i) 1,2,3 ….n
(ii) n, n – 1, n – 2, …. 2, 1
when Quick-sort  runs on increasing or decreasing order same input   then Time Complexity O(n2) , number of comparisons are same.
(i) 1,2,3 ….n------------- increaing oder --------- C1  be the number of comparisons
(ii)  n, n – 1, n – 2, …. 2, 1 --------- decreasing order ---------  C2 be the number of comparisons
 

 

0Comment