To much who don”t know , Divide and conquer I am going to talk about, isn”t related to politics. It”s about Algorithms, Yes, it”s a theory!!
Alot of Algorithms use the Divide and conquer theory Like the Quick sort and Merge sort
Divide and Conquer does contain three steps as follows : Divide – Conquer – Combine
It”s all about having a big problem that you want to solve. so virtually you are going to divide it into smaller problems which means the Divide step
in the Conquer step we literally conquer the smaller problems which we had from the divide step recursively ( using recursion)
in the Combine step, since you are conquering recursively the smaller problems you are actually combining them to result the big problem which we wanted to solve.
to discuss the features of Divide and Conquer we need to work on some example that help us fully understand what does Divide and Conquer mean. so we are going to talk about Merge sort
Merge Sort is a fast sorting algorithm
Technically, we recursively divide and sort the given array so as we said “we Divide the problem into two smaller problems”
so we will sort the first half of the big array and then sort the second half. If we suppose the length of the given array is n so we will sort the two sub arrays A[1 : n/2] and A[n/2 1 : n]
and after we sort the two sub arrays we merge them (Combine).
to Summarize what we said :-
Merge Sort A[n]
1- Recursively sort A[1 : n/2] and A[n/2 1 : n]
2- Merge the two sorted sub Arrays
Actually, what happens is like when you sort cards ( كوتشينه ) so assume you have a big list of cards [2,6,9,5,8,1,4,3,0,7]. so first we divide it into two sub lists
A1=[2,6,9,5,8] , A2= [1,4,3,0,7]
so i want to merge these two lists into one sorted list so what we do is sort these two lists and then compare and combine. after sorting we have A1=[2,5,6,8,9] , A2=[0,1,3,4,7]
so in the compare and combine step we compare the first element of the first array to the first element of the second array and pick the smaller and add to the big array. so we do what follows:-
Compare (2) to (0) and since (0) is smaller we pick (0) and put it in the big array, since we took (0) away from the 2nd list the first element of the 2nd list will be (1) so we compare again
Compare (2) to (1) -> 1 is smaller than 2 so we add 1
Compare (2) to (3)-> 2 is smaller than 3 so we add 2
till both lists are empty..eventually we will have our big array sorted.
anyway i will show you some code which will make things more clear, the following code is a merge sort JAVA code
the code is a bit complicated but can be implemented in anyway since the concept is understood.
first we define the master function which will have the big array as a parameter and in it we will create a temporary array where the sub arrays will be combined.and we call another merge sort function which receive the big array and a temporary array and the left and right indexes of the array
Actually, this is the function which will divide (Recursively divide) the array. as you may notice it recursively call itself on two lists, the first half and second half.. which will end up best online casino giving us a tree as this
but as u may have noticed we have put a boundary condition for the whole block [if(left<right)] because on leaves we will have left= right, and a leaf mean we are having a list of one element only which is already sorted and the least small problem we cloud get.
after we recursively call the function we have to merge the divided elements so we go from down to up.
but what is more important is how the merge algorithm works.
since we have two list, we virtually divide them by obtaining the left and right positions which are initially the first element of each list and the end of each list so we can bound them.
As we said before we always compare the first element of each sub list. so you may have guessed that the LeftPos and RightPos are like pointers each iterates on it”s list. And we compare and add but what if the left list has no elements left and right has more than one element left. that”s why we first kept comparing while the Position of any pointer didn”t exceed it”s End but if it did we quit the first loop and decide which list have elements left and then append then to the big array. this saves time…..
So you may have made the big picture in your mind. we divided..and then conquered and merged. trying to trace the merge sort code is quite fuzzy so it”s better to understand it in graphs not to trace the code because all these divide and conquer things are done virtually, doing such a thing by keeping on instantiating new arrays will only use too much memory, and if you are coding in C that will cost you few more lines and thinking.
More can be done using the Divide and Conquer algorithm like binary search and powering numbers. actually much more fun can be done and it”s a quite great theoretical solution to lots of problems.