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

Dark Mode

9,059 views

30 votes

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

- $1, 2, 3, \dots n$
- $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,

- $C_1 < C_2$
- $C_1 > C_2$
- $C_1 = C_2$
- we cannot say anything for arbitrary $n$

0

0

29 votes

Best answer

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)

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

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

=

=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
Nov 27, 2018
by HeadShot

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

edited
Aug 10, 2020
by sanjaysharmarose

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]

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

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.