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

The Gateway to Computer Science Excellence

+24 votes

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:

- $165$
- $90$
- $75$
- $65$

0

@the_bob optimal merge patterns - https://www.includehelp.com/algorithms/optimal-merge-pattern-algorithm-and-example.aspx

+26 votes

Best answer

Arrange files in increasing order of records:

$\overset{\boxed5}{\text{D}}\quad \overset{\boxed{10}}{\text{A}}\quad\overset{\boxed{15}}{\text{C}}\quad\overset{\boxed{20}}{\text{B}}\quad\overset{\boxed{25}}{\text{E}}$

$\qquad\qquad\qquad\qquad\color{blue}{75}$

$\qquad\qquad\quad\color{blue}{30}\qquad\qquad\qquad\color{blue}{45}$

$\qquad\quad\color{blue}{15}\qquad\overset{\boxed{\text{C}}}{15}\qquad\qquad\overset{\boxed{\text{B}}}{20}\qquad\overset{\boxed{\text{E}}}{25}$

$\quad\overset{\boxed{\text{D}}}{5}\qquad\overset{\boxed{\text{A}}} {10}$

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

Correct Answer: $A$

$\overset{\boxed5}{\text{D}}\quad \overset{\boxed{10}}{\text{A}}\quad\overset{\boxed{15}}{\text{C}}\quad\overset{\boxed{20}}{\text{B}}\quad\overset{\boxed{25}}{\text{E}}$

$\qquad\qquad\qquad\qquad\color{blue}{75}$

$\qquad\qquad\quad\color{blue}{30}\qquad\qquad\qquad\color{blue}{45}$

$\qquad\quad\color{blue}{15}\qquad\overset{\boxed{\text{C}}}{15}\qquad\qquad\overset{\boxed{\text{B}}}{20}\qquad\overset{\boxed{\text{E}}}{25}$

$\quad\overset{\boxed{\text{D}}}{5}\qquad\overset{\boxed{\text{A}}} {10}$

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

Correct Answer: $A$

+1

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!

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!

+7

"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

Why isn't this like- When we are merging the file with 5 records with another file of 10 records then the least no of records(i.e one with #records=5) among them would be moved to another file. Thus reducing no of movements to just 5? Why there is a need to use another file?

0

@Mamta , what if there is no space in other file to contain these 5 records :P ..Actually given question is an example of optimal merge pattern which follows greedy strategy for optimal solution. For this , Files should be sorted and then we merge these sorted files to make one sorted file...In question , it is not mentioned the word "sorted" but I think we should have to assume it.

+5 votes

+2

@ suneeta m and n are the size of 2 files to which we are merging by using optimal merge pattern of greedy approach

+3

@ramswaroop

for getting the number of comparisons we need to use formula (m+n-1).

here m,n is the size of the file.

for example,

m=b=5;

n=a=10;

when we merge these two files we need to do the comparison between the elements of b and a so it takes

10+5-1=14(comparison requires ), here why we subtract 1 bczz we need not to compare the last element.

for getting the number of comparisons we need to use formula (m+n-1).

here m,n is the size of the file.

for example,

m=b=5;

n=a=10;

when we merge these two files we need to do the comparison between the elements of b and a so it takes

10+5-1=14(comparison requires ), here why we subtract 1 bczz we need not to compare the last element.

+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

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

+1 vote

**Sorted files 5,10,15,20,25**

**1) merge min two -- 15,15,20,25 | merges=5+10=15**

**2) next two -- 30,20,25 -> reordering -- 20,25,30 | merges = merges+15+15=15+(15+15) = 45**

**3) next two -- 45,30 --> reordering -- 30,45 | merges= merges+ 20+25 = 45+(20+25) = 45+45= 90**

**4) last two -- 75 | merges = merges+45+30 = 90+(45+30) = 90+75 = 165**

**so, 165 is the answer**

52,345 questions

60,470 answers

201,795 comments

95,272 users