Java Reference
In-Depth Information
}
}
Solution 65: A Strange Saga of a Suspicious Sort
The
main
method creates an array of
Integer
instances, initializes it with random values, and sorts
the array using the comparator
cmp
. This comparator's
compare
method returns its second argument
minus its first, which is positive if its second argument represents a larger value than its first, zero if
they're equal, and negative if its second argument represents a smaller value than its first. This is the
opposite of what is normally done by the
compare
method, so this comparator should impose a
descending order.
After sorting the array, the
main
method passes it to the static method
order
and prints the result
returned by this method. This method returns
CONSTANT
if all the elements in the array represent
equal values,
ASCENDING
if the second element in every adjacent pair is greater than or equal to the
first,
DESCENDING
if the second element in every adjacent pair is less than or equal to the first, and
UNORDERED
if none of these conditions holds. Although it is theoretically possible that all 100
random numbers in the array are equal to one another, the odds of this happening are infinitessimal:
1 in 2
32x99
, which is approximately 1 in 5 x 10
953
. Therefore, it seems likely that the program
should print
DESCENDING
. If you ran it, you almost certainly saw it print
UNORDERED
. Why would it
do such a thing?
The
order
method is straightforward, and it does not lie. The
Arrays.sort
method has been around
for years, and it works fine. This leaves only one place tolook for bugs: the comparator. At first
glance, it may seem unlikely that the comparator is broken. After all, it uses a standard idiom: If you
have two numbers and you want a value whose sign indicates their order, compute their difference.
This idiom has been around at least since the early 1970s. It was commonly used in the early days
of UNIX. Unfortunately, this idiom never worked properly. Perhaps this puzzle should have been
called "The Case of the Idiotic Idiom?" The problem with this idiom is that a fixed-width integer is
not big enough to hold the difference of two arbitrary integers of the same width. When you
subtract two
int
or
long
values, the result can overflow, in which case it will have the wrong sign.
For example, consider this program:
public class Overflow {
public static void main(String[] args) {
int x = -2000000000;
int z = 2000000000;
System.out.println(x - z);
}
Search WWH ::
Custom Search