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

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

Re: Using Java Classes to Sort a Small Array Quickly

Show all headers | View raw

On 9/16/2011 8:54 PM, Wanja Gayk wrote:
> In article<900ffdda-7170-44e3-a141-bfec09c74dd1
> @glegroupsg2000goo.googlegroups.com>, lewbloch@gmail.com says...
>>
>> Arne Vajhøj wrote:
>>> 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.  The hub of the joke was his reference to "O(n)" and calling it "proof" when he was making no statement about asymptotic performance.
>>>>
>>>> I get it.
>>>
>>> ????
>>>
>>> Bucket sort is O(n) in n.
>>
>> n+k in the average, n^2 worst-case, but that has nothing to do with the joke as I read it.  It looked like he was talking about one specific array, and then he challenged us with "I didn't say it works for any array out there, did I?"
>>
>> It looks like I did misread his post.  I didn't realize he was speaking of the general case given the presence of only one input.
>
> The claim was that _any_ sort would be at least O(n log n). I've proven
> him wrong by sorting something in o(n) using a kind of bucket sort, that
> trades number range for runtime complexity.

     And for correctness.

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

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

Thread

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

csiph-web