Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #7525

Re: Using Java Classes to Sort a Small Array Quickly

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Find similar

Thread

Using Java Classes to Sort a Small Array Quickly KevinSimonson <kvnsmnsn@hotmail.com> - 2011-08-31 19:48 -0700
  Re: Using Java Classes to Sort a Small Array Quickly markspace <-@.> - 2011-08-31 20:39 -0700
    Re: Using Java Classes to Sort a Small Array Quickly bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-09-01 09:18 +0100
    Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:38 -0700
      Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-01 03:50 -0700
    Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-11 23:14 +0200
      Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-11 17:53 -0400
        Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-12 01:40 +0200
          Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-11 20:32 -0400
          Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-11 21:10 -0400
            Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-11 20:30 -0700
              Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 19:13 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-12 17:42 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-12 21:24 -0400
          Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-12 10:57 -0700
            Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 19:01 -0400
              Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-12 21:29 -0400
                Re: Using Java Classes to Sort a Small Array Quickly markspace <-@.> - 2011-09-12 19:49 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-12 21:51 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-13 11:32 -0500
                Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-13 21:51 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-13 06:33 -0700
              Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-13 09:48 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 00:25 -0400
    Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 00:54 -0400
    Re: Using Java Classes to Sort a Small Array Quickly bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-09-01 09:20 +0100
      Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 08:06 -0400
    Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:43 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Robert Klemme <shortcutter@googlemail.com> - 2011-09-01 08:32 +0200
  Re: Using Java Classes to Sort a Small Array Quickly RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-09-01 10:08 +0100
    Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-01 04:02 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:37 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 04:53 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-01 09:05 -0500

csiph-web