CHAPTER 7
Sorting
7.1
7.3 The inversion that existed between a[i] and a[i + k] is removed. This shows at least one inversion is removed.
7.4
7.5 (a) (N2). The 2-sort removes at most only three inversions at a time; hence the algorithm is (N2). The 2-
7.7 See reference [12].
7.8 Use the input specified in the hint. If the number of inversions is shown to be (N2), then the bound follows,
7.10 (a) No, because it is still possible for consecutive increments to share a common factor. An example is the
7.11 The input is read in as
142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102
The result of the heapify is
879 is removed from the heap and placed at the end. We’ll place it in italics to signal that it is not part of the
heap. 102 is placed in the hole and bubbled down, obtaining
811, 543, 572, 434, 453, 123, 142, 65, 111, 242, 102, 879
Continuing the process, we obtain
572, 543, 142, 434, 453, 123, 102, 65, 111, 242, 811, 879
142, 111, 123, 102, 65, 242, 434, 453, 543, 572, 811, 879
123, 111, 65, 102, 142, 242, 434, 453, 543, 572, 811, 879
7.13 Heapsort uses at least (roughly) N log N comparisons on any input, so there are no particularly
7.14 If the root is stored in position low, then the left child of node i is stored at position 2i + 1 − low.
7.15 First the sequence {3, 1, 4, 1} is sorted. To do this, the sequence {3, 1} is sorted. This involves
sorting {3} and {1}, which are base cases, and merging the result to obtain {1, 3}. The sequence
7.16 Mergesort can be implemented nonrecursively by first merging pairs of adjacent elements, then
pairs of two elements, then pairs of four elements, and so on.
void mergesort( vector<Comparable> & a )
7.19 The original input is
3, 1, 4, 1, 5, 5, 2, 6, 5, 3, 9
Thus the pivot is 5. Hiding it gives
We now recursively quicksort the first eight elements:
3, 1, 4, 1, 5, 3, 2, 5
Sorting the three appropriate elements gives
The first swap is between 4 and 3:
1, 1, 3, 2, 5, 4, 3, 5
The next swap crosses pointers, so is undone; i points at 5, and so the pivot is swapped:
7.20 (a) O(N log N) because the pivot will partition perfectly.
7.21 (a) If the first element is chosen as the pivot, the running time degenerates to quadratic in the first two cases.
(c) If a random element is chosen, then the running time is O(N log N) expected for all inputs, although there
(d) This is a dangerous road to go; it depends on the distribution of the keys. For many distributions, such as
(b) Sentinels need to be used to guarantee that i and j don’t run past the end. The running time will be (N2)
7.24 The strategy used here is to force the worst possible pivot at each stage. This doesn’t necessarily give the
maximum amount of work (since there are few exchanges, just lots of comparisons), but it does give (N2)
7.26 Each recursive call is on a subarray that is less than half the size of the original, giving a logarithmic number
7.29
template<typename Comparable>
void selectionSort(vector<Comparable> & toSort)
7.32 (d) f (N) can be O(N/log N). Sort the f (N) elements using mergesort in O(f (N) log f (N)) time. This is O(N) if f
(b) The information-theoretic lower bound is
2
log N
N
Applying Stirling’s formula, we can estimate the
7.37 Algorithms A and B require at least three comparisons based on the information-theoretic lower bound.
7.38 Here is a c++ implementation
/** Exercise738.c++
* Given N points in the plane, we are to find 4 of them that
* are collinear. The algorithm needs to be O(n^2 log_2 n).
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
}
bool operator == (const Point & point)
{
return (x == point.x && y == point.y);
}
};
class Line
return INF;
else
return (p2.y – p1.y)/(p2.x – p1.x);
};
void printPoints(vector<Point> collinear)
{
vector<Point>::iterator it;
int count = 0;
}
int main()
{
cout<<“enter the x and y coordinates for the “<<i<<“th point :”;
cin>>points[i].x>>points[i].y;
}
for (int i = 0; i < points.size(); i++)
for (int j = i+1 ; j < points.size(); j++)
{
line = new Line(points[i], points[j]);
lines.push_back(line);
}
else
7.39 First, we will find the smallest element, and then the second smallest. Create a binary tree based on the
elements of the array. First, the N values of the array will be the leaves of the tree. The higher levels of the
tree will be formed as follows.
Create a new higher level L-1 of the binary tree by taking each pair at level L of the tree, seeing which
number is smaller, and creating a parent node with this value. This procedure of creating new levels of the
tree completes once you have the root of the tree, which is the smallest value in the array.
As an illustration, consider the array: 5, 4, 7, 3, 2, 6, 1, 8.
And we create the next level of the tree:
3 1
4 3 2 1
5 4 7 3 2 6 1 8
Finally, add the root:
In order to find the smallest value, we needed to perform n/2 + n/4 + n/8 + … + 1 comparisons, which in this
7.40 Here is a Java implementation:
import java.util.Random;
public class Exercise740
{
public static int numComparisons;
public static final int N = 1048576; // Let N be some power of 2.
numComparisons = 0;
Pair p = findMaxMin(a, 0, N-1, false);
System.out.printf(“Among first %d elements, max = %d, min = %d, # comp =
%d\n”,
4.
numComparisons = 0;
p = findMaxMin(a, 0, N-1, true);
// Find the max and min of the array segment a[first..last].
// The parameter phaseTwo tells us if we are considering part (c)
// of the exercise, where we must split up the array recursively into
// sizes /2-1 and n/2+1 if n is even but not a multiple of 4.
public static Pair findMaxMin(int [] a, int first, int last, boolean
phaseTwo)
}
// Part (c) of the exercise tests a slight imbalance of the halves.
0)
midpoint = first + (last – first + 1)/2 – 1;
// Otherwise split into two halves
else
int min = (p1.y < p2.y) ? p1.y : p2.y;
return new Pair(max, min);
}
{
public int x;
public int y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
}
7.42 Note that any two fractions that are not equal differ by at least 1/N2. Thus rewrite the fractions as
7.43 Look at the middle elements of A and B. Let m1 and m2 be these two middle elements; assume m1 is the larger
7.44 We add a dummy N + 1th element, which we’ll call maybe. maybe satisfies false < maybe < true. Partition the
7.45 We add a dummy N + 1th element, which we’ll call probablyFalse. probablyFalse satisfies false <
probablyFalse < maybe. Partition the array around probablyFalse as in the previous exercise. Suppose that
(b) Compare and exchange (if necessary) a1 and a2 so that a1 a2, and repeat with a3 and a4 so that a3 a4.
Compare and exchange (if necessary) the two winners, a1 and a3. Assume without loss of generality that we
7.51 (a) For the given input, the pivot is 2. It is swapped with the last element. i will point at the second element,
and j will be stopped at the first element. Since the pointers have crossed, the pivot is swapped with the
(b) Although the first pivot generates equal partitions, both the left and right halves will have the same form
7.52 We show that in a binary tree with L leaves, the average depth of a leaf is at least log L. We can prove this by
induction. Clearly, the claim is true if L = 1. Suppose it is true for trees with up to L − 1 leaves. Consider a
7.55 (b) After sorting the items do a scan using an outer loop that considers all positions p, and an inner loop that