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