Divide and conquer

Divide and conquer

1. DIVIDE & CONQUER
ALGORITHMS
Shashikant V. Athawale
Assistant Professor ,Computer Engineering Department
AISSMS College of Engineering,
Kennedy Road, Pune , MS, India - 411001
1

2. DIVIDE & CONQUER
The most well known algorithm design strategy:
1.Divide the problem into two or more smaller
subproblems.
2.Conquer the subproblems by solving them
recursively.
3.Combine the solutions to the subproblems into
the solutions for the original problem.
2

3. THE DIVIDE AND CONQUER
ALGORITHM
Divide_Conquer(problem P)
{
if Small(P) return S(P);
else {

divide P into smaller instances P
1
, P
2
, …,
P
k
, k³1;

Apply Divide_Conquer to each of these
subproblems;

return Combine(Divide_Conque( P
1
),
Divide_Conque(P
2
),…, Divide_Conque(P
k
));
}
} 3

4. DIVIDE AND CONQUER EXAMPLES
Merge sort
Quick sort
Binary Search
4

5. MERGE SORT
The merge sort algorithm works from “the
bottom up”
start by solving the smallest pieces of the main
problem
keep combining their results into larger solutions
eventually the original problem will be solved
5

6. MERGE SORT
Sort into nondecreasing order
log
2
n passes are required.
time complexity: O(nlogn)
[25][57][48][37][12][92][86][33]
[25 57][37 48][12 92][33 86]
[25 37 48 57][12 33 86 92]
[12 25 33 37 48 57 86 92]
pass 1
pass 2
pass 3
6

7. QUICK SORT
Select a pivot whose value we are going to divide the
sublist. (e.g., p = A[l])
Rearrange the list so that it starts with the pivot
followed by a ≤ sublist (a sublist whose elements are
all smaller than or equal to the pivot) and a ≥ sublist
(a sublist whose elements are all greater than or equal
to the pivot ) (See algorithm Partition in section 4.2)
Exchange the pivot with the last element in the first
sublist(i.e., ≤ sublist) – the pivot is now in its final
position
Sort the two sublists recursively using quicksort.
p
A[i]≤p A[i] ≥ p
7

8. QUICK SORT
5 3 1 9 8 2 4 7
2 3 1 4 5 8 9 7
1 2 3 4 5 7 8 9
1 2 3 4 5 7 8 9
1 2 3 4 5 7 8 9
1 2 3 4 5 7 8 9
8

9. BINARY SEARCH
ALGORITHM
BinarySearch(A[0..n-1], K)
//Implements nonrecursive binary search
//Input: An array A[0..n-1] sorted in ascending order and
// a search key K
//Output: An index of the array’s element that is equal to K
// or –1 if there is no such element
l  0, r  n – 1
while l £ r do //l and r crosses over can’t find
K.
m ë(l + r) / 2û
if K = A[m] return m //the key is found
else
if K < A[m] r m – 1//the key is on the left half of the
array
elsel  m + 1// the key is on the right half of
the array
return -1
9

10. Thank You
10