Let P be a Quicksort Program to sort numbers in ascending order using the first element as 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?
t1 = t2
t1 > t2
t1 < t2
What is quick sort and how to solve ths
Hello @Somasree have not you gone through the quicksort editorial and algorihtm?
the answer for the above question is t1>t2
for explanation you can see this:
Best answer
it would be t1>t2t1>t2, because the first case is the worst case of quicksort i.e. minimum number is chosen as pivot. Hence in the worst case the comparisons are high.
The splitting occurs as
[1][2345][1][2345]
[2][345][2][345]
[3][45][3][45]
[4][5][4][5]
and
[123][45][123][45]
[1][23][4][5][1][23][4][5]
[2][3][2][3]
Number of recursive calls remain the same, but in second case the number of elements passed for the recursive call is less and hence the number of comparisons also less.