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

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

Re: Using Java Classes to Sort a Small Array Quickly

Show all headers | View raw

On 8/31/2011 10: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>.
>
> I wrote a little program that compares the performance of
> SelectionSort and InsertionSort on comparable arrays of<String>s, and
> discovered that InsertionSort sorts in about half the amount of time
> that InsertionSort does, at least on our machines.  Therefore I
> implemented my static method,<alphaSort()>, using InsertionSort.

     Failed to find Arrays.sort, did you?

> On the way home from work my fellow carpooler told me that there are
> Java classes that can do sorts in O(N) time.

     Possible, perhaps, for restricted key types and given some
assumptions about the possible values: For instance, it's easy to
sort an array of `boolean' in O(N) time.  But quite clearly *not*
possible for sorts based on pairwise comparisons, since log(N!)
grows faster than O(N).

> That would be an
> improvement, since although InsertionSort is faster than
> SelectionSort, it's still an O(N^2) algorithm.

     So?  N in your case is twelve.  There's no point in studying the
behavior "as twelve approaches infinity," becase it doesn't.

     Besides, you're misusing O.  Suppose I offer you two algorithms,
one whose running time is O(N^2) and the other O(N).  Which is faster?
Before you say "O(N), nitwit," let me show you the actual timing
formulae:

	T1(N) = N * N (nanoseconds)
	T2(N) = N (gigayears)

T1(N) is clearly O(N^2), while T2(N) is O(N).  Which do you choose
for sorting N=12 items?

> So I went looking, but
> all I could find was the<sort()>  method from the<Collections>
> class.

     Either your looking was extremely cursory, or you haven't learned
how to look.  I'm not sure how you found Collections.sort, but *if*
you had opened the Javadoc, gone to the "S" index page, and hunted for
the word "sort," you'd have found Arrays.sort right next door to it.

> I replaced my code for SelectionSort with a loop that reads
> the input array into an<ArrayList<  String>>  object, calls<sort()>  on
> the<ArrayList<  String>>  object, and then reads the values back into
> the array; and then ran my test code again.  This method was
> significantly faster than SelectionSort, but my InsertionSort code
> still beat it.

     Your improved Javadoc searching skills would have found Arrays.sort,
which might have directed your attention to the Arrays class as a whole
and led you to discover Arrays.asList.  Or possibly not, because you
have no need of a List anyhow.  Meanwhile you've run "seven times around
the seven hills of Rome," and it's no surprise that the unnecessary trip
has made your task take longer than it needed to.

> So I guess my question is,<b><i>is</i></b>  there a way in Java to
> sort an array of<String>s (or perhaps more to the point to sort an
> array of<ProjectEnum>s) that runs in O(N) time?  Or even that runs in
> O(N^2) time but faster than InsertionSort?  I'd appreciate any
> information anyone can give me on this.

     Probably nothing of O(N); see remarks above.  Also probably
nothing as bad as O(N^2), but you can always do the hills of Rome
thing to slow down a better method if you want.

     BUT, BUT, BUT!  Your N is a constant, a small constant!  Even if
your hand-crafted sort runs at ten times the speed of Arrays.sort,
I posit that you have already expended more time than your speedy
method will ever recoup: If Arrays.sort takes a microsecond while
yours takes 100 nanoseconds, and if all your investigation and
implementation (and writing to Usenet) took just ten minutes, you
need more than six hundred billion fast sorts merely to break even.
Modify the arithmetic as needed in light of your actual measurements,
then turn your talents elsewhere instead of wasting them on a non-
problem.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next 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