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

The minimum number of record movements required to merge five files A (with $10$ records), B (with $20$ records), C (with $15$ records), D (with $5$ records) and E (with $25$ records) is:

  1. $165$
  2. $90$
  3. $75$
  4. $65$
asked in Algorithms by Boss (6.3k points)
edited by | 1.5k views

Notice difference with respect to question --> https://gateoverflow.in/1997/gate2014-2-38

3 Answers

+21 votes
Best answer

Arrange files in increasing order of records

D  A   C   B   E

$5$ $10$ $15$ $20$ $25$

                              $75$

              $30$                           $45$

    $15$           $15$ (C)    $20$ (B)      $25$ (E)

$5$ (D)     $10$ (A)

No of movements$=15+30+45+75=165$

answered by Veteran (33.9k points)
edited by
Hi Pooja

I am not able to follow how did you get 45 ?

Could u please explain it for me.

Thanks in advance.

# Update:Understood.! First three files u merged and then u merged last two files and then clubbed u merged the two!
YES

"This is different from another greedy problem in which we simply merge the files one into another in after arranging them in ascending order."

In the above solved question, we have used to "MERGE" procedure from merge sort which takes one element of each array compare them and put them in the final or output array.

  • Movement of record is analogous to the movement of elements of arrays which we merge and no. of element get moved in MERGE producer are "all" i.e m+n.
  • Comparisons would be just m+n-1 as last element remaining does not need any comparison to put it into the output array.
    more:-https://gateoverflow.in/1997/gate2014-2-38?show=7132#c7132
+2 votes
Sort the files: 5, 10, 15, 20, 25.
Merge the smallest two records 15, 15, 20, 25
Merge 30, 20, 25
Sort 20, 25, 30
Merge 45, 30
75. So C is the answer
answered by Boss (6.3k points)
Your answer is not correct.Correct ans is 165 !
whats the diffrence between no.of movement  and comparisions ?????????

@AkashKanase
if you will count no of comparison it will come out to be 165-4=161 and nos of movement= 165, because no of comparison on merging two nodes will be m+n-1, but the record movement will be m+n..because you have to move entire records of both nodes to newly created node
0 votes
(a) 165
answered by (27 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

32,620 questions
39,267 answers
109,738 comments
36,656 users