Re: Using Java Classes to Sort a Small Array Quickly
On 8/31/2011 9:48 PM, KevinSimonson wrote:
I have an<enum> named<ProjectEnum> that has twelve values. Today I
added an instance variable to it, a<String> named<collectionTitle>.
The engineer I'm working with asked me to write a static method in
class<ProjectEnum> that returns an array of<ProjectEnum>s sorted
alphabetically by this value<collectionTitle>.
Let me start by pointing out: you have 12 elements in your array to
sort. Any sort you pick, short of bogosort, would complete in at most a
millisecond or two, even on crappy old hardware.
On the way home from work my fellow carpooler told me that there are
Java classes that can do sorts in O(N) time. That would be an
improvement, since although InsertionSort is faster than
SelectionSort, it's still an O(N^2) algorithm.
The big-O notation is used to indicate asymptotic execution time, so
it's more useful if you're talking about high values of N (billions are
not unheard of in graph theory). At low values of N, the overhead in
setting up and per-element stuff can dominate the runtime.
The standard sort methods are quicksort (used in Java for primitive
arrays) and mergesort (used in Java for arrays of reference types).
These are both implemented recursively. However, recursion induces a
high overhead cost (setting up and tearing down the function stack isn't
cheap, and in these cases also involves yet another linear scan, etc.),
so when the array size is very small, it just sorts the array using
insertion sort. I do not recall the magic cutoff point off the top of my
had, but I believe it is between 8 and 16.
I would also like to point out that no comparison sort is capable of
achieving faster than O(n lg n) time in the worst case. Things like
radix sort can achieve O(n), at the cost of being dependent on the size
of the input, so they are less generally usable. Boolean sort and
possibly byte sort (given the extremely low numbers of values these can
attain) actually do use this sort of algorithm in Java.
So I went looking, but
all I could find was the<sort()> method from the<Collection
class.
Actually, Arrays.sort is the "main" sort method[s]: if you look at the
code for Collections.sort, it extracts the elements into an array, sorts
that array, and then reinserts the method in the Collections in order.
If you originally have an array, Arrays.sort will save you 4 buffer
copies. Since you commented that your insertion sort beat this method, i
am betting that it's the multiple copies that is making it slower than
your hand-built sort.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth