The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
773 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 (67.5k points)
retagged by | 773 views
Notice --> 'Comparison' and 'Swap' may be different.

1 Answer

+16 votes
Best answer

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.
answered by Veteran (19.3k points)
edited ago 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......


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,792 answers
91,068 comments
34,689 users