'
Divide and Conquer Divide and Conquer
Algorithm D-and-C(n: input size) if n n0 /* small size problem*/ Solve problem without futher sub-division; else Divide into m sub-problems; Conquer the sub-problems by solving them independently and recursively; /* D-and-C(n/k) */ Combine the solutions;
Advantage: straightforward and running times are often easily determined.
& CS404/504 %
Computer Science Design and Analysis of Algorithms: Lecture 8 1
'
Complexity of Divide and Conquer Complexity of Divide and Conquer
Suppose we divide the original problem into m sub-problems, each with a problem size n/k, and let D(n) be the time needed to do the dividing, and C(n) the time needed to do the combining. Then we got a very general formula to compute T(n):
T (n) =
(1) , for small sizes mT (n/k) + D(n) + C(n) , otherwise
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 2
'
Merge Sort Merge Sort
MERGE-SORT(A, p, r) {
if (p == r) /* small size */ return; else q = (p + r)/2; Merge-Sort(A, p, q); Merge-Sort(A, q+1, r); Merge(A, p, q, r);
}
To sort the whole array, Merge-Sort(A, 1, n) is called.
& CS404/504 %
Computer Science Design and Analysis of Algorithms: Lecture 8 3
'
Complexity of Merge Sort Complexity of Merge Sort
Divide: The divide step only computes the middle, takes only constant time. D(n) = (1). Conquer: Recursively sort 2 subarrays. C(n) = 2T (n/2). Combine: Merge two n/2-element subarrays, in linear time (n). Overall: T (n) = (1) if n = 1 (or smallsize ) 2T (n/2) + (1) + (n) if n > 1 (or smallsize)
Based on Master Method-Case 2, T (n) = (nlgn) for best, worst and average cases.
& CS404/504 %
Computer Science Design and Analysis of Algorithms: Lecture 8 4
'
Quick Sort Quick Sort
Basic Steps: - Divide: split the array A[p..r] into two nonempty subarrays A[p..q] and A[q+1..r] such that each element of A[p..q] is less than or equal to each element of A[q+1..r]. - Conquer: Sort the two subarrays by calling quicksort recursively. - Combine: Trivial.
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 5
'
Quick Sort algorithm Quick Sort algorithm
QUICK-SORT(A, p, r)
if (p r) /* small size problem*/ return; else q := Partition(A, p, r); Quick-Sort(A, p, q-1); Quick-Sort(A, q+1, r);
To sort the whole array, Quick-Sort(A, 1, n) is called.
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 6
'
Partition Partition
- There are several dierent strategies that can be used by Partition. - One possible strategy: as we scan from left to right, we move the left bound to the right when the element is less than the pivot, otherwise we swap it with the rightmost unexplored element and move the right bound one step closer to the left. - Note: although the strategy used in CLRS textbook takes dierent form, it is essentially the same as the above.
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 7
'
Illustration of Partition Illustration of Partition
Pivot about the last element: 10. We keep 3 sections: the elements 10, elements > 10 and the unexplored elements. | 17 12 6 19 23 8 5 10 | 5 12 6 19 23 8 | 17 10 5 | 12 6 19 23 8 | 17 10 5 | 8 6 19 23 | 12 17 10 5 8 | 6 19 23 | 12 17 10 5 8 6 | 19 23 | 12 17 10 5 8 6 | 23 | 19 12 17 10 5 8 6 ||23 19 12 17 10 5 8 6 |10| 19 12 17 23 Complexity: consists of n 1 comparisons and at most n swaps. So T(Partition) = (n).
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 8
'
Complexity of Quick Sort Complexity of Quick Sort
Divide: The divide step Partition takes linear time (n). Conquer: Recursively sort 2 subarrays, one with size q 1, the other is n q. C(n) = T (q 1) + T (n q). Combine: Basically no Combine step. T (n) = T (q 1) + T (n q) + (n).
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 9
'
Worst Case Worst Case
Partition always separates the array into one 0length and one (n 1)length subarrays. If we pick the last element as the pivot, this situation happens when the input is sorted ascendingly or descendingly.
T (n) = T (n 1) + (n) T (n) = (n2)
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 10
'
Best Case Best Case
T (n) = 2T (n/2) + (n) T (n) = (nlgn)
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 11
'
A case between the best and worst case A case between the best and worst case
T (n) = T (9n/10) + T (n/10) + (n) = (nlgn)
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 12
'
Average-Case Analysis of Quicksort Average-Case Analysis of Quicksort
To do a precise average-case analysis of quicksort, we formulate a recurrence given the exact expected time T (n): T (n) = 1 (T (q 1) + T (n q)) + n 1 n q=1
n
Each possible pivot p is selected with equal probability. The number of comparisons needed to do the partition is n 1. 1 (T (q 1) + T (n q)) + n 1 n q=1
n n
T (n) =
2 T (n) = T (q 1) + n 1 n q=1
n
nT (n) = 2
q=1
& CS404/504
T (q 1) + n(n 1)
multiply by n
%
Computer Science Design and Analysis of Algorithms: Lecture 8 13
'
Contd Contd
n1
(n 1)T (n 1) = 2
q=1
T (q 1) + (n 1)(n 2)
apply to n 1
nT (n) (n 1)T (n 1) = 2T (n 1) + 2(n 1) rearranging the terms give us:
T (n) n+1
= = < < < <
T (n1) 2(n1) + n(n+1) n T (n1) 2 2 + n+1 n(n+1) n T (n1) 2 + n+1 n T (n2) 2 2 + n + n+1 n1 T (n3) 2 2 2 + n1 + n + n+1 n2 T (1) 2 2 2 + 3 + 2 + ... + n + n+1 2 4 n+1 1 k=1 k
But the harmonic series
= ln (n + 1) + O(1)
so T (n) < (n + 1)(2 ln (n + 1) + O(1)) = O(nlgn)
& CS404/504
Computer Science Design and Analysis of Algorithms: Lecture 8 14
