Question

Let P be a 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$

Answer 1

The correct option is D $t_1$ > $t_2$

Input 1: [ 1 2 3 4 5 ]
Input 2: [ 4 1 5 3 2 ]
(a)
[ 1 2 3 4 5 ] : Already elements are in
order $\frac{5(5-1)}{2}$ comparisons are required .
$\Rightarrow t_1=10$

(b) [ 4 1 5 3 2 ] : Elements are in random order .
Choosing first element as pivot will give comparisons compared to $t_1$
$\therefore t_2<t_1$.