GATE CSE
First time here? Checkout the FAQ!
x
+9 votes
667 views

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$

 

asked in Algorithms by Veteran (64.6k points)  
retagged by | 667 views
Notice --> 'Comparison' and 'Swap' may be different.

1 Answer

+14 votes
Best answer
C.

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

i) is sorted in ascending order.

ii) is sorted in descending order.
answered by Veteran (19.1k points)  
selected by
Does not it depend on the pivot chosen?
yes, it should. I guess it is missing in question.
explain anyone ... specifically abt the pivot element......


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,650 answers
79,695 comments
31,069 users