Solutions Manual: Chapter 18 Big Java, by Cay Horstmann 1
Review Exercises
R18.1
Array length 0 or 1: i < a.length - 1 is not true when i equals 0, the for loop in the sort method never executes and the array is unchanged. That is ok.
Array length 2: The for loop in sort executes once, with i = 0. minimumPosition(0) is called. The for loop in that method executes from i going from 1 to less than 2, i.e. that loop also executes once. minPos is initially 0. If a[1] is less than a[0], then minPos is set to 1. When the method returns, if minPos is not 0 (i.e. a[1]a[0]), then the two values are swapped, which causes the array to be sorted.
Array length 3: There are six possible variations of the array. Using 1, 2, 3 for the three elements, they are
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Here is a walk-through for the last scenario. The others are similar.
a[0] a[1] a[2] i minPos
3 2 1 0 0
3 2 1 0 2
1 2 3 0 2
1 2 3 1 1
1 2 3 1 2
R18.3
n2+2n+1 / O(n2) / n3-1000n2+109 / O(n3)n10+9n9+20n8+145n7 / O(n10) / n + log n / O(n)
(n + 1)4 / O(n4) / n2 + nlog n / O(n2)
(n2 + n)2 / O(n4) / 2n+n2 / O(2n)
n+0.001n3 / O(n3) / (n3+2n)/(n2+0.75) / O(n)
R18.5
For a set of 2000 records, it will take 10 seconds.
For a set of 10,000 records, it will take 50 seconds.
R18.7
- O(1)
- O(log (n))
- O(sqrt(n))
- O(n)
- O(n log (n))
- O(n sqrt(n))
- O(n2 log (n))
- O(n3)
- O(nlog (n))
- O(2n)
- O(nn)
R18.9
The for loop is executed n times, where n is the length of the array. So it is an O(n) algorithm.
R18.11
Sorting takes O(n log n) time. After the array is sorted, we traverse it.
If we detect adjacent duplicates, we must move the remainder of the array down, which takes on average n/2 steps. So in the worst case this might be an O(n log n + n·n/2) = O(n2) algorithm.
However, you can easily do better. Sort the array (O(n log n)). Traverse the array, and whenever the next element is strictly larger, append it into a second array (O(n)). Then copy the second array back into the first (O(n)). The result is an O(n log n) algorithm. (You can even avoid the second array by moving the elements to the head the original array.)
R18.13
The process needs to be repeated n times, where n is the size of the array. We'll look at the average case, when the size of b is n/2. It takes O(n/4) steps for the insertion. So the entire algorithm is O(n·n/4) = O(n2). That is not an efficient sorting algorithm.
Programming Exercises
P18.1
ArrayUtil.java
import java.util.Random;
/**
This class contains utility methods for array
manipulation.
*/
public class ArrayUtil
{
/**
Creates an array filled with random values.
@param length the length of the array
@param n the number of possible random values
@return an array filled with length numbers between
0 and n-1
*/
public static int[] randomIntArray(int length, int n)
{ int[] a = new int[length];
Random generator = new Random();
for (int i = 0; i < a.length; i++)
a[i] = generator.nextInt(n);
return a;
}
/**
Prints all elements in an array.
@param a the array to print
*/
public static void print(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
SelectionSorter.java
/**
This class sorts an array, using the selection sort
algorithm
*/
public class SelectionSorter
{
/**
Constructs a selection sorter.
@param anArray the array to sort.
*/
public SelectionSorter(int[] anArray)
{
a = anArray;
}
/**
Sorts the array managed by this selection sorter.
*/
public void sort()
{
for (int n = 0; n < a.length - 1; n++)
{
int maxPos = maximumPosition(n);
if (maxPos != n)
swap(maxPos, n);
}
}
/**
Finds the largest element in an array range.
@param from the first position in a to compare
@return the position of the largest element in the
range a[from]...a[a.length - 1]
*/
public int maximumPosition(int from)
{
int maxPos = from;
for (int i = from + 1; i < a.length; i++)
if (a[i] > a[maxPos]) maxPos = i;
return maxPos;
}
/**
Swaps two entries of the array.
@param i the first position to swap
@param j the second position to swap
*/
private void swap(int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private int[] a;
}
ExP18_1.java
/**
This class tests the SelectionSorter class.
*/
public class ExP18_1
{
public static void main(String[] args)
{
int[] a = ArrayUtil.randomIntArray(20, 100);
ArrayUtil.print(a);
SelectionSorter s = new SelectionSorter(a);
s.sort();
ArrayUtil.print(a);
}
}
P18.3
StopWatch.java
/**
A stopwatch accumulates time when it is running. You can
repeatedly start and stop the stopwatch. You can use a
stopwatch to measure the running time of a program.
*/
public class StopWatch
{
/**
Constructs a stopwatch that is in the stopped state
and has no time accumulated.
*/
public StopWatch()
{
reset();
}
/**
Starts the stopwatch. Time starts accumulating now.
*/
public void start()
{
if (isRunning) return;
isRunning = true;
startTime = System.currentTimeMillis();
}
/**
Stops the stopwatch. Time stops accumulating and is
is added to the elapsed time.
*/
public void stop()
{
if (!isRunning) return;
isRunning = false;
long endTime = System.currentTimeMillis();
elapsedTime = elapsedTime + endTime - startTime;
}
/**
Returns the total elapsed time.
@return the total elapsed time
*/
public long getElapsedTime()
{
if (isRunning)
{
long endTime = System.currentTimeMillis();
elapsedTime = elapsedTime + endTime - startTime;
startTime = endTime;
}
return elapsedTime;
}
/**
Stops the watch and resets the elapsed time to 0.
*/
public void reset()
{
elapsedTime = 0;
isRunning = false;
}
private long elapsedTime;
private long startTime;
private boolean isRunning;
}
ArrayUtil.java
import java.util.Random;
/**
This class contains utility methods for array
manipulation.
*/
public class ArrayUtil
{
/**
Creates an array filled with random values.
@param length the length of the array
@param n the number of possible random values
@return an array filled with length numbers between
0 and n-1
*/
public static int[] randomIntArray(int length, int n)
{ int[] a = new int[length];
Random generator = new Random();
for (int i = 0; i < a.length; i++)
a[i] = generator.nextInt(n);
return a;
}
/**
Prints all elements in an array.
@param a the array to print
*/
public static void print(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
SelectionSorter.java
/**
This class sorts an array, using the selection sort
algorithm
*/
public class SelectionSorter
{
/**
Constructs a selection sorter.
@param anArray the array to sort.
*/
public SelectionSorter(int[] anArray)
{
a = anArray;
}
/**
Sorts the array managed by this selection sorter.
*/
public void sort()
{
for (int i = 0; i < a.length - 1; i++)
{
int minPos = minimumPosition(i);
swap(minPos, i);
}
}
/**
Finds the smallest element in a tail range of the array
@param from the first position in a to compare
@return the position of the smallest element in the
range a[from]...a[a.length - 1]
*/
private int minimumPosition(int from)
{
int minPos = from;
for (int i = from + 1; i < a.length; i++)
if (a[i] < a[minPos]) minPos = i;
return minPos;
}
/**
Swaps two entries of the array.
@param i the first position to swap
@param j the second position to swap
*/
private void swap(int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private int[] a;
}
ExP18_3.java
import javax.swing.JOptionPane;
/**
This class tests the SelectionSorter class.
*/
public class ExP18_3
{
public static void main(String[] args)
{
String input = JOptionPane.showInputDialog(
"Enter smallest array size:");
int n1 = Integer.parseInt(input);
input = JOptionPane.showInputDialog(
"Enter largest array size:");
int n2 = Integer.parseInt(input);
input = JOptionPane.showInputDialog(
"Enter number of measurements (>=2):");
int m = Integer.parseInt(input);
for (int i = 0; i < m; i++)
{
int n = n1 + i * (n2 - n1) / (m - 1);
int[] a = ArrayUtil.randomIntArray(n, 100);
// use stopwatch to time selection sort
StopWatch timer = new StopWatch();
timer.start();
SelectionSorter s = new SelectionSorter(a);
s.sort();
timer.stop();
System.out.println("n:" + n + ". Elapsed time: "
+ timer.getElapsedTime() + " milliseconds");
}
System.exit(0);
}
}
P18.5
Item.java
/**
An item in a phone book.
*/
public class Item
{
/**
Constructs an Item object.
@param k the key string
@param v the value of the item
*/
public Item(String k, String v)
{
key = k;
value = v;
}
/**
Gets the key.
@return the key
*/
public String getKey()
{
return key;
}
/**
Gets the value.
@return the value
*/
public String getValue()
{
return value;
}
private String key;
private String value;
}
ArrayUtil.java
import java.util.Random;
/**
This class contains utility methods for array
manipulation.
*/
public class ArrayUtil
{
/**
Creates an array filled with random values.
@param length the length of the array
@param n the number of possible random values
@return an array filled with length numbers between
0 and n-1
*/
public static int[] randomIntArray(int length, int n)
{ int[] a = new int[length];
Random generator = new Random();
for (int i = 0; i < a.length; i++)
a[i] = generator.nextInt(n);
return a;
}
/**
Prints all elements in an array.
@param a the array to print
*/
public static void print(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
BinarySearcher.java
/**
A class for executing binary searches through an array.
*/
public class BinarySearcher
{
/**
Constructs a BinarySearcher.
@param anItem a sorted array of items
*/
public BinarySearcher(Item[] anItem)
{
v = anItem;
}
/**
Finds a value in a sorted array, using the binary
search algorithm.
@param from the number to search from
@param to the number to search to
@param a the string to search
@return the index at which the value occurs, or -1
if it does not occur in the array
*/
public int binarySearch(int from,
int to, String a)
{
if (from > to)
return -1;
int mid = (from + to) / 2;
int diff = v[mid].getKey().compareTo(a);
if (diff == 0) /* v[mid] == a */
return mid;
else if (diff < 0) /* v[mid] < a */
return binarySearch(mid + 1, to, a);
else
return binarySearch(from, mid - 1, a);
}
private Item[] v;
}
LookupTable.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.FileReader;
/**
A lookup table for a phone list.
*/
public class LookupTable
{
/**
Constructs a LookupTable object.
@param n the maximum number of entries
*/
public LookupTable(int n)
{
items = new Item[n];
itemCount = 0;
}
/**
Reads a file.
@param in the file to read.
*/
public void read(BufferedReader in)
throws IOException
{
boolean more = true;
while (more & itemCount < items.length)
{
String k = in.readLine();
String v = null;
if (k != null) v = in.readLine();
if (v != null)
{
items[itemCount] = new Item(k, v);
itemCount++;
}
else more = false;
}
MergeSorter m = new MergeSorter(items);
m.sort();
}
/**
Reverse the lookup by reading phone numbers
@param b the LookupTable
*/
public void reverse(LookupTable b)
{
itemCount = Math.min(b.itemCount, items.length);
for (int i = 0; i < itemCount; i++)
{
items[i] = new Item(b.items[i].getValue(), b.items[i].getKey());
}
MergeSorter m = new MergeSorter(items);
m.sort();
}
/**
Looks up an entries in the list.
@param k the key to find
@return the item
*/
public String lookup(String k)
{
BinarySearcher b = new BinarySearcher(items);
int pos = b.binarySearch(0, itemCount - 1, k);
if (pos < 0)
return "Not found";
else
return items[pos].getValue();
}
private Item[] items;
private int itemCount;
}
MergerSorter.java
/**
This class sorts an array, using the merge sort
algorithm
*/
public class MergeSorter
{
/**
Constructs a merge sorter.
@param anItem the array of items to sort
*/
public MergeSorter(Item[] anItem)
{
a = anItem;
}
/**
Sorts the array managed by this merge sorter.
@param from the item to sort from
@param to the item to sort to
*/
/* public void sort(int from, int to)
{
if (from >= to) return;
int mid = (from + to) / 2;
/* sort the first and the second half */
/* sort(from, mid);
sort(mid + 1, to);
merge(from, mid, to);
}
/**
Merges two sorted arrays into the array to be sorted by this
merge sorter.
@param from the item to sort from
@param mid the middle of the items
@param to the item to sort to
*/
/* private void merge(int from, int mid,
int to)
{
int n = to - from + 1;
/* size of the range to be merged */
/* merge both halves into a temporary vector b */
/* Item[] b = new Item[n];
int i1 = from;
/* next element to consider in the first half */
/* int i2 = mid + 1;
/* next element to consider in the second half */
/* int j = 0; /* next open position in b */
/* as long as neither i1 nor i2 past the end, move
the smaller element into b
*/
/* while (i1 <= mid & i2 <= to)
{
if (a[i1].getKey().compareTo(a[i2].getKey()) < 0)
{
b[j] = a[i1];
i1++;
}
else
{
b[j] = a[i2];
i2++;
}
j++;
}
/* note that only one of the two while loops
below is executed
*/
/* copy any remaining entries of the first half */
/* while (i1 <= mid)
{
b[j] = a[i1];
i1++;
j++;
}
/* copy any remaining entries of the second half */
/* while (i2 <= to)
{
b[j] = a[i2];
i2++;
j++;
}
/* copy back from the temporary vector */
/* for (j = 0; j < n; j++)
a[from + j] = b[j];
}
*/
/**
Sorts the array managed by this merge sorter
*/
public void sort()
{
if (a.length <= 1)
return;
Item[] first = new Item[a.length / 2];
Item[] second = new Item[a.length - first.length];
System.arraycopy(a, 0, first, 0, first.length);
System.arraycopy(a, first.length, second, 0, second.length);
MergeSorter firstSorter = new MergeSorter(first);
MergeSorter secondSorter = new MergeSorter(second);
firstSorter.sort();
secondSorter.sort();
merge(first, second);
}
/**
Merges two sorted arrays into the array to be sorted by this
merge sorter.
@param first the first sorted array
@param second the second sorted array
*/
private void merge(Item[] first, Item[] second)
{
// merge both halves into the temporary array
int iFirst = 0;
// next element to consider in the first array
int iSecond = 0;
// next element to consider in the second array
int j = 0;
// next open position in a
// as long as neither iFirst nor iSecond past the end, move
// the smaller element into a
while (iFirst < first.length & iSecond < second.length)
{
if (first[iFirst].getKey().compareTo(second[iSecond].getKey()) < 0)
//if (a[iFirst].getKey().compareTo(a[iSecond].getKey()) < 0)
{
a[j] = first[iFirst];
iFirst++;
}
else
{
a[j] = second[iSecond];
iSecond++;
}
j++;
}
// note that only one of the two while loops
// below is executed
// copy any remaining entries of the first array
System.arraycopy(first, iFirst, a, j, first.length - iFirst);
// copy any remaining entries of the second half
System.arraycopy(second, iSecond, a, j, second.length - iSecond);
}
private Item[] a;
}
ExP18_5.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.FileReader;
import javax.swing.JOptionPane;
/* The input file has the format
Abbott, Amy
408-924-1669
Abeyta, Ric
408-924-2185
Abrams, Arthur
408-924-6120
Abriam-Yago, Kathy
408-924-3159
Accardo, Dan
408-924-2236
Acevedo, Elvira
408-924-5200
Acevedo, Gloria
408-924-6556
Achtenhagen, Stephen
408-924-3522
. . .
*/
public class ExP18_5
{
public static void main(String[] args)
{
String fileName = JOptionPane.showInputDialog(
"Enter the name of the phonebook file: ");
if (fileName == null)
System.exit(0);
LookupTable names = new LookupTable(1000);
try
{
FileReader in = new FileReader(fileName);
names.read(new BufferedReader(in));
}
catch (IOException exception)
{
System.out.println(exception);
System.exit(1);
}
LookupTable numbers = new LookupTable(1000);
numbers.reverse(names);
boolean more = true;
while (more)
{
String cmd = JOptionPane.showInputDialog(
"Lookup N)ame, P)hone number, Q)uit?");
if (cmd == null)
more = false;
else if (cmd.equalsIgnoreCase("Q"))
more = false;
else if (cmd.equalsIgnoreCase("N"))
{
String n = JOptionPane.showInputDialog(
"Enter name:");
System.out.println("Phone number: " + names.lookup(n));
}
else if (cmd.equalsIgnoreCase("P"))
{
String n = JOptionPane.showInputDialog(
"Enter phone number:");
System.out.println("Name: " + numbers.lookup(n));
}
}
System.exit(0);
}
}
P18.7
Coin.java
/**
A coin with a monetary value.
*/
public class Coin
{
/**
Constructs a coin.
@param aValue the monetary value of the coin.
@param aName the name of the coin
*/
public Coin(double aValue, String aName)
{
value = aValue;
name = aName;
}
/**
Gets the coin value.
@return the value
*/
public double getValue()
{
return value;
}
/**
Gets the coin name.
@return the name
*/
public String getName()
{
return name;
}
public String toString()
{
return "Coin[value=" + value + ",name=" + name + "]";
}
private double value;
private String name;
}
Purse.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
/**
A purse holds a collection of coins.
*/
public class Purse
{
/**
Constructs an empty purse.
*/
public Purse()
{
coins = new ArrayList();
}
/**
Add a coin to the purse.
@param aCoin the coin to add
*/
public void add(Coin aCoin)
{
coins.add(aCoin);
}
/**
Returns a string describing the purse contents,
sorted by the most valuable coin value.
@return the string describing the purse contents
*/
public String toString()
{
// sort the coins first
class CoinComparator implements Comparator
{
public int compare(Object firstObject, Object secondObject)
{
Coin first = (Coin)firstObject;
Coin second = (Coin)secondObject;
if (first.getValue() > second.getValue()) return -1;
if (first.getValue() == second.getValue()) return 0;
return 1;
}
}
Comparator comp = new CoinComparator();
Collections.sort(coins, comp);
String r = "Purse[coins=";
for (int i = 0; i < coins.size(); i++)
{
if (i > 0) r = r + ",";
r = r + coins.get(i);
}
return r + "]";
}
private ArrayList coins;
}
ExP18_7.java
import javax.swing.JOptionPane;
/**
This class tests the Purse class by prompting the
user to add coins into a purse and printing the
purse contents, sorted by coin value.
*/
public class ExP18_7
{
public static void main(String[] args)
{
double NICKEL_VALUE = 0.05;
double DIME_VALUE = 0.1;
double QUARTER_VALUE = 0.25;
Purse myPurse = new Purse();
boolean done = false;
while (!done)
{
String input
= JOptionPane.showInputDialog("Enter coin name or Cancel");
if (input == null)
done = true;
else
{
double value = 0;
if (input.equals("nickel"))
value = NICKEL_VALUE;
else if (input.equals("dime"))
value = DIME_VALUE;
else if (input.equals("quarter"))
value = QUARTER_VALUE;
if (value != 0)
{
Coin c = new Coin(value, input);
myPurse.add(c);
System.out.println("The contents of the purse is "
+ myPurse);
}
}
}
System.exit(0);
}
}
P18.9
ArrayUtil.java
import java.util.Random;
/**
This class contains utility methods for array
manipulation.
*/
public class ArrayUtil
{
/**
Creates an array filled with random values.
@param length the length of the array
@param n the number of possible random values
@return an array filled with length numbers between
0 and n-1
*/
public static int[] randomIntArray(int length, int n)
{ int[] a = new int[length];
Random generator = new Random();
for (int i = 0; i < a.length; i++)
a[i] = generator.nextInt(n);
return a;
}
/**
Prints all elements in an array.
@param a the array to print
*/
public static void print(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
BinarySearcher.java
/**
A class for executing binary searches through an array.
*/
public class BinarySearcher
{
/**
Constructs a BinarySearcher.
@param anArray a sorted array of integers
*/
public BinarySearcher(int[] anArray)
{
a = anArray;
}
/**
Finds a value in a sorted array, using the binary
search algorithm.
@param v the value to search
@param high the last index in the array to consider
@return the index at which the value occurs, or -k - 1