Chapter 2
Chapter 2
Chapter 2
Chapter 2
Objectives
Describe the divide-and-conquer approach to
solving problems
Apply the divide-and-conquer approach to solve a
problem
Determine complexity analysis of divide and
conquer algorithms
3
2.1 Binary Search
We present a recursive . The steps are
If x equals the middle item, quit. Otherwise:
1. Divide the array into two subarrays about half .
a) If x is smaller than the middle item, choose the left subarray.
b) If x is larger than the middle item, choose the right subarray.
2. Conquer (solve) the subarray : whether x is in that subarray.
Unless the subarray is sufficiently small, use recursion to do this.
3. Obtain the solution to the array from the solution to the subarray.
4
Binary search
Example:
10 12 13 14 18 20 25 27 30 35 40 45 47
Algorithm 2.1 5
Example B1 in Appendix B:
W(n) = lg n + 1
n not a power of 2 (exercise)
W(n) = lg n +1 θ(lg n)
11
t1 =1
t2 =t1 +1 =2
t3 =3
…
tn =n
Proof by induction
13
2.2 Mergesort
Sort an array S of size n ( let n be a power of 2)
Divide S into 2 sub-arrays of size n/2
Conquer (solve) recursively sort each sub-array until
array is sufficiently small (size 1)
Combine merge the solutions to the sub-arrays into a
single sorted array
14
Figure 2.2
15
Algorithm 2.2 - Mergesort
Problem: Sort n keys in nondecreasing sequence.
Inputs: +ve int n, array of keys S indexed from 1 to n.
Outputs: the sorted array S in nondec. order.
void mergesort (int n, keytype S [ ])
{
if (n > 1) {
const int h = n /2 ; m = n – h;
keytype U [1 . . h] , V [1 . . m] ,
copy S [ 1 ] through S [ h ] to U [1 ] through U [ h ] ;
copy S [ h + 1 ] through S [ n ] to V [1 ] through V [ m ] ;
mergesort ( h, U);
mergesort ( m, V);
merge ( h, m, U, V, S);
}
}
16
n not a power of 2
W(n)=W(n/2) + W(n/2) + n-1
From Theorem B4: (W(n) eventually nondecreasing,
n lg n is smooth )
W(n) Θ(n lg n)
23
EXERCISE
Solve
T(n) = 2T(n/2) + n, T(1)=1
24
2.4 Quicksort
Array recursively divided into two partitions and
recursively sorted
Division based on a pivot
pivot divides the array into two sub-arrays
All items < pivot placed in sub-array before pivot
All items >= pivot placed in sub-array after pivot
30
Example 2.3
Suppose the array contains these numbers in
sequence:
Pivot item
15 22 13 27 12 10 20 25
Pivot item
13 12 10 15 22 27 20 25
Sort the subarrays:
10 12 13 15 20 22 25 27
31
15 22 13 27 12 10 20 25
Basic operation
Comparison of S[i] with pivot item
Input size n
36
Worst Case
Use induction to show it is the worst case
W(n)<= n(n-1)/2
40
42
43