The Gateway to Computer Science Excellence
+20 votes
2.3k 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$
in Algorithms by Veteran (52.1k points)
retagged by | 2.3k views
+2
Notice --> 'Comparison' and 'Swap' may be different.
+2
What if it is number of swap I think

b will the answer.
0
for number of swaps.

$i)$ no swaps needed

$ii)$ total $n$ swaps needed
0

Hi @reena_kandari ji,

It depends on how the actual partition function is implemented. 

0

yes, and if I Implements the following procedure than in second case I am getting total $n/2$ swaps.

Partition(A,p,r) //A[p...r]
i=r+1;
j=r;
for(j=r to p+1; j--)
{
    if(A[j]>A[p]){
         i=i--;
         if(i!=j) exchange A[i] with A[j]
    }
     
}
if(p!=i-1) exchange A[p] with A[i-1]
0

Hi @reena_kandari ji,

For self verification just use some static count variable and print it. 

0
according to isro it is c.

they are kidding
0
C1 = C2 is the correct answer but ISRO have given key as C1 > C2
0
yeah

2 Answers

+22 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.
by Boss (19.9k points)
edited by
+1
Does not it depend on the pivot chosen?
+1
yes, it should. I guess it is missing in question.
0
explain anyone ... specifically abt the pivot element......
0
If you consider like a tree then the no of comparison at each levels depends upon 'n' and if the pivot element is last in case of an already sorted array. Then no of levels = n. Thus no of comparison = n*n.

In case of an unsorted array no of comparison considering logn levels= n*logn.

So shouldn't c1>c2? (Assuming the last element is choosen as the pivot always)
+1 vote
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

 

                                                                =
by Loyal (5.4k points)
0

@Mk Utkarsh 

i am not getting why that "single" swap required if array is sorted in ascending order, as pivot is placed correctly ( say left end element as pivot ) and all right side elements are larger and lhs are smaller ( though nothing is in lhs ).. So where single swap is needed ?

are we swapping element with itself hence "1" swap ?

Related questions

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
50,654 questions
56,166 answers
193,872 comments
94,261 users