divide and conquer

[vgoel38]

in the algorithms of divide and conquer, it is shown that the function works simultaneously like the following way:

                     8
          4                    4
      2       2             2      2
          4                    4
                     8                                                                                      

but can it actually happen like this?
A function cant be called simultaneously called two times by itself. So,shouldnt it be like this??

                         8
                 4
             2
                 4
                     2
                 4
                         8
                                  4
                              2
                                  4
                                      2
                                  4
                         8
 

[georgep]

I think I understand what you mean, and I think you're right.

For example, this animation shows how merge sort works: http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif

However, obviously that isn't how it works, it's just illustrated that way to be simpler.

[vgoel38]

yes, exactly...so in merge sort also..the first half will be sorted first even before splitting the second half..right?

[vgoel38]

but why is it illustrated like this when it is actually wrong..u cant say its simple but wrong..But since this notion has been accepted worldwide and been applied everywhere..so i m confused where i am being incorrect??

[georgep]

Well, as I see it, it works in the same way whether you split each half at the same time or not.

The idea behind the divide and conquer method is that you split it into halves. In a simple representation (like the above animation) it is quicker to show it that way, and it is more clear what is happening (ie. you don't leave half until the end).

However, if anyone ever gives you a full explanation, they will always explain how it really works. This video gives a nice example, in the correct way: http://www.youtube.com/watch?v=t8g-iYGHpEA&feature=player_detailpage#t=54s

[vgoel38]

yeah..the video says the same..
P.S.- the video is cool

[vgoel38]

but the problem that comes up is annoying me is this:
to find min and max values in an array, I came across this following algo:

                                8
               4(i)                              4(ii)
        2(i)        2(ii)                2(iii)      2(iv)

now, we find minL and maxL in 2(i) and minR and maxR in 2(ii). Then we compare minL to minR and maxL to maxR and come up with minL and maxL of 4(i).

similarly, we do same with 2(iii) and 2(iv) and get minR and maxR of 4(ii).

then we compare minL to minR and maxL to maxR to get the ultimate min and max values of 8.

But now..how can i apply this concept when i know the array doesnt split simultaneously. Then, I came up with a solution that instead of comparing the minL and maxL to minR and maxR, i'll keep two global variables min and max and compare the minL,maxL,minR,maxR to them and update max and min at each time i calculate minL,maxL,minR,maxR.

But, main problem is I am not able to follow the exact algo pattern of comapring minL,maxL to minR,maxR and i want to do that...!!!!!!!!!

[georgep]

I don't think I understand the method here. If you are trying to find the minimum and maximum values in an array, you have to look at every single element. Iterating through the array is simpler and is as efficient as you can get. I don't see why divide an conquer would be the way to go here.