Design and Analysis of Algorithms
Chapter II. 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.
The divide-and-conquer strategy splits the problem into k sub problems for
1≤ k ≤ n. Each of these k sub problems is solved individually.
Afterwards a suitable method is applied to assemble all these k sub solutions
to obtain a solution of the original problem. All the above said sub problems
must be of the same type as the original problem.
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: P 1, 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 DAndC,
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
Some Problems under Divide and
Conquer
Binary search
Merge sort
Quick sort
Selection sort
8
Binary Search
This is a standard search technique that is used very frequently when
necessary. a[i], for 1 ≤ i ≤ n, is a sorted array of size n, say in the non-
decreasing order, x is a given search element.
The problem is to determine whether x is present in the list a[i] or not. If
present we determine a value j such that a[j]= x. If x is not present in the list,
then conveniently, zero is assigned to j.
Let P=(n, a , …., a , x) denote an arbitrary instance of this problem. We use
i j
divide-and- conquer technique to solve this problem.
S(P) will receive the value i if x = a[i], otherwise zero. Then g(1) = Θ(1).
P is split into smaller problems if P has more than one element.
9
Binary Search cont….
Compare x with a[q], for i ≤ q ≤ l. Then the following three possibilities arise:
1. x = a[q], in which case the search is successful and the problem is solved.
2. x < a[q]. Then a[i] ≤ x ≤ a[q-1], that is, x has to be searched only in the sub list a[i] a[i+1],…, a[q-1]. As
such P reduces to (q-i, a[i], …, a[q-1], x ).
3. x > a[q]. In this case a[q+1] ≤ x ≤ l. x has to be searched in the sub list a[q+1] , , …, a[l]. P now
reduces to ( l-q, a[q+1], …, a[l], x ).
Division of P into smaller sub problems take only Θ(1) time. We apply the divide-and conquer method
again and again to solve the instance if necessary.
This divide-and-conquer method is called a binary search method if q is chosen every time such that a q is
the middle element of the list, that is q = |_ _(n + 1)/2__|.
10
Example
In this example we start by taking low (l)=1 and high(h)=15, and find the mid by
adding l and h then divide by two. The compare the key 42 with the value at mid,
if not the same continue the process.
We will get the key 42 after just four comparison.
11
Recursion algorithm for binary search
a[1:n] is an array of n elements in non- decreasing order. This algorithm determines whether x is
present in a[ ] and if so returns j such that x = a[ j ], else returns 0
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. }
2.
12
}
Binary Search 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.
13
Merge Sort
One example of divide-and-conquer, we investigate a sorting algorithm that has the nice
property that in the worst case its complexity is 0(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[l],... ,a[n], the general idea is to imagine them split into
two sets a[l],... ,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.
14
Merge Sort cont……..
15
Merge Sort cont……
The time complexity of merge sort is proportional to n, then the computing time for merge sort is
described by the recurrence relation:
a, n 1, a....cons tan t
T ( n)
2T (n / 2) cn, n 1, c....cons tan t
16
Merge Sort..
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).
17
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)
18
QUICK SORT
Compared to the Merge Sort algorithm in the Quick Sort algorithm the merging part is avoided by
rearranging the elements in a[1:n] such that a[i]<=a[j], for all i, 1 <= i <= m and for all j, m+1 <= j<= n, for
some m such that 1 <= m <= n.
Thereby the two arrays a[1:m] and a[m+1:n] can be independently sorted.
The regrouping of the elements of the given array a[ ] is done as follows. We select one element, say t =
a[s]. Now rearrange the other elements, so that all the elements of a[1 : n ] to the left of t are less than or
equal to t and all elements appearing to the right of t are greater than or equal to t.
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
19
Quick sort Analysis
Best Case of Quick Sort: Suppose the partition is done in the middle of the list, then the
height of the tree will be almost logn, and it is n elements logn times. Therefore, in best
case the time complexity of quick sort is O(nlogn).
This happens when the pivot element is the median.
In the average case also its time complexity is O(nlogn).
Worst case of quick sort: It happens when, the list is sorted either in ascending or
descending order, and the pivot element is either the first or the last element.
Worst case time complexity of quick sort is O( n2).
Space complexity of quick sort: In best case, it uses stack but no extra spaces, then the
height of the tree will be logn, hence, sp= O(logn).
In worst case, height of the tree = n, hence, space complexity (sp) = O(n)
20
Selection sort
We are given n elements a[1 : n] and are required to determine the k th-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 k th –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..
21
End of
Lecture II.