Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 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
t1 = 5
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
t1 < t2
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
t1 = t2
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
t1 > t2
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution
The correct option is Dt1 > t2 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 5(5−1)2 comparisons are required . ⇒t1=10
(b) [ 4 1 5 3 2 ] : Elements are in random order .
Choosing first element as pivot will give comparisons compared to t1 ∴t2<t1.