Chapter Two.
Divide – and – conquer
1
Contents
Divide-and-conquer
Binary Search,
Merge Sort
Quick Sort
Selection Sort
2
Divide and Conquer
Divide and conquer is related to the strategy for solving a problem.
The divide-and-conquer methods are used, particularly, when the function to
compute has n inputs.
3
The general method
Let say we have problem P of size n:
The problem is sub divided into sub problems (p1, p2,…) and
each sub problems are solved individually, then combine the
solutions (s1, s2, ...) to get the solution for the whole problem
In divide and conquer, whatever the problem is sub problem will be same as that problem.
E.g. if the problem is sorting, then sub problems are also sorting.
So, when we use divide and conquer strategy for solving problems it is recursive process.
Always we should have mechanism to combine solutions of sub problems, otherwise we
cannot use divide and conquer.
4
The General Method
The following algorithm gives the control abstraction for divide-and-
conquer:
5
The General Method cont……
P is the problem having n inputs.
The boolean function “Small(P)” checks whether the input size is small enough. If
Small(P) is true (no more splitting) then the solution function S is returned.
Otherwise the problem is split into k smaller sub problems: P1, P2, P3, ………..,Pk .
Then these sub problems are solved by applying the algorithm DAndC recursively.
The function Combine assembles solutions of all these k sub problems.
6
The General Method cont……
The time complexity of a program is generally expressed as a recurrence relation.
g(n) if n small otherwise
T(n) = T(n1) + T(n2) +…….+ T(n k) + f(n)
Where
T(n) is the time for DAC,
g(n) is the time to compute a small sub problem,
f(n) is the time for splitting the problem and combining the solutions of the sub
problems.
Generally the time complexity of any divide-and-conquer algorithm is given by a
recurrence relation of the form
T(1) for n=1
T(n) = a T(n/b)+f(n) for n>1
Where: a and b are known constants. We assume that T(1) is known and that n is a power
of b (n = bk).
7
Pros and cons of DAC approach
8
Some Problems under Divide and Conquer
Analysis of Binary search
Analysis of Merge sort
Analysis of Quick sort
Analysis of Selection sort
9
Binary Search
10
Binary Search implementation….
11
cont...
12
cont...
13
cont...
example:
14
Recursion algorithm for binary search
1. Algorithm [Link](l,h,key) {
1. If (l==h){
2. If (A[l]==key)
1. Return l;
2. else return 0;}
3. else{
4. Mid=(l+h)/2;
5. If(key==A[mid])
1. Return mid;
6. If (key<A[mid])
1. Return [Link](l, mid-1, key);
2. Else
3. Return [Link](mid+1, h, key);
4. }}
15
Analysis of Binary Search
16
cont….
Time complexity of binary search
Cases Successful Unsuccessful
searches searches
Best: O(1) O(log n)
Average: O(log(n)) Θ(log n)
Worst: O(log n) Θ(log n)
Example: Apply the above binary search algorithm for finding 100 in the following
data items: -20, -10, 0, 8, 10, 24, 41, 55, 83, 102, 113, 126, 132, 143 and 152.
17
Merge Sort
18
cont…
19
Example
20
Recursive merge sort algorithm
21
Complexity Analysis of Merge Sort
22
cont...
23
cont...
24
cont...
25
cont...
26
cont...
Time complexity of merge sort is similar O(nlogn) in all three cases.
Cases
Best case O(nlogn)
Average case O(nlogn)
Worst Case O(nlogn)
Space complexity of merge sort: we need to build a temporary array to
merge the sorted arrays in case of merge sort. Hence, the auxiliary space
requirement is O(n).
27
Pros and Cons of Merge Sort
Pros:
Suitable for large size data list
Linked list (to easily merge two sorted lists without creating third list)
Supports external sorting
Cons:
It is not inplace sort (external space needed; in case of array)
No small problem (and it is slower for small size list)
Recursive (all recursive algorithms use stack)
28
QUICK SORT
Choosing the pivot element:
Pivot element can be random: selecting random element from the given
array.
Pivot can be either the first or the last element
Pivot can be the middle element
29
cont...
30
Quick sort Analysis
31
cont...
32
cont...
33
cont...
34
cont...
35
cont...
36
cont...
37
cont...
38
Selection sort
We are given n elements a[1 : n] and are required to determine the kth-smallest element of the given
unsorted array a[1 : n].
If the array is partitioned at position j, then the partitioning element v is a[j].
Then j-1 elements are less than or equal to a[j] and n-j elements are greater than or equal to a[j]. if k < j,
then the kth –smallest element is in a[1 : j -1].
If k =j, then a[j] is the smallest element, and if k > j then the kth –smallest element is the (k-j)th-smallest
element in a[j+1 : n].
The selection sort algorithm, places the kth-smallest element into position a[k] and partitions the remaining
elements so that a[i] ≤ a[k], 1 ≤ i < k, and a[i] ≥ a[k] for 1 < i ≤ n..
39
41