Chapter II
Divide and Conquer Methods
In this chapter, we study about divide and conquer method. As the name suggests in this strategy
the big problem is broken down into smaller sub problems and solution to these sub problems is
obtained.
Divide and Conquer Technique
Binary Search
To find the minimum element from the set of n numbers by using following algorithm, Also, we
require total (n-1) comparison to obtain minimum value. Similarly we can obtain the maximum
value from an array A in (n-1) comparison. Here is an algorithm for finding maximum element
Algorithm Minimum_Maximum_val(A[1..n])
{
Min ←A[1]
Max ←A[1]
For (i←2 to n) do
{
If (min>A[i])then
Min ← A[i]
If (A[i] > Max)then
Max ← A[i]
}
Return Min,Max
}
We can obtain minimum from min and maximum from max variable from above algorithm.
Consider following array
Algorithm Min_Max_val(i,j,min,max)
{
If (i==j) then {
max = A[i], min =A[j] }
elseif (i= j-1) {
if (A[i]<A[j] ) then {
max ← A[j], min← A[i] }
else {
max ← A[i], min← A[j] }
}
mid ← (i+j)/2
Max_Min_val(I,mid,max,min)
Max_Min_val(mid+1,j,max_new,min_new)
If(max<max_new)then
max←max_new
if (min>min_new) then
min←min_new
}
MERGE SORT
As another example divide-and-conquer, we investigate a sorting algorithm that has the nice
property that is the worst case its complexity is O(n log n)
This algorithm is called merge sort
We assume throughout that the elements are to be sorted in non-decreasing order.
Given a sequence of ‘n’ elements a[1],…,a[n] the general idea is to imagine then split into 2 sets
a[1],…..,a[n/2] and a[[n/2]+1],….a[n].
Each set is individually sorted, and the resulting sorted sequences are merged to produce a
single sorted sequence of ‘n’ elements.
Thus, we have another ideal example of the divide-and-conquer strategy in which the splitting is
into 2 equal-sized sets & the combining operation is the merging of 2 sorted sets into one.
Algorithm For Merge Sort:
1. Algorithm MergeSort(low,high)
2. //a[low:high] is a global array to be sorted Small(P) is true if there is only one element
3. //to sort. In this case the list is already sorted.
4. {
5. if (low<high) then //if there are more than one element
6. { //Divide P into subproblems , find where to split the set
7. mid = [(low+high)/2];
8. //solve the subproblems.
9. mergesort (low,mid);
10. mergesort(mid+1,high);
11. //combine the solutions .
12. merge(low,mid,high);
13. } }
Algorithm: Merging 2 sorted subarrays using auxiliary storage.
1. Algorithm merge(low,mid,high)
2. //a[low:high] is a global array containing
3. //two sorted subsets in a[low:mid]
4. //and in a[mid+1:high].The goal is to merge these 2 sets into
5. //a single set residing in a[low:high].b[] is an auxiliary global array.
6. {
7. h=low; I=low; j=mid+1;
8. while ((h<=mid) and (j<=high)) do
9. {
10. if (a[h]<=a[j]) then
11. {
12. b[I]=a[h];
13. h = h+1;
14. }
15. else
16. {
17. b[I]= a[j];
18. j=j+1;
19. }
20. I=I+1;
21. }
22. if (h>mid) then
23. for k=j to high do
24. {
25. b[I]=a[k];
26. I=I+1;
27. }
28. else
29. for k=h to mid do
30. {
31. b[I]=a[k];
32. I=I+1;
33. }
34. for k=low to high do a[k] = b[k];
35. }
Consider the array of 10 elements a[1:10] =(310, 285, 179, 652, 351, 423, 861, 254, 450, 520)
Algorithm Mergesort begins by splitting a[] into 2 sub arrays each of size five (a[1:5] and
a[6:10]).
The elements in a[1:5] are then split into 2 sub arrays of size 3 (a[1:3] ) and 2(a[4:5])
Then the items in a a[1:3] are split into sub arrays of size 2 a[1:2] & one(a[3:3])
The 2 values in a[1:2} are split to find time into one-element sub arrays, and now the merging
begins.
(310| 285| 179| 652, 351| 423, 861, 254, 450, 520)
Where vertical bars indicate the boundaries of sub arrays.
Elements a[I] and a[2] are merged to yield,
(285, 310|179|652, 351| 423, 861, 254, 450, 520)
Then a[3] is merged with a[1:2] and
(179, 285, 310| 652, 351| 423, 861, 254, 450, 520)
Next, elements a[4] & a[5] are merged.
(179, 285, 310| 351, 652 | 423, 861, 254, 450, 520)
And then a[1:3] & a[4:5]
(179, 285, 310, 351, 652| 423, 861, 254, 450, 520)
Repeated recursive calls are invoked producing the following sub arrays.
(179, 285, 310, 351, 652| 423| 861| 254| 450, 520)
Elements a[6] &a[7] are merged.
Then a[8] is merged with a[6:7] (179, 285, 310, 351, 652| 254,423, 861| 450, 520)
Next a[9] &a[10] are merged, and then a[6:8] & a[9:10]
(179, 285, 310, 351, 652| 254, 423, 450, 520, 861 )
At this point there are 2 sorted sub arrays & the final merge produces the fully
sorted result. (179, 254, 285, 310, 351, 423, 450, 520, 652, 861)
If the time for the merging operations is proportional to ‘n’, then the computing time for
merge sort is described by the recurrence relation.
T(n) = { a n=1,’a’ a constant
2T(n/2)+cn n>1,’c’ a constant.
When ‘n’ is a power of 2, n= 2^k, we can solve this equation by successive substitution.
T(n) =2(2T(n/4) +cn/2) +cn
= 4T(n/4)+2cn
= 4(2T(n/8)+cn/4)+2cn
*
*
= 2^k T(1)+kCn.
= an + cn log n.
It is easy to see that if s^k<n<=2^k+1, then T(n)<=T(2^k+1). Therefore,
T(n)=O(n log n)
QUICK SORT
The divide-and-conquer approach can be used to arrive at an efficient sorting method different
from merge sort.
In merge sort, the file a[1:n] was divided at its midpoint into sub arrays which were
independently sorted & later merged.
In Quick sort, the division into 2 sub arrays is made so that the sorted sub arrays do not need to
be merged later.
This is accomplished by rearranging the elements in a[1:n] such that a[I]<=a[j] for all I between 1
& n and all j between (m+1) & n for some m, 1<=m<=n.
Thus the elements in a[1:m] & a[m+1:n] can be independently sorted.
No merge is needed. This rearranging is referred to as partitioning.
Function partition of Algorithm accomplishes an in-place partitioning of the elements of a[m:p-
1]
It is assumed that a[p]>=a[m] and that a[m] is the partitioning element. If m=1 & p-1=n, then
a[n+1] must be defined and must be greater than or equal to all elements in a[1:n]
The assumption that a[m] is the partition element is merely for convenience, other choices for
the partitioning element than the first item in the set are better in practice.
The function interchange (a,I,j) exchanges a[I] with a[j].
Algorithm: Partition the array a[m:p-1] about a[m]
1. Algorithm Partition(a,m,p)
2. //within a[m],a[m+1],…..,a[p-1] the elements are rearranged in such a manner that if
3. //initially t=a[m],then after completion a[q]=t for some q between m and
4. //p-1,a[k]<=t for m<=k<q, and a[k]>=t for q<k<p. q is returned , Set a[p]=infinite.
5. {
6. v=a[m];I=m;j=p;
7. repeat
8. {
9. repeat
10. I=I+1;
11. until(a[I]>=v);
12. repeat
13. j=j-1;
14. until(a[j]<=v);
15. if (I<j) then interchange(a,i.j);
16. }until(I>=j);
17. a[m]=a[j]; a[j]=v;
18. retun j;
19. }
Algorithm Interchange(a,I,j)
1. //Exchange a[I] with a[j]
2. {
3. p=a[I];
4. a[I]=a[j];
5. a[j]=p; }
Algorithm: Sorting by Partitioning
1. Algorithm Quicksort(p,q)
2. //Sort the elements a[p],….a[q] which resides
3. //is the global array a[1:n] into ascending
4. //order; a[n+1] is considered to be defined
5. // and must be >= all the elements in a[1:n]
6. {
7. if(p<q) then // If there are more than one element
8. {
9. // divide p into 2 subproblems
10. j=partition(a,p,q+1);
11. //’j’ is the position of the partitioning element.
12. //solve the subproblems.
13. quicksort(p,j-1);
14. quicksort(j+1,q);
15. //There is no need for combining solution.
16. }
17. }
Record Program: Quick Sort
#include <stdio.h>
#include <conio.h>
int a[20];
main()
{
int n,I;
clrscr();
printf(“QUICK SORT”);
printf(“\n Enter the no. of elements “);
scanf(“%d”,&n);
printf(“\nEnter the array elements”);
for(I=0;I<n;I++)
scanf(“%d”,&a[I]);
quicksort(0,n-1);
printf(“\nThe array elements are”);
for(I=0;I<n;I++)
printf(“\n%d”,a[I]);
getch();
}
quicksort(int p, int q)
{
int j;
if(p,q)
{
j=partition(p,q+1);
quicksort(p,j-1);
quicksort(j+1,q); }}
Partition(int m, int p)
{
int v,I,j;
v=a[m];
i=m;
j=p;
do
{
do
i=i+1;
while(a[i]<v);
if (i<j)
interchange(I,j);
} while (I<j);
a[m]=a[j];
a[j]=v;
return j; }
Interchange(int I, int j)
{
int p;
p= a[I];
a[I]=a[j];
a[j]=p;
}
Output:
Enter the no. of elements 5
Enter the array elements
38152
The sorted elements are,
12358
Strassen’s Matrix Multiplications
Analysis of Algorithm
