The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
3.9k views

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$
asked in Algorithms by Veteran (103k points)
edited by | 3.9k views

6 Answers

+29 votes
Best answer
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.
answered by Junior (817 points)
edited by
+3
thank you for your explanation
0
why will the no of recursive calls be same??
+16

Total number of comparisons made by partition algorithm for input array of size $n = n+1$
(See 2nd page here http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/quicksort.pdf)
[12345]           6
[1] [2345]       5
[2] [345]         4
[3] [45]            3
[4] [5]
Total = 6+5+4+3 = 18

[12345]            6
[123] [45]        4+3
[1] [23] [4][5]  3
[2] [3]

total = 6+4+3+3 = 14
Hence $t_1 \gt t_2$

+2
How does the splitting take place this way? For the ist case u hv taken elements less than or equal to pivot in left list and elements greater than pivot in right list and in 2nd case less than pivot in left list and elements greater or equal to  pivot in right list ?
+13 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.

answered by (313 points)
+3

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

Total 6 

0
it should be 4 1 2 3 5 in second  case.
+2
this seems intuitively correct to me though selected answer has different logic. I wonder which is correct. :(
+10 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
answered by (327 points)
+3 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

answered by Loyal (8.5k points)
–3 votes
both arrays are worst case example of Quick sort .∴ t1=t2.
answered by Active (1k points)
0
Array 2 is not worst case example.
–5 votes

i think equal number of comparisons are required as the pivot element is always the highest or lwest element in the current array being worked on

answered by Boss (14.3k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,079 questions
47,675 answers
147,469 comments
62,393 users