retagged by
10,902 views
31 votes
31 votes

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

  1. $1, 2, 3, \dots n$
  2. $n, n-1, n-2, \dots, 2, 1$

Let $C_1$ and $C_2$ be the number of comparisons made for the inputs (i) and (ii) respectively. Then, 

  1. $C_1 < C_2$
  2. $C_1 > C_2$
  3. $C_1 = C_2$
  4. we cannot say anything for arbitrary $n$
retagged by

3 Answers

Best answer
32 votes
32 votes

Correct Option: C
both are the worst cases of quick sort. (assuming pivot is either first or last element)

  1. is sorted in ascending order.
  2. is sorted in descending order.
edited by
5 votes
5 votes
1)ascending case==>Comparisons(C1)=(n-1)+(n-2)+(n-3)+.........................+2+1

                                                               =n(n-1)/2

                                                               =o(n^2)

                                             Swaps(S1)=1+1+1+............................................+1(upto n pass)

                                                               =n

                                                               =o(n)

2)Descending case==>Comparisons(C2)=(n-1)+(n-2)+(n-3)+....................................+1

                                                                 =n(n-1)/2

                                                                 =o(n^2)

                                               Swaps(S2)=(n)+(1)+(n-2)+(1)+(n-4)+...........(ascending and descending cases will come alternatively)                                           

                                                                 =3n^2/4

                                                                =o(n^2)

so C1=C2 and S1<S2

 

                                                                =
1 votes
1 votes
I think answer is C1>C2 because in ascending input left do 1 comparison and than stops and than right do all comparison until left=right. But in descending input left keeps going until left=right and right won't do any comparison because according to algorithm right start moving only after left finds a key which is larger than pivot which is not in the case of descending input.
Answer:

Related questions

23 votes
23 votes
4 answers
2
Kathleen asked Oct 9, 2014
7,113 views
The recurrence relation$T(1) = 2$$T(n) = 3T (\frac{n}{4}) +n$has the solution $T(n)$ equal to$O(n)$$O (\log n)$$O\left(n^\frac{3}{4}\right)$ None of the above