Java Reference
In-Depth Information
{
int compare (Coin a, Coin b);
}
The call
comp.compare(a, b)
must return a negative number if
a
should come before
b
, 0 if
a
and
b
are the
same, and a positive number otherwise. (Here,
comp
is an object of a class that
implements
Comparator<Coin>
.)
For example, here is a
Comparator
class for coins:
public class CoinComparator implements
Comparator<Coin>
{
public int compare(Coin a, Coin b)
{
if (a.getValue() < b.getValue()) return -1;
if (a.getValue() == b.getValue()) return 0;
return 1;
}
}
657
658
To sort an array of coins by value, call
Arrays.sort(coins, new CoinComparator());
CHAPTER SUMMARY
1. The selection sort algorithm sorts an array by repeatedly finding the smallest
element of the unsorted tail region and moving it to the front.
2. Computer scientists use the big-Oh notation f(n)=O(g(n)) to express that the
function f grows no faster than the function g.
3. Selection sort is an O(n
2
) lgorithm. Doubling the data set means a fourfold
increase in processing time.
4. Insertion sort is an O(n
2
) algorithm.