1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

# 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 D t1 > 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.

Suggest Corrections
1
Join BYJU'S Learning Program
Related Videos
Defining Relations
MATHEMATICS
Watch in App
Explore more
Join BYJU'S Learning Program