Given problem P and input I. Let us denote this problem instance by (P,I). If size(I) is small, e.g. size(I) = 1, the instance probably is easy to solve. If size(I) = n is large, a divide-and-conquer approach takes the following steps:
|
Since the divide-and-conquer method starts with the largest problem (the top level) and proceeds to solve smaller and smaller subproblems (going down the recursion tree), it is a top-down approach.
In order that divide-and-conquer approach is possible, we must have:
|
|
The recurrence
|
|
To sort an input of n different keys, a comparison sorting algorithm does a series of comparisons to determine the correct order of the keys. Such an algorithm can be described by its decision tree.
The decision tree of a sorting algorithm for n different keys is a
regular (or full) binary tree in which each internal node
represents a comparison of two keys Ki and Kj.
The left subtree corresponds to the case Ki < Kj, and the right subtree
corresponds to Ki > Kj. An external node contains a permutation
p of {1,2,¼,n} that represents the order
|
Since all permutations of {1,2,¼,n} are possible, and there are n! of them. It follows that there are at least n! external nodes in this decision tree. We know that a regular binary tree with m external nodes must have at least élgm ù+ 1 levels. On a path from the root to an external node, each internal node represents a comparison of keys performed for this particular input. Hence in the worst case, the algorithm has to perform as many comparisons as the number of levels in the tree minus one, which is élg(n!) ù » nlgn.
Any comparison sorting algorithm on n keys must perform approximately n lgn comparisons in the worst case.
Can we find a sorting algorithm that has this best worst-case performance? It turns out that a straightforward application of the divide-and-conquer method on a sorting problem can almost achieve this. The resulting algorithm is mergesort. The idea is illustrated in Figure 3.2.
[Mergesort] Sort the array a[low..high].
Suppose Step (3) above is done by a procedure merge, then the above can be implemented as in Figure 3.3.
mergesort (int a[], int low, int high)
/* Sort array a[low..high] */
{
int mid = (low + high) / 2;
if (low < high) {
mergesort(a, low, mid);
mergesort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
merge (int a[], int low, int mid, int high)
/* Merge sorted subarrays a[low..mid] and a[mid+1..high]
* into sorted array a[low..high] */
{
int b[MAX_SIZE], i = low, j = mid + 1, k = 0;
/* Merge into b */
while (i <= mid && j <= high)
b[k++] = (a[i] < a[j]) ? a[i++] : a[j++];
/* Copy rest of first half */
while (i <= mid)
b[k++] = a[i++];
/* Copy rest of second half */
while (j <= high)
b[k++] = a[j++];
/* Copy back into a */
for (k = 0; k <= high - low; k++)
a[low + k] = b[k];
}
It is obvious that merge runs in Q(n) time. Let T(n) be
the running time of mergesort. We have
|
Let us take key comparison as the basic operation, and let
W(n) be the number of basic operations performed by mergesort
in the worst case. It is obvious that merge does n-1 comparisons
with an input of size n in the worst case. Therefore we have
|
|
|
Mergesort is asymptotically optimal. Since merge requires an additional array as big as the input, mergesort does not sort in place. To implement function calls, the computer has to do a lot of housekeeping chores, e.g. pushing local variables, parameters, and return addresses onto the recursion stack, and save the contents of all registers. To mimic the returning from a recursive call, values of the local variables and parameters of the previous call must be restored. Contents of the registers of the previous call must also be restored. Then control can be branched back to the return address found on the top of the recursion stack. When the subarrays in mergesort are short, this overhead for recursion dominates the running time. In this case, nonrecursive algorithms run faster. Hence, the overall performance of mergesort can be improved if it switches to a nonrecursive sorting algorithm for short subarrays, say of size less than 20. Figure 3.4 shows such an improved version.
/* M is a constant determined by experiments */
mergesort (int a[], int low, int high)
{
int mid = (low + high) / 2;
if (high - low >= M) {
mergesort(a, low, mid);
mergesort(a, mid + 1, high);
merge(a, low, mid, high);
}
else /* switch to a nonrecursive sort */
other_sort(a + low, high - low + 1);
}
Quicksort is another fast sorting algorithm based on the divide-and-conquer paradigm. It has many different versions. The following version is chosen because its analysis is simple.
[Quicksort] Sort the array a[low..high].
The idea of quicksort is illustrated in Figure 3.5.
In pseudocode, quicksort can be described as:
quicksort (a, low, high )
// Sort a[low..high ].
{
if (low < high ) then {
c ¬ partition (a, low, high );
quicksort (a, low, c-1);
quicksort (a, c+1, high );
}
}
[Partition]
Rearrange array a[low .. high] and returns index c such that
|
Figure 3.6 shows how partition works. An implementation of partition and quicksort is shown in figure 3.7.
int partition (int a, int low, int high)
/* return c such that elements in a[low..c-1] <=
* a[c] <= elements in a[c+1..high] */
{
int t, x = a[low];
i = low, j = high + 1;
while (1) {
/* move i */
do { i++; } while (i <= high && a[i] < x);
/* move j */
do { j--; } while (i <= j && a[j] > x);
if (i < j) { /* swap a[i] and a[j] */
t = a[i]; a[i] = a[j]; a[j] = t;
}
else { /* Swap a[low] and a[j] */
a[low] = a[j]; a[j] = x;
return (j);
}
}
}
quicksort (int a, int low, int high)
/* Sort array a[low..high] */
{
int c;
if (low < high) {
c = partition(a, low, high);
quicksort(a, low, c - 1);
quicksort(a, c + 1, high);
}
}
For simplicity, we assume that there are no equal keys in the array. The result we will obtain is also valid with equal keys, but the derivation is more intricate.
We choose key comparison as the basic operation.
Notice procedure quicksort is only a driver to make calls to
partition where all basic operations are performed.
We observe that in partition, one comparison is done after each index is
advanced. The two indices will cross eventually. Hence n+1 comparisons
are required where n is the number of entries in the subarray.
In general, let C(n) be the number of basic operations performed with
input size n. We have
|
|
|
|
|
|
| (3.1) |
| (3.2) |
|
|
|
There are many ways of choosing the pivot:
/* M is a constant determined by experiments */
quicksort (int a[], int low, int high)
{
int c, p;
if (high - low >= M) {
p = choose(a, low, high);
swap a[low] and a[p];
c = partition(a, low, high);
quicksort(a, low, c - 1);
quicksort(a, c + 1, high);
}
else /* switch to a nonrecursive sort */
other_sort(a + low, high - low + 1);
}
Even though partition splits the input in place. Quicksort is not an in-place sorting algorithm, since the depth of the recursion stack depends on the input size n. In the worst case, the depth could be as bad as Q(n). However, if we carefully juggle the order of the two recursive calls, the depth can be kept under lgn. Figure 3.9 shows how this can be done.
/* M is a consant determined by experiments */
quicksort (int a[], int low, int high)
{
int c, p;
if (high - low >= M) {
p = choose(a, low, high);
swap a[low] and a[p];
c = partition(a, low, high);
if (c - low < high - c) {
quicksort(a, low, c - 1);
quicksort(a, c + 1, high);
}
else {
quicksort(a, c + 1, high);
quicksort(a, low, c - 1);
}
}
else
other_sort(a + low, high - low + 1);
}
There are various reasons for removing recursions:
nonrecursive_quicksort (int a[], int n)
/* Sort array a of size n */
{
int p, low = 0, high = n - 1;
STACK S = create_stack();
while (1) {
while (high - low >= M) {
p = choose(a, low, high);
swap a[p] and a[low];
c = partition(a, low, high);
push(S, c + 1); push(S, high);
high = c - 1;
}
other_sort(a + low, high - low + 1);
if (!stack_empty(S)) {
high = pop(S); low = pop(S);
}
else
return;
}
}
try (int n)
int n;
{
if (n < 2)
dosomething(); /* runs in constant time */
else
{
try(n - 1);
try(n - 2);
}
}
Design a divide-and-conquer algorithm for this problem that runs in Q(n lgn) time.
[Hint: At the first stage, the maximizing segment may
|
|