ANALYSIS DESIGN OF ALGORITHM | OPTIMAL MERGE PROBLEM USING GREEDY APPROACH

📌Highlights: Hi friends ! In this I am going to explain about Optimal Merge Problem using Greedy Approach. In this post I covered what is optimal merge problem? , How this approach work to solve the problem?, Examples.

This approach is very simple. In this approach we simply merge those set of files / elements which have smaller values.it follow optimal search pattern.

For understanding Optimal Merge Problem, Let we understand simple merging.

Suppose if we have two shorted list. Marge these two list and create a third list.

Above figure show merge List-1 and List-2 and insert into List-3. Here both the list are shorted list. Compare element of List-1 and List-2  and insert into List-3 which one is minimum. So it is very simple method to merge two shorted list.

So here If we calculate the time taken for merging is suppose

List-1 take (m) time and List-2 takes (n) time then total time become O(m+n) i.e [bigo of (m+n)]

Note: Total time is depend on the size of list.

Now if we have more than two list of different size suppose,

Now we want to merge all these lists.For merging let we see so many merging patters: such as :

PATTERN-I

In this pattern total cost will be (11+15+17=43)

PATTERN-II

In this pattern total cost will be (11+6+17=34)

PATTERN-III

                                    

In this pattern total cost will be (6+12+17=35)

We can also find some other patterns for merging but here we can analysis if merging is done by taking two smaller values than their total will become minimum compare to other pattern.

So by taking this concept we solve the problem using greedy approach. Greedy approach says that you should always select smaller set of element for merging.For doing this we must arrange all elements in ascending order.

EXAMPLE:

Let we understand by taking an example such as.

Here given list is not arrange in order so first we arrange element of list in ascending order

we get:

Now let us follow optimal search pattern, so we should select a smaller pair of element of list and merge them.

Let we understand step by step:

First we select two smallest elements in the list and merge them such as:

After merging 5 and 10 we get 15, Now again check whether the list is in ascending order or not if not then arrange it such as:

Now the list will be (10, 15, 20, 30) which is in order.

Again select two smallest element in the list and merge them such as:

After merging 10 and 15 we get 25, Now again check whether the list is in ascending order or not if not then arrange it such as:

Now the list will be (20, 25, 30) which is in order.

Again select two smallest element in the list and merge them such as:

After merging 20 and 25 we get 45, Now again check whether the list is in ascending order or not if not then arrange it such as:

After merging 30 and 45 we get 75 and now there is no element remain for merging so the final answer will be 75 or we can say that it is a total cost.

Method / Algorithm for Optimal Merge Problem:

STEP 1: START WITH LIST

STEP 2: SORT FILE WITH INCREMENT ORDER OF LENGTH.

STEP 3: MERGE FIRST TWO FILES/ELEMENTS AND REPLACE THEM WITH                           RESULTING FILE / ELEMENT IN THE LIST.

STEP 4: REPEAT FROM STEP 1 TILL THE LIST HAS ONLY ONE FILE.

STEP 5: END

📌 Now friends ! this is the end of his post. This is all about Optimal Merge Problem using Greedy Approach. I hope this post is some thing helpful for you. We will meet with new post till continue reading...