Divide and Conquer algorithm

                                                           CONTENTS

List of topics that we cover in the article:

  • What is Divide and conquer?
  • How problems are solved using Divide and conquer?
  • Running times for sorting algorithms.
  • Examples of Divide and conquer algorithm.
  • Merge sort
  • Quick sort
  • Binary search
  • Strassen’s Matrix multiplication
  • Closest Pair
  • Implementation of Merge sort.
  • Quick sort algorithm.
  • Pseudocode for Quicksort.  
  • Conclusion.

                                                 DIVIDE AND CONQUER ALGORITHM

  • What is Divide and Conquer?

Divide and conquer is the most important algorithm in the data structure. The main aim of Divide and conquer is to solve the problem by dividing the complex problem into sub-problems solves in easier manner and later combines all the subproblems to solve the actual problem.

  • How problems are solved using divide and conquer?

Usually divide and conquer having the three parts:

Divide: Divide the problem into sub problems.

Conquer: In this step all the sub-problems are solved recursively.

Combine: Here all the subproblems are combined to solve the complex problem.

Running times for sorting algorithm:

  • Examples of Divide and conquer:
  • Merge sort
  • Quick sort
  • Implementation of Merge sort:

Merge sort is an example for Divide and conquer algorithm. It is the most important sorting algorithm.

  • Merge sort Algorithm:

MergeSort(A, p, r)

If (p>r)

  • q=(p+r)/2;
  • mergesort(A,p,q)
  • mergesort(A,q+1,r)
  • merge(A,p,q,r)

In order to sort an array we need to call MergeSort(A,0,length(A)-1)

  • Let’s see how the merge sort works:
  • create the duplicate copies of subarrays L<-A[p..q] and M <- A[q+1..r]
  • create three pointers i,j,k
    • i maintains current index of L, starting at 1
    • j maintains current index of M, starting at 1
    • k maintains current index of A[p..q], starting at p
  • select all the larger among the elements from L and M and place them in correct position at A[p..q]
  • select the remaining elements and put in A[p..q]
  • code looks like:

void merge(int A[], int p, int q, int r)

int n1 = q – p + 1;

int n2 = r – q;

int L[n1], M[n2];

for(i = 0; i< n1;i++)

L[i] = A[p+i];

for (j = 0; j<n2;j++)

 M[j] = A[q+1+j];

int I, j, k;

I = 0;

J = 0;

K = p;

While (i < n1 && j < n2)

{

arr[k] = L[i];

i++;

}

​else

{

arr[k] = M[j];

j++;

}

K++;

}

While (i < n1)

{

A[k] = L[i];

i++;

K++;

​}

While (j < n2)

{

A[k] = M[j];

j++;

}

}

Merge sort, quick sort, binary search, strassen’s matrix multiplication are the problems that can be solved by Divide and Conquer technique.

 

For better under understanding lets see one more sorting technique called quick sort.

 

Quick sort is the most efficient algorithm and divides the array into smaller arrays and choosing one element as pivot the elements which are less than the pivot element placed at left side and the elements which are greater than pivot element placed at right side of the pivot.

Let’s see the implementation of quick sort:

This is how quick sort works.

Quick sort Algorithm:

Step:1

         Make right most index as a pivot value.

Step:2

        Divide the array using pivot value.

Step:3

        Sort the left part of array recursively.

Step:4

        Sort the right part of array recursively.

Quick sort pseudocode:

           Procedure quicksort (left, right)

              If right-left <= 0

                    return

              else

                   pivot = A[right]

                   partition = partitionFunc(left, right,pivot)

                   quicksort (left, partition-1)

                   quicksort (partition+1, right)

              end if

         end procedure

Advantages of quick sort:

  • Cache performance is very high when compared to other sorting algorithm.
  • No need of extra memory.

Conclusion:

Finally, Divide and Conquer algorithm works more efficiently

Take a complex problem to be solved, divide the problem into small sub-problems and solve the sub problems and later combine all the sub-problems to get the solution for the problem this process can be done by recursively.

The important factor in Divide and conquer algorithm is works on multiprocessor system.

Contributor's Info

Created:
1Comment
Tharun sai @tharunsaikalimi 7 Oct 2018 12:50 am
Nice one
Understanding Merge Sort

In order to understand how merge sort works, we first need to talk about merging two sorted lists. So, if we are given two sorted lists:

 4  15  16  50                    8  23  42  108

and we have to sort them into one list we can take the advantage of the fact that they are sorted lists. The first element of the new sorted list must contain the smallest element. Now, as we know these lists are already sorted that means we just need to compare the first element of both the lists and whichever is small get inserted into the new list. That means, we compare 4 and 8 and as 4 is small it gets into the new list. Then we compare 15 and 8, the first element of first and second list and as 8 is small it gets into the new list. We continue with the same procedure until every element from 1st and 2nd list gets into the new list. That's exactly how merge sort works.

There are two big steps in the process of merge sort:

1) Continuously split the number of elements into half until we have a bunch of lists which have only       one element in them(single elements are always sorted i.e. we have a bunch of sorted lists).

2) Repeatedly merge pairs of lists using the merge algorithm we discussed above.

Let's take an example. Suppose we have to sort the given list:

     108  15  50  4  8  42  23  16

Let's split it into half

      108  15  50  4   |   8  42  23  16

Now, we have two lists, we repeat until we have every element seperated into individual list as:

     108  |  15  |  50  |  4  |  8  |  42  |  23  |  16

Now, we merge first two lists i.e. 108 and 15 using the above method that is we compare and place the small one in the new list. So, the list becomes: 

     15  108  |  50  |  4  |  8  |  42  |  23  |  16

Again, we merge 15 108 and 50, new list become:

     15  50  108  |  4  |  8  |  42  |  23  |  16

Repeatedly doing this we get:

     4  8  15  16  23  42  50  108

this is a sorted list!

Though, merge sort generally works better than bubble, insertion and selection sort but there is also a drawback, in order to merge two lists it needs extra space.

That's the basics of merge sort. Go ahead and try to implement it and in case you need some help check out the references.

Contributor's Info

Created:
0Comment