Quick sort is run on 2 inputs shown below to sort in ascending order A. 1, 2,…
2017
Quick sort is run on 2 inputs shown below to sort in ascending order
A. 1, 2, 3……n
B. n, n – 1, n – 2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
- A.
C1 > C2
- B.
C1 = C2
- C.
C1 < C2
- D.
Cannot say anything for arbitrary n
Attempted by 206 students.
Show answer & explanation
Correct answer: B
In Quick Sort, the comparison count depends on pivot selection. Assuming the first or last element is chosen as the pivot, both sorted (Input A) and reverse-sorted (Input B) inputs lead to the worst-case scenario. Each partition step creates highly unbalanced subarrays, requiring n-1 comparisons per level regardless of input order. Therefore, the total number of comparisons is identical for both cases (C1 = C2).