667 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$

retagged | 667 views
Notice --> 'Comparison' and 'Swap' may be different.

C.

both are the worst cases of quick sort. (assuming pivot is either first or last element)

i) is sorted in ascending order.

ii) is sorted in descending order.
selected by
Does not it depend on the pivot chosen?
yes, it should. I guess it is missing in question.
explain anyone ... specifically abt the pivot element......