Quicksort is run on two inputs shown below to sort in ascending order taking…
1996
Quicksort is run on two inputs shown below to sort in ascending order taking the first element as pivot,
(i) 1, 2, 3,......., n
(ii) n, n-1, n-2,......, 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
- A.
C1 < C2
- B.
C1 > C2
- C.
C1 = C2
- D.
We cannot say anything for arbitrary n
Attempted by 56 students.
Show answer & explanation
Correct answer: C
In Quicksort, the number of comparisons depends on how balanced the partitions are at each step. When sorting a sorted array (1, 2, ..., n) with the first element as pivot, the pivot is always the smallest. This results in one subarray of size 0 and another of size n-1, leading to a recurrence T(n) = T(n-1) + (n-1).
Similarly, for the reverse sorted array (n, n-1, ..., 1), the first element is always the largest. This also creates one subarray of size n-1 and another of size 0, yielding the same recurrence T(n) = T(n-1) + (n-1).
In both cases, the total number of comparisons is the sum of integers from 1 to n-1, which equals n(n-1)/2. Therefore, C1 and C2 are exactly equal.
Options suggesting inequality (A or B) are incorrect because the structural imbalance is identical in both scenarios, just mirrored. Option D is wrong since we can definitively calculate the count.