Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Using Java Classes to Sort a Small Array Quickly Date: Fri, 16 Sep 2011 21:13:19 -0400 Organization: A noiseless patient Spider Lines: 49 Message-ID: References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <4e6d5bf5$0$316$14726298@news.sunsite.dk> <4e6e9217$0$308$14726298@news.sunsite.dk> <900ffdda-7170-44e3-a141-bfec09c74dd1@glegroupsg2000goo.googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 17 Sep 2011 01:13:44 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="f8igmItKsWs6nM5YanFxAA"; logging-data="21761"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/WVvWZU6zOVMSV0M4NQ6MG" User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2 In-Reply-To: Cancel-Lock: sha1:kJVeTuCxtZ06bsl5pGsugqQDpzE= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:8099 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