edited by
19,109 views
46 votes
46 votes

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?

  1. $t_1 = 5$
  2. $t_1 < t_2$
  3. $t_1>t_2$
  4. $t_1 = t_2$
edited by

6 Answers

Best answer
59 votes
59 votes
it would be $t_1>t_2$, 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]$
$[2] [345]$
$[3] [45]$
$[4] [5]$

and

$[123] [45]$
$[1] [23] [4][5]$
$[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.

Correct Answer: $C$
edited by
49 votes
49 votes

Question is asking about number of comparisons. 

First case [1 2 3 4 5]

1 [2 3 4 5]    ->  4 comparisons
2 [3 4 5]  -> 3 comparisons
3 [4 5] -> 2 comparisons
[5] -> 1 comparison

Second case [4 1 5 3 2]
[1 3 2] [5] -> 4 comparisons
[3 2]  -> 2 comparisons
3 [2]  -> 1 comparison

Hence, in second case number of comparisons is less. => t1 > t2.

22 votes
22 votes
We dont even need to compare the number of comparisions we know that Quick sort gives worst result

list is already sorted ascending or decending and when all element are equal it has time complexity of O($n^{2}$)  

in rest cases it is O($nlogn$)  hence t1>t2
4 votes
4 votes

When first element or last element is chosen as pivot, Quick Sort's worst case occurs for the sorted arrays. In every step of quick sort, numbers are divided as per the following recurrence. T(n) = T(n-1) + O(n)

So, t1>t2

Answer:

Related questions

31 votes
31 votes
5 answers
1
61 votes
61 votes
10 answers
2
go_editor asked Sep 28, 2014
30,682 views
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the...
19 votes
19 votes
4 answers
3
go_editor asked Sep 28, 2014
5,160 views
The function $f(x) =x \sin x$ satisfies the following equation: $$f''(x) + f(x) +t \cos x = 0$$The value of $t$ is______.
54 votes
54 votes
4 answers
4
go_editor asked Sep 28, 2014
18,709 views
Which of the regular expressions given below represent the following DFA?$0^*1(1+00^*1)^* $$0^*1^*1+11^*0^*1 $$(0+1)^*1$I and II onlyI and III onlyII and III onlyI, II an...