Let \(P\) be quicksort program to sort numbers in ascending order using the…
2014
Let \(P\) be quicksort program to sort numbers in ascending order using the first element as the pivot. Let \(t_1\) and \(t_2\) be the number of comparisons made by \(P\) for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
- A.
\(t_1 = 5\) - B.
\(t_1 < t_2\) - C.
\(t_1 > t_2\) - D.
\(t_1 = t_2\)
Attempted by 291 students.
Show answer & explanation
Correct answer: C
Key idea: each partition step on a subarray of size k performs k-1 comparisons between the pivot and the other elements.
For [1 2 3 4 5]:
First pivot = 1 gives 4 comparisons; then pivot = 2 gives 3; then 3 gives 2; then 4 gives 1. Total = 4 + 3 + 2 + 1 = 10 comparisons.
For [4 1 5 3 2]:
First pivot = 4 gives 4 comparisons and partitions into left [1,3,2] and right [5]. Sorting left: pivot = 1 gives 2 comparisons; then its right [3,2] needs 1 comparison. Total = 4 + 2 + 1 = 7 comparisons.
Conclusion: t1 = 10 and t2 = 7, so t1 > t2.