in Algorithms retagged by
10,865 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$
in Algorithms retagged by
10.9k views

4 Comments

No, in :”REVISED AND FINAL ANSWER KEY” they have given B as the correct answer i.e. C1 = C2. So, ISRO’s Final Answer is B

1
1
Refering quicksort algorithm given in CLRS,

then ,  C1 = C2 (for comparison)

C1 < C2  (for swaps)
3
3
What if the pivot is the middle element??
0
0

3 Answers

32 votes
32 votes
Best answer

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

4 Comments

explain anyone ... specifically abt the pivot element......
0
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)
0
0
If the same algorithm is used for running both arrays and the algorithm chooses the last element as the pivot, then the comparisons will be C1<C2 and vice versa if the pivot chosen is the first element.

If the pivot chosen is the middle element, every time, then C1=C2.
0
0
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

 

                                                                =

4 Comments

edited by

@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 ?

0
0
@talha hashim please explain how you are calculating swaps when input is in descending order?
0
0
edited by
This is what I think:

In ascending order :
                  No. of comparisons = (n-1)+(n-2)+......+1  = O(n^2)
                  No. of swappings = (n)+(n-1)+......+1  = O(n^2)     [here every element will be swapped with itself ]

In descending order :
                  No. of comparisons = (n-1)+(n-2)+......+1  = O(n^2)
                  No. of swappings = 1+1+1+......n times = O(n)     [here only pivot element will be swapped]
0
0
No.of swappings for ascending order will be O(n) because it is 1 + 1 + 1 + 1 + ...
0
0
1 vote
1 vote
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.

1 comment

Thanks
0
0
Answer:

Related questions