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

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

Re: Using Java Classes to Sort a Small Array Quickly

Show all headers | View raw

On 9/12/2011 7:13 PM, Arne Vajhøj wrote:
> On 9/11/2011 11:30 PM, Lew wrote:
>> Arne Vajhøj wrote:
>>> Wanja Gayk wrote:
>>>> esosman@ieee-dot-org.invalid says...
>>>>> Wanja Gayk wrote:
>>>>>> Here's the proof: Sorting an array of positive integers in O(n) time:
>> ...
>>>>> Very nice! Would you care to try this approach on a shorter
>>>>> input array, like
>>>>>
>>>>> data = new int[] { Integer.MAX_VALUE };
>>>>>
>>>>> This case should be quite simple, since the array is already sorted.
>>>>> Let us know how you make out, will you?
>>>>
>>>> I didn't say it works for any array out there, did I?
>>
>> By using big-O notation, you said something about the behavior of the
>> algorithm as the size of the data set tends to infinity, so yes, you did.
>>
>>> No.
>>>
>>> But a solution is a bit more practical if it does.
>>
>> Wanja was making a joke. The performance of an algorithm on one
>> particular data set is irrelevant to a discussion of asymptotic
>> performance.

     What about correctness?  Try his code on the one-element array
I offered: I guarantee that performance will not be an issue.  (In
particular, I guarantee you will not get a correct result *and* you
will not run out of memory.)

> Bucket sort is O(n) in n.

     It depends on what you choose to count, and how.  Question: How
much time does it take to select between K alternatives?  You need
at least lg(K) decisions.  Even if those decisions are being made at
the level of individual transistors you need more time to coordinate
a thousand transistors than to coordinate three.  In hardware, this
shows up as a slower clock speed, and in other ways as well, so it
is an error to consider "time to decision" as a constant.

     Depending on how you choose to count.  Many things can be proven
if you select your counting schemes with due care ...

     There's a famous algorithm for finding the largest of an unlimited
quantity of positive numbers: You represent the numbers as chunks of
uncooked spaghetti, each of a length proportional to the number
represented.  That's your input.  Algorithm: Pick up the whole bunch,
turn it upright, plonk one end down on the kitchen counter, and pluck
out the tallest spaghetto (spaghettus?).  Voila! An O(1) maximum-
finding algorithm!

     Discerning the flaws in this method is left as an exercise for
the astute reader.

> Big O for execution speed traditionally does not look at
> memory restrictions and data type restrictions.

     Big O for proton density traditionally does not look at execution
time.  Big O for the error in Stirling's approximation traditionally
does not look at proton density.  Big O for X traditionally does not
look at Y.  So?

-- 
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 Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 02:54 +0200
              Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-16 21:03 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 16:52 +0200
                Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-17 11:05 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-18 15:41 +0200
                Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-18 12:53 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-18 13:20 -0700
          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 Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 02:54 +0200
                Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-16 21:13 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-16 23:14 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 16:53 +0200
                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 Gene Wirchenko <genew@ocis.net> - 2011-09-14 11:00 -0700
                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