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 <esosman@ieee-dot-org.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Using Java Classes to Sort a Small Array Quickly
Date: Sun, 11 Sep 2011 17:53:03 -0400
Organization: A noiseless patient Spider
Lines: 62
Message-ID: <j4jala$dkh$1@dont-email.me>
References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <j3mupc$d5m$1@dont-email.me> <MPG.28d742f5c91d21e9896b8@202.177.16.121>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 11 Sep 2011 21:53:46 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="f8igmItKsWs6nM5YanFxAA"; logging-data="13969"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/sc7FTxjC5vTECnqwOxQbZ"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2
In-Reply-To: <MPG.28d742f5c91d21e9896b8@202.177.16.121>
Cancel-Lock: sha1:iagdC/JNW/j0Vc2psVSs5ZoLshc=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7829

On 9/11/2011 5:14 PM, Wanja Gayk wrote:
> In article<j3mupc$d5m$1@dont-email.me>, -@. says...
>>
>> On 8/31/2011 7:48 PM, KevinSimonson wrote:
>>> On the way home from work my fellow carpooler told me that there are
>>> Java classes that can do sorts in O(N) time.
>>
>>
>> Pfft.  No.  Theoretical maximum speed of a sort is something like n log
>> n.  The only data you can sort in n time is data that's already sorted.
>
> Wrong.
> Here's the proof: Sorting an array of positive integers in O(n) time:
>
>   public static void main(final String[] args) {
>    final int[] data = new int[]{3,7,6,3,5,4,1,3,1,1,1,3,4,6,0,0};
>    System.out.println(Arrays.toString(data));
>    sort(data);
>    System.out.println(Arrays.toString(data));
>   }
>
>   private static void sort(final int[] data) {
>    if (data.length>  0) {
>     long max = Long.MIN_VALUE;
>     for (final int t : data) {
>      max = Math.max(t, max);
>     }
>     final long[][] buckets = new long[(int) max+1][data.length];
>     for (final long[] bucket : buckets) {
>      Arrays.fill(bucket, Long.MIN_VALUE);
>     }
>     for (final int x : data) {
>      for (int y = 0; y<  buckets[x].length; ++y) {
>       if (buckets[x][y] == Long.MIN_VALUE) {
>        buckets[x][y] = x;
>        break;
>       }
>      }
>     }
>     int x = -1;
>     for (long[] bucket : buckets) {
>      for (long value : bucket) {
>       if (value == Long.MIN_VALUE) {
>        break;
>       }
>       data[++x] = (int) value;
>      }
>     }
>    }
>   }

     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?

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