Divide and Conquer is a recursive algorithm, applied to many problems. Name a few? Sorting, searching and closest pair.
The general algorithm:
If the problem is too big then recursively divide the problem into smaller parts until the problem size is small enough to solve. During the recursive callbacks merge the solutions from the smaller problems.
The recursive divide can reduce the problem size so that it trivial to solve, for example a sorting a single element array, but in practice the base case is at a size that a brute force technique becomes efficient.
Work (the computation) must be done either during the division, the merge, or both, as we'll see in merge and quick sort.
Recursive algorithm will have a recursive relation for the time cost:
T(n) = aT(n/b) + f(n).
The quantity b is the number of splits, for a binary split (for example in merge sort) b = 2. Generally a ≥ b.
The smoothness rule can help solve the recursive relation but the recursive relation is inhomogeneous because of f(n). Inhomogeneous recursive relations are difficult to solve, generally, requiring guessing the solution. Fortunately someone has already solved this recursive relation.
Master Theorem
If f(n) ε Θ(nd) with d ≥ 0 in the recursive relation
T(n) = aT(n/b) + f(n)
then
T(n) ε Θ(nd) if a < bd
T(n) ε Θ(nd lg n) if a = bd
T(n) ε Θ(n logb a) if a > bd
Analogous results hold for O and Ω.
The array is divided in half and during the merge the sorted array halves are linearly merged.
Algorithm Mergesort(A[0...n-1])
if n >1 then
copy A[0...floor(n/2)-1) to B[0...floor(n/2)-1]
copy A[ceiling(n/2)...n-1] to C[0...ceiling(n/2)-1]
Mergesort(B[0...floor(n/2)-1])
Mergesort(C[0...ceiling(n/2)-1])
Merge(B, C, A)
Merging the two sequences back into the original array assumes that the two arrays are sorted. Three pointers keep track of index in the arrays and the array element from each array is compared sequentially and loaded into Array.
Algorithm Merge(B[0...p-1], C[0...q-1], A[0...p+q-1])
i ← 0; j ← 0; k ← 0
while i < p and j < q do
if B[i] ≤ C[j] then A[k] ← B[i]; i++
else A[k] ← C[j]; j++
k++
if i = p then copy C[j...q-1] to A[k...p+q-1]
else copy B[i...p-1] to A[k...p+q-1]
Cost of mergesort, assuming n is a power of 2
C(n) = 2C(n/2) + Cmerge(n)
IC C(1) = 0
What is the cost of the merge? Counting comparisons the worst case is that the less element alternates between the arrays, then n-1 comparisons is made.
Cworst(n) = 2Cworst(n/2) + n -1, IC Cworst(1) = 0
Using Master's theorem, d = 1, b = 2, so bd = 2 = a, so
Cworst(n) ε Θ(n lg n)
Is the sort in-place? No. It is possible to make mergesort in place but difficult and expensive. The array is divided into three parts using pointers (instead of two parts), and the third part is used a temporary storage during the merge (many swaps, in and out of the temporary storage). The swapping is too expensive for this to be an efficient algorithm.
Quick sort does the work during the divide, by dividing the array into three parts, small, medium, and large values. The merge is automatic.
Algorithm Quicksort(A[l...r])
if l < r then
s ← Partition(A[l...r]) // s is the split position
Quicksort(A[l...s-1])
Quicksort(A[s+1...r])
Note that the merge is automatic.
Partitioning is done using a pivot, which is an array element. Array elements are compared sequentially with the pivot and used to assign the array element to small or large part. If we can make Partition in-place then quick sort will be in-place.
Algorithm Partition(A[l...r])
p ← A[l] // the pivot
i ← l; j ← r + 1
repeat
repeat i++ until A[i] ≥ p
repeat j-- until A[j] ≤ p
swap(A[i], A[j])
until i ≥ j
swap(A[i], A[j]) // undo the last incorrect swap
swap(A[l], A[j]) // puts the pivot in the proper position
What is the cost of Partition? Always linear in r-l.
The choice of pivot affects the cost of quick sort. We'll first calculate best case, where the pivot divides the array evenly.
Cbest(n) = 2Cbest(n/2) + n
IC Cbest(1) = 0
Using Masters Theorem, d = 1, b = 2, so bd = 2 = a, so
Cbest(n) ε Θ(n lg n)
In the worst case the pivot is always the smallest or largest element, so the array size is decreased by only one.
Cworst(n) = (n+1) + n + ... + 3 = (n+1)(n+2)/2 - 3 ε Θ(n2)
We need to determine the average case cost. Assume that the pivot is uniformly distributed. So s can have values between 0 and n-1 with probability 1/n. Note that s is the size of the smaller part. The recurrence relation for the average cost is
Cavg(n) = (1/n)∑s=0n-1[(n+1) + Cavg(s) + Cavg(n-1-s)]
IC Cavg(0) = 0, Cavg(1) = 0
Solution left for an exercise
Cavg(n) ≈ 2n ln n ≈ 1.38n lg n
Quick sort only makes 38% more comparison than the best case. The average case runs faster than merge sort. It is in-place but not stable.
Quick sort worst case cost can be improved by the choice of pivot. Do you have any better ideas for choosing the pivot?
Is Quick sort really in-place?
What is put on the stack? Only the pointers.
How many pointers will be put on the stack? The number of splits, so on average Θ(lg n), but worst case could be Θ(n). When?