36 votes 36 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$ Algorithms gate1999 algorithms normal greedy-algorithm + – Keith Kr asked Sep 12, 2014 • edited Oct 28, 2017 by kenzou Keith Kr 14.9k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments neel19 commented Oct 6, 2020 reply Follow Share The question didn’t mention that the records should be sorted, then why are we solving it for sorted order? 2 votes 2 votes shubhendra-20 commented May 9, 2021 reply Follow Share We are required to find the minimum number of record movements, which is possible only by optimal merge and in this method we sort in ascending order. 1 votes 1 votes Abhishek Rauthan commented Jan 4, 2023 i edited by Abhishek Rauthan Jan 4, 2023 reply Follow Share if ask for no. of comparison then in worst case max no. of comparison would be m+n-1 so 14+29+44+74=161 but what about best case? is this correct? minimum no. of comparison would be min(m,n) so 5+15+20+30=70? 0 votes 0 votes Please log in or register to add a comment.
Best answer 35 votes 35 votes 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$ Pooja Palod answered Oct 9, 2015 • edited Apr 29, 2019 by Naveen Kumar 3 Pooja Palod comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments ankitgupta.1729 commented Oct 8, 2018 reply Follow Share @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. 3 votes 3 votes toxicdesire commented Sep 29, 2020 reply Follow Share How do we assume that the records should be sorted? This is not a trivial thing to assume. What's the answer if records didn't need to be in sorted order? 0 votes 0 votes Roshni22 commented Jan 10, 2022 reply Follow Share For those who are wondering why records should be in sorted order as it’s not mentioned in question to merge the files in sorted order, “ The files are merged in "sorted order of number of records" just to ensure minimum moves while merging ( you can try merging files in any random order to check other cases ) assuming there is no enough space to merge one file inside another file” .Hence, the sequence of records inside the files and their comparison is of no significance here simply appending records or one file followed by records of another file won’t change the number of moves. 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes No of movements=15+30+45+75=165 abhishekmehta4u answered Mar 22, 2018 abhishekmehta4u comment Share Follow See all 4 Comments See all 4 4 Comments reply suneetha commented Jan 8, 2019 reply Follow Share what is the meaning of m and n will you give explanation 2 votes 2 votes talha hashim commented Jan 14, 2019 reply Follow Share @ suneeta m and n are the size of 2 files to which we are merging by using optimal merge pattern of greedy approach 2 votes 2 votes Ram Swaroop commented Mar 14, 2019 reply Follow Share What are those files m, n 0 votes 0 votes air1ankit commented Mar 25, 2019 reply Follow Share @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. 5 votes 5 votes Please log in or register to add a comment.
3 votes 3 votes Try to implement it like Huffman coding. 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 rishav1995 answered Sep 4, 2019 rishav1995 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 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 Keith Kr answered Feb 4, 2015 Keith Kr comment Share Follow See all 3 Comments See all 3 3 Comments reply Akash Kanase commented Nov 23, 2015 reply Follow Share Your answer is not correct.Correct ans is 165 ! 6 votes 6 votes akankshadewangan24 commented Jul 2, 2017 reply Follow Share whats the diffrence between no.of movement and comparisions ????????? @AkashKanase 0 votes 0 votes joshi_nitish commented Jul 3, 2017 reply Follow Share 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 14 votes 14 votes Please log in or register to add a comment.