The Gateway to Computer Science Excellence

+20 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$

+22 votes

Best answer

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)

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

=

=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

=

0

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 ?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,166 answers

193,872 comments

94,261 users