Gateforum Test Series: Algorithms - Sorting

Question

. In the standard merge sort algorithm on a list of size n, what is the maximum number of times an item can be compared?

a)2

b)logn

c)n-1

d)nlogn

Comments

Is it C?

---

@minipanda i think all are wrong. if u can read the question carefully it says for an item. and floor(n/2) or (n-1)/2

---

arvin Please check this

---

Hmm right for a particular item, it should be n/2

---

yes u are right @minipanda what i did. was i followed bottom to up approach and i took for n=8 and than i considered it as binary tree. than calculated it on the basis of entire nodes of tree. and here i made silly mistake as i had to find with respect to only leaf node.

---

Won't it be

$1+2+4+8+...\frac{n}{2}$

---

@gauravkc : no see here n means number of leaf nodes and i also did the same mistake. 

---

@Minipanda, 

let take n=8, ===> 1,2,3,4,5,6,7,8 ===> check for 5 ? is it 7?

let take n=16, ===> 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ===> check for 9 ? is it 15?

 

check this formula :- $\frac{n}{2} + ⌈ log n ⌉ - 1 $

---

@shaikh : see i too did the same mistake. but here we have to consider n as leaf nodes.

---

@arvin, take it as leaf nodes only.... then you are apply just merge, right ?

---

Shaik Masthan  yes i think you are right.. at each level except the root one, the middle element is getting one comparison and at the root level it is n/2.

So no. of levels where one comparison is there is  ⌈logn⌉−1

and at the root level it's n/2.

So approximately it is n/2+⌈logn⌉−1 .

But then here the options are not in Order ..are they wanting exact number? :/

---

@shaikh :yes. see suppose n=8 so we will have 3 levels(root=level 0). at level 3 there will be only 1 comparison. at level 2 there will be 2 comparison and level3= 4comparison and finally we have all elements sorted.

.

total compasion= 1+2+4=7=(n-1)

---

i think they have asked for #minimum comparisons for a particular element in worst case.

---

@minipanda yes answer is c)

And i got ur explanation and on that basis I got this

If n=2^k

let at level 1 , L1 and L2 is merged,

An item in L1 is compared maximum times when all the items in L2 is less than item in L1.

Say at leaf level k , an item is compared only once when merging.

at level k-1  an item is compared twice when merging.

At level 2 it is compared n/2 times and after merging we get the sorted array total comparison of an item =n/2+ n/(2²)+. . . . +   .n/(2^k)    where n/(2^k) =1

                                          = n*(1-1/(2^k))

                                          = n - n/(2^k)

                                          = n-1

---

@Minipanda,

that formula is exact value but not the order.

may be options wrong? we can't trust the options always right ?

check this question https://gateoverflow.in/68844/test-series, options are not matching

( i know there is no relation between the questions )

 

@arvin,

 we will have 3 levels(root=level 0). at level 3 there will be only 1 comparison

why one comparission required at level 3? we can optimize it right?

at level 2 there is only one comparission

at level 1 there is only one comparission

at level 0 there is four comparission ===> 4+1+1 = 6

---

@shaikh it says maximum number of times an item can be compared. so i have considered a particular item. i mean a single element that gets leveled up at each level comparison

---

@arvin,

can you please give which number is comparing 15 times in array of 16 numbers?

---

@shaikh bro u not getting my point. i am considering a worst case

---

@shaikh see i know that as every comparison happens from lower level the position of the element a will change or if does not changes than we will have only one comparison for a with the element in another array. but if u consider worst case comparison that can happen at every level forgetting the actual value of element u will have more comparisons at each level...

and its (n-1) when i considered worst case comparison at every level.

.

it  might not be possible with real values..

---

Nice one arvin 

"it  might not be possible with real values.. "  - Take this array : 10,9,8,7,1,2,3,4 and concentrate on comparisons over 9. I think then we will get 1+2+4=7 comparisons. Please check.

---

@minipanda yes it will work. 

"it  might not be possible with real values.. "

yes i just assumed that it might not be possible.

because sometimes i just give up on lamo :p.. but thanks @minipanda

and moreover i must say that : even it could be 9,10,7,8,1,2,3,4.

as they are asking only for comparison and whether we have swapped it or not its not necessay...

---

arvin Yes..that can also be another i/p array :P

---

@arvin, @MiNiPanda

Now i got where you are going to be wrong...

let take your input 10,9,8,7,1,2,3,4  as per your approach

at low level ( consider it as i^th level ) only one element---> no comparisons

( i - 1 )^th level only 2 elements -----> 1 comparisons ( concentrate on 9, compared with 10 ) ===> after merging array look like 9,10 .... 7,8 .... 1,2... 3,4...

( i - 2 )^th level only 4 elements -----> 2 comparisons ( concentrate on 9,  compared with 7 and 8 ) ===> after merging array look like 7,8,9,10 .... 1,2,3,4...  ====> note that in this case 9 should be change ( if an element compared with every element of the remaining divided array ( divided array should have atleast 2 numbers ) then most compared element of your array should change )

( i - 3 )^th level only 4 elements -----> 0 comparisons ( concentrate on 9,  compared with none ) ===> after merging array look like 1,2,3,4... 7,8,9,10.....

---

I modified the code for merge sort. The maximum number of comparisons an element is having is  n/2+⌈logn⌉−1

I didn't get how yet.

---

Shaik Masthan Yeah right.. I did a mistake there -_-

arvin  your statement was True.." it  might not be possible with real values.. "

gauravkc Yes.. But that is an approximate value right? Like if n is not multiple of 2 then n/2 will give fraction.. so i think it is the ceil( n/2+⌈logn⌉−1 ).

---

@shaikh yes u are right..

@minipanda :/

---

@shaik brother I didn't get this line please explain a bit more 

note that in this case 9 should be change ( if an element compared with every element of the remaining divided array ( divided array should have atleast 2 numbers ) then most compared element of your array should change )

---

@MiNiPanda,

 it  might not be possible with real values..

brother, arvin takes his values as a,b,c,d,e,f,g... therefore there must be some criteria to compare them, right

then also a can't be make 4 comparissions with e,f,g,h when a compared with c and d

---

@shaikh yes surely you are right. this is why? i was not sure on my this answer as it is not possible for the real values in real time. with real values we will have different answer what u have given.

---

@Rishav Kumar Singh, @arvin

 if an element compared with every element of the remaining divided array ( divided array should have atleast 2 numbers ) then most compared element of your array should change 

it means

let take array a,b,c,d,e,f,g,h ( consider we are merging )

at first level, we look that array in the angle of one element each

 ....... a.........b.......c.....d......e......f.......g......h........

the next level we have 2 elements each ===> a compared with b

After merginig .....a,b.....c,d.....e,f...g,h....

the next level we have 4 elements each ===> ( an element compared with every element of the remaining divided array ) when will a compared to c and d ? it happens when a is grater than c and d only ===> ( then most compared element of your array should change ) in the sorted array a must be changed it's position to before 'd' or after 'd' 

After merginig .....c,d,a,b.....e,f,g,h.... ===> it can't create more comparissions in further level....

---

@shaikh yes my result was based for worst case comparisons at each level without real values. so it may or may not be valid.

Answer 1

I think , if we want the maximum number of comparisons to be made for an element then let us assume that element to be the comapared is the biggest in the given array , so at level 0 , 2^0 comparison is done

 At level 1, 2^1 comparisons will be done

At level 2, 2^2 comparisons will be done

.

.

.

Similarly at kth level 2^k comparison will be done .

Therefore total number of comparisons made will be summation of all the comparisons.

Plz comment if this analysis is wrong

 

.

Comments

read the comments