9,059 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$

@chhotu

I think we should answer sorting questions based on algorithms given in standard textbooks because most of the gate questions were based on those.

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

Refering quicksort algorithm given in CLRS,

then ,  C1 = C2 (for comparison)

C1 < C2  (for swaps)

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.

explain anyone ... specifically abt the pivot element......
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)
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.
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

=

edited by

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 ?

@talha hashim please explain how you are calculating swaps when input is in descending order?
edited
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]
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.
by

Thanks