CHAPTER 5 Divide and Conquer
Introduction: Divide and Conquer Algorithms
The divide and conquer approach divides a problem into several smaller sub problems.
These sub problems are solved by some means.
The solutions of these sub problems are then combined to become a solution of the original problem. Very often each sub problem is also solved by the divide and conquer approach. Well-known divide and conquer algorithms include binary search, merge sort, and recurrence relationships
Ex: The Fibonacci numbers
Fib (5)
Fib (4)
Fib (3)
Fib (3)
Fib (2)
Fib (2)
Fib (1)
Fib (2)
Fib (1)
Ex: The example of factorial l
Ex: The example of
xy
Factorial (5)
35
3 *
Factorial (4)
34 33 32 31
Factorial (3)
Factorial (2)
Factorial (1)
Binary Search on 16 sorted elements
Search A[0] to A[7]
Search A[8] to A[15]
Search A[0] to A[3]
Search A[4] to A[7]
Search A[8] to A[11]
Search A[12] to A[15]
Search A[0] to A[1] Search A[2] to A[3]
Search A[4] to A[5] Search A[6] to A[7]
Search A[8] to A[9] Search A[10] to A[11]
Search A[12] to A[13] Search A[14] to A[5]
T(n) = 5 T(n) = 18 T( n/2 ) T(n) = 20+T( n/2 )
for n = 0 for n>0 and n is even for n> 0 and n is odd
Suppose n = 2k for some k>0. Obviously 2k is an even number, we get
T(2k) = 18 + T(2k-1) = 18 + (18 + T(2k-2)) = 18 + 18 + (18 + T(2k-3)) = .. = .. = 18k + T(2k-k) = 18k + T(20) = 18k + T(1)
Since T(1) is add number, the running time of T(1) is: T(1) = 20 + T(0) = 20 + 5 = 25 Therefore, T(2k) = 18k + 25
If n = 2k, then log n = log2k indicating that k = log n
Therefore,
T(n) = 18log n + 25
T(2k) = 18 + T(2k-1) T(2k) = 18 + (18 + T(2k-2) T(2k) = 18 + 18 + 18 + T(2k-3)
T(2k) = 18 + 18 + 18 + 18 + T(2k-4)
T(2k) = 18 + 18 + 18 + 18 + T(2k-4) + .+ 18 + T(2k-k) T(2k) = 18n + T(20) = = 18n + T(1) = 18k + 25 18logn + 25
Recursive Binary Search
- A little while ago, we saw how to search through a sorted array for a key using binary search - assume array sorted in increasing order
- This is an algorithm which is naturally stated recursively - First, recall the iterative solution
int binsearch( const vector< int>& A, int key)
{
int mid; // the middle point of the array int first= 0; // start of section in array int last= A.size()- 1; // end of section bool found = false; // assume not found to start while (first <= last && !found) { mid = (first+ last)/ 2; // roughly the middle if (A[ mid] == key) // found it - stop the loop found = true; else if (A[ mid] < key) // key is in the top half first = mid+ 1; else last = mid -1; // key must be in bottom half } // end while loop if (found) return mid; else return -1; // indicating that the key was not found }
Recursive Binary Search
- What's really happening in here? bisect the current range first... last at mid if A[mid] == key we are done if A[ mid] < key then key is in upper half of region first... last - continue by searching upper half mid+1... last if key < A[mid] then key is in lower half of array if it is in array at all - continue by searching lower half first...mid- 1
Recursive Binary Search - This is a recursive description
algorithm defined in terms of itself - Base Case: - if first > last we are finished - key is not found - otherwise, compute mid and compare A[mid] to key
- recursively search lower or upper half accordingly - return result of search
Recursive Binary Search
int binsearch (const vector< int>& A, int key int first, int last) { if (first> last) return -1; // key not found (null vector) else { int mid = (first+ last)/ 2; // define mid- point if (A[mid] == key) return mid; // found it if (A[mid] < key) // search upper half of region return binsearch( A, key, mid+1, last); else // search lower half of region return binsearch( A, key, first, mid-1); } }
Recursive Binary Search
- Consider the sorted array index: 0 1 2 3 4 5 6 7 value: 2 3 5 7 11 13 14 17
Start by calling binsearch( A, 11, 0, 7) - mid = 3 and A[3] < 11 // key in A[ 4]... A[ 7] call binsearch( A, 11,4,7) - mid = 5 and A[5] > 11 // key in A[ 4].. A[ 4] call binsearch( A, 11, 4, 4) - mid = 4 and A[4]==11 - Found it
Mergesort
- Sometimes a recursive solution is in fact the fastest solution - An important example of this is mergesort one of the fastest known "comparison based" sorting algorithms also extremely fast in practice
Mergesort
- Main idea break the array into two unsorted arrays of equal size sort each side recursively
merge the two sorted halves into a single sorted array
Mergesort
- For example, on array A = { 5, 9, 3, 13, 2, 6, 4, 1, 3, 7 } left = { 5, 9, 3, 13, 2 } right = { 6, 4, 1, 3, 7 } Recursively sort left to {2, 3, 5, 9, 13} Recursively sort right to {1, 3, 4, 6, 7} Merge the two sorted arrays into a single sorted array: { 1, 2, 3, 3, 4, 5, 6, 7, 9, 13 }
Mergesort: merging
- Aside from the recursion, the only operation which needs to be accomplished is to merge two sorted lists
- Idea: maintain a "pointer" into each sorted array at each step, append the smallest element pointed to onto the final array
Mergesort: merging
Step 1:
sort_ left = { 2 , 3, 5, 9, 13 } sorted_ right = { 1 , 3, 4, 6, 7 } sorted_ array = {}
Step 2:
sort_ left = { 2 , 3, 5, 9, 13 } sorted_ right = { 1, 3 , 4, 6, 7 } sorted_ array = { 1 }
Step 3: sort_ left = { 2, 3 , 5, 9, 13 } sorted_ right = { 1, 3 , 4, 6, 7 } sorted_ array = { 1, 2 }
Step 4: sort_ left = { 2, 3, 5 , 9, 13 } sorted_ right = { 1, 3 , 4, 6, 7 } sorted_ array = { 1, 2, 3 }
Step 5: sort_ left = { 2, 3, 5 , 9, 13 } sorted_ right = { 1, 3, 4 , 6, 7 } sorted_ array = { 1, 2, 3, 3 }
Step 6: sort_ left = { 2, 3, 5 , 9, 13 } sorted_ right = { 1, 3, 4, 6 , 7 } sorted_ array = { 1, 2, 3, 3, 4 }
Step 7: sort_ left = { 2, 3, 5, 9 , 13 } sorted_ right = { 1, 3, 4, 6 , 7 } sorted_ array = { 1, 2, 3, 3, 4, 5 }
Step 8: sort_ left = { 2, 3, 5, 9 , 13 } sorted_ right = { 1, 3, 4, 6, 7 } sorted_ array = { 1, 2, 3, 3, 4, 5, 6 }
Step 9: sort_ left = { 2, 3, 5, 9 , 13 } sorted_ right = { 1, 3, 4, 6, 7 } sorted_ array = { 1, 2, 3, 3, 4, 5, 6, 7 }
Step 10:
sort_ left = { 2, 3, 5, 9, 13 } sorted_ right = { 1, 3, 4, 6, 7 } sorted_ array = { 1, 2, 3, 3, 4, 5, 6, 7, 9 }
Step 11: sort_ left = { 2, 3, 5, 9, 13 } sorted_ right = { 1, 3, 4, 6, 7 } sorted_ array = { 1, 2, 3, 3, 4, 5, 6, 7, 9, 13 }
Mergesort: merging
vector< int> merge( const vector< int>& L, const vector< int>& R) { int Lptr= 0, Rptr= 0; vector< int> A; while (Lptr< L.size() || Rptr< R.size()) { if ((Lptr< L.size()) && ((Rptr>= R.size() || L[Lptr]<= R[Rptr]))) { A.push_back( L[Lptr]); Lptr++; } else { A.push_back(R[Rptr]); Rptr++; } } return A; }
Mergesort
- The
recursive mergesort routine itself is very simple
vector<int> mergesort(const vector<int>& A) { vector< int> left, right; if (A.size() <= 1) return A; for (int i= 0; i< A.size()/ 2; i++) left.push_back(A[ i]); for (i=A.size()/ 2; i< A.size(); i++) right.push_back(A[ i]); return merge(mergesort( left), mergesort( right)); }
- Again, follow the recursion
- We split the array into two
- And each half into two recursively
- And so on - eventually it gets split into N lists of a single element each
- For each split at the end, a pair of elements is merged
- Then we merge the pairs, and then the quartets
- And so on until one merge of two large lists at the end
- This is a by far faster than some other sorts like bubble sort or insertion sort algorithm
