1.
Introduction to Divide and Conquer
Divide-and-conquer method: Divide-and-conquer are probably the best known general
algorithm design technique. The principle behind the Divide-and-conquer algorithm design technique is
that it is easier to solve several smaller instance of a problem than the larger one.
The “divide-and-conquer” technique involves solving a particular problem by dividing it into one
or more cub-problems of smaller size, recursively solving each sub-problem and then “merging” the
solution of sub-problems to produce a solution to the original problem.
Divide-and-conquer algorithms work according to the following general plan.
1. Divide: Divide the problem into a number of smaller sub-problems ideally of about the same size.
2. Conquer: The smaller sub-problems are solved, typically recursively. If the sub-problem sizes are
small enough, just solve the sub-problems in a straight forward manner.
3. Combine: If necessary, the solution obtained the smaller problems are connected to get the
solution to the original problem.
The following figure shows-
Problem of
size n
Solution to Solution to
sub-problem 1 sub-problem 2
Sub-problem 1 Sub-problem 2
size n/2 size n/2
Solution to the
original problem
Fig: Divide-and-Conquer technique (Typical case).
Control abstraction for divide-and-conquer technique:
Control abstraction means a procedure whose flow of control is clear but whose primary
operations are satisfied by other procedure whose precise meanings are left undefined.
Algorithm DandC(p)
{
if small (p) then
return S(p)
else
{
Divide P into small instances P1, P2, P3 .............. Pk, k≥1;
Apply DandC to each of these sub-problems;\
return combine (DandC(P1), DandC(P1),…. (DandC(Pk);
}
}
Algorithm: Control abstraction for divide-and-conquer
DandC(p) is the divide-and-conquer algorithm, where P is the problem to be solved. Small(p) is a
Boolean valued function(i.e., either true or false) that determines whether the input size is small enough
that the answer can be computed without splitting. If this, is so the function S is invoked. Otherwise the
problem P is divided into smaller sub-problems. These sub-problems P1, P2, P3……..Pk, are solved by
receive applications of DandC.
Combine is a function that combines the solution of the K sub-problems to get the solution for
original problem ‘P’.
Example: Specify an application that divide-and-conquer cannot be applied.
Solution: Let us consider the problem of computing the sum of n numbers a0, a1,…..an-1. If n>1, we
divide the problem into two instances of the same problem. That is to compute the sum of the first [n/2]
numbers and to compute the sum of the remaining [n/2] numbers. Once each of these two sum is compute
(by applying the same method recursively), we can add their values to get the sum in question-
a0+ a1+….+an-1= (a0+ a1+….+a[n/2]-1)+ a[n/2]-1+………+ an-1).
For example, the sum of 1 to 10 numbers is as follows-
(1+2+3+4+ ......................... +10) = (1+2+3+4+5)+(6+7+8+9+10)
= [(1+2) + (3+4+5)] + [(6+7) + (8+9+10)]
= …..
= …..
= (1) + (2) +…………..+ (10).
This is not an efficient way to compute the sum of n numbers using divide-and-conquer technique.
In this type of problem, it is better to use brute-force method.
2. Quick Sort
The quick sort is considered to be a fast method to sort the elements. It was developed by CAR
Hoare. This method is based on divide-and-conquer technique i.e. the entire list is divided into various
partitions and sorting is applied again and again on these partitions. This method is also called as partition
exchange sorts.
The quick sort can be illustrated by the following example
12 6 18 4 9 8 2 15
The reduction step of the quick sort algorithm finds the final position of one of the numbers. In
this example, we use the first number, 12, which is called the pivot (rotate) element. This is accomplished
as follows-
Let ‘i’ be the position of the second element and ‘j’ be the position of the last element.
i.e. i =2 and j =8, in this example.
Assume that a [n+1] =, where ‘a’ is an array of size n.
[1] [2] [3] [4] [5] [6] [7] [8] [9] i j
12 6 18 4 9 8 2 15 2 8
First scan the list from left to right (from i to j) can compare each and every element with the
pivot. This process continues until an element found which is greater than or equal to pivot element. If
such an element found, then that element position becomes the value of ‘i’.
Now scan the list from right to left (from j to i) and compare each and every element with the
pivot. This process continues until an element found which is less than or equal to pivot element. If such
an element finds then that element’s position become ‘j’ value.
Now compare ‘i’ and ‘j’. If i <j, then swap a[i] and a[j]. Otherwise swap pivot element and a[j].
Continue the above process the entire list is sorted.
[1] [2] [3] [4] [5] [6] [7] [8] [9] i j
12 6 18 4 9 8 2 15 2 8
12 6 18 4 9 8 2 15 3 7
12 6 2 4 9 8 18 15 7 6
Since i = 7 j=6, then swap pivot element and 6th element ( jth element), we get
8 6 2 4 9 12 18 15
Thus pivot reaches its original position. The elements on left to the right pivot are smaller than
pivot (12) and right to pivot are greater pivot (12).
8 6 2 4 9 12 18 15
Sublist 1 Sublist 2
Now take sub-list1 and sub-list2 and apply the above process recursively, at last we get sorted list.
Ex 2: Let the given list is-
8 18 56 34 9 92 6 2 64
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] i j
8 18 56 34 9 92 6 2 64 2 98
8 18 56 34 9 92 6 2 64 2 8
8 2 56 34 9 92 6 18 64 3 7
8 2 6 34 9 92 56 18 64 4 3
Since i j, then swap jth element, and pivot element, we get
6 2 8 34 9 92 56 18 64
< > < >
Sublist 1 Sublist 2
Now take a sub-list that has more than one element and follow the same process as above. At last,
we get the sorted list that is, we get
2 6 8 9 18 34 56 64 92
The following algorithm shows the quick sort algorithm-
Algorithm Quicksort(i, j)
{
// sorts the array from a[i] through a[j]
If ( i <j) then //if there are more than one element
{
//divide P into two sub-programs
K: = partition (a, i, j+1);
//Here K denotes the position of the partitioning element
//solve the sub problems
Quicksort(i, K-1);
Quicksort(K=1, j);
// There is
no need for
combining
solution
}
}
Algorithm
Partition (a,
left, right)
{
// The
element
from a[left]
through
a[right] are
rearranged in such a manner that if initially
// pivot =a[left] then after completion a[j]= pivot, then return. Here j is the position where
// pivot partition the list into two partitions. Note that a[right]= .
pivot: a[left];
i:= left; j:=right;
repeat
{
repeat
i: =i+1;
until (a[i] ≥ pivot);
repeat
j: =j-1;
until (a[j] < pivot);
if( i<j) then
Swap (a, i, j);
}until (i ≥ j);
a[left]: = a[j];
a[j]: = pivot;
return j;
}
Algorithm Swap (a, i, j)
{
temp:= a[i];
a[i]: = a[j];
a[j]:= temp;
}
Advantages of Quick-sort: Quick-sort is the fastest sorting method among all the sorting methods. But it
is somewhat complex and little difficult to implement than other sorting methods.
Efficiency of Quick-sort: The efficiency of Quick-sort depends upon the selection of pivot element.
Best Case: In best case, consider the following two assumptions-
1. The pivot, which we choose, will always be swapped into the exactly the middle of the list. And
also consider pivot will have an equal number of elements both to its left and right.
2. The number of elements in the list is a power of 2 i.e. n= 2y.
This can be rewritten as, y=log2n.
Thus, the total number of comparisons would be
O (n) + O (n) + O (n) + ......... (y terms)
= O (n * y).
.
. . Efficency in best case O( n log n) ( ... y=log2 n)
Worst Case: In worst case, assume that the pivot partition the list into two parts, so that one of the
partition has no elements while the other has all the other elements.
Total number of comparisons will be-
Thus, the efficiency of quick-sort in worst case is O (n2).
Average Case: Let cA(n) be the average number of key comparisons made by quick-sort on a list of
elements of size n. assuming that the partitions split can happen in each position k(1kn)
With the same probability 1/n, we get the following recurrence relation.
The left child of each node represents a sub-problem size 1/4 as large, and the right child
represents a sub-problem size 3/4 as large.
There are log4/3 n levels, and so the total partitioning time is O(nlog4/3n). Now, there's a
mathematical fact that
logan = logbn / logba
for all positive numbers a, b, and n. Letting a=4/3 and b=2, we get that
log4/3 n=log n / log(4/3)
Quick Sort
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n2)
3. Randomized version of quick sort
What is a Randomized Algorithm?
An algorithm that uses random numbers to decide what to do next anywhere in its logic is called a
Randomized Algorithm. For example, in Randomized Quick Sort, we use a random number to pick the
next pivot (or we randomly shuffle the array).
IDEA:
Partition around a random element.
Running time is independent of the input order.
No assumptions need to be made about the input distribution.
No specific input elicits the worst-case behaviour.
The worst case is determined only by the output of a random-number generator.
Randomized quicksort analysis
Let T(n) = the random variable for the running time of randomized quicksort on an input of size n,
assuming random numbers are independent. For k = 0, 1, …, n–1, define the indicator random variable
E[Xk] = Pr{Xk = 1} = 1/n, since all splits are equally likely, assuming elements are distinct.
Quicksort in practice:
• Quicksort is a great general-purpose sorting algorithm.
• Quicksort is typically over twice as fast as merge sort.
• Quicksort can benefit substantially from code tuning.
• Quicksort behaves well even with caching and virtual memory.
Merge Sort
Merge sort is based on divide-and-conquer technique. Merge sort method is a two phase process-
1. Dividing
2. Merging
Dividing Phase: During the dividing phase, each time the given list of elements is divided into two parts.
This division process continues until the list is small enough to divide.
Merging Phase: Merging is the process of combining two sorted lists, so that, the resultant list is also the
sorted one. Suppose A is a sorted list with n element and B is a sorted list with n2 elements. The operation
that combines the elements of A and B into a single sorted list C with n=n1 + n2, elements is called
merging.
Algorithm-(Divide algorithm)
Algorithm Divide (a, low, high)
{
// a is an array, low is the starting index and high is the end index of a
If( low < high) then
{
Mid: = (low + high) /2;
Divide( a, low, mid);
Divide( a, mid +1, high);
Merge(a, low, mid, high);
}
}
The merging algorithm is as follows-
Algorithm Merge( a, low, mid, high)
{
L:= low;
H:= high;
J:= mid +1;
K:= low;
While (low mid AND j high) do
{
If (a[low < a[j]) then
{
B[k] = a[low];
K:= k+1;
Low:= low+1;
}
Else
{
B[k]= a[j];
K: = k+1;
J: = j+1;
}
}
While (low mid) do
{
B[k]=a[low];
K: = k+1;
Low: =low + 1;
}
While (j high) do
{
B[k]=a[j];
K: = k+1;
j: =j + 1;
}
//copy elements of b to a
For i: = l to n do
{
A[i]: =b[i];
}
}
Ex: Let the list is: - 500, 345, 13, 256, 98, 1, 12, 3, 34, 45, 78, 92.
500 345 13 256 98 1 12 3 34 45 78 92
500 345 13 256 98 1 12 3 34 45 78 92
500 345 13 256 98 1 12 3 34 45 78 92
500 345 13 256 98 1 12 3 34 45 78 92
500 345 13 256 98 1 12 3 34 45 78 92
345 500 13 98 256 1 3 12 34 45 78 92
13 345 500 1 98 256 3 12 34 45 78 92
500 345 13 256 98 1 3 12 34 45 78 92
1 3 12 13 34 45 78 92 98 256 354 500 Sorted List
The merge sort algorithm works as follows-
Step 1: If the length of the list is 0 or 1, then it is already sorted, otherwise,
Step 2: Divide the unsorted list into two sub-lists of about half the size.
Step 3: Again sub-divide the sub-list into two parts. This process continues until each element in
the list becomes a single element.
Step 4: Apply merging to each sub-list and continue this process until we get one sorted list.
Efficiency of Merge List: Let ‘n’ be the size of the given list/ then the running time for merge sort is
given by the recurrence relation.
T(n) = { a
2T(n/2) + Cn
if n=1, a is a constant
if n>1, C is constant
Assume that ‘n’ is a power of 2 i.e. n=2k.
This can be rewritten as k=log2 n.
Let T(n) = 2T (n/2) +Cn 1
We can solve this equation by using successive substitution.
Replace n by n/2 in equation, 1 ,we get
T (n/2) = 2T(n/4) + Cn 2
2
Thus, T(n) = 2 2T (n/4) + Cn + Cn
2
= 4T (n/4) + 2Cn
= 4T 2 T (n/8) + Cn + 2Cn
4
...
...
...
= 2 k T(1) + KCn . .. k = log2 n
= a n + Cn log n
.
. . T (n) = O( n log n)
Worst case O(n log n)
Best case O(n)
Average case O(n log n)
Space Complexity О(n)