Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!news.glorb.com!news.netfront.net!not-for-mail
From: Wanja Gayk <brixomatic@yahoo.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: Using Java Classes to Sort a Small Array Quickly
Date: Sun, 11 Sep 2011 23:14:11 +0200
Organization: Netfront http://www.netfront.net/
Lines: 61
Message-ID: <MPG.28d742f5c91d21e9896b8@202.177.16.121>
References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <j3mupc$d5m$1@dont-email.me>
NNTP-Posting-Host: 77.8.106.205
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Trace: adenine.netfront.net 1315775658 95113 77.8.106.205 (11 Sep 2011 21:14:18 GMT)
X-Complaints-To: news@netfront.net
NNTP-Posting-Date: Sun, 11 Sep 2011 21:14:18 +0000 (UTC)
User-Agent: MicroPlanet-Gravity/3.0.4
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7824

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;
    }
   }
  }
 }


Kind regards,
Wanja

-- 
..Alesi's problem was that the back of the car was jumping up and down 
dangerously - and I can assure you from having been teammate to 
Jean Alesi and knowing what kind of cars that he can pull up with, 
when Jean Alesi says that a car is dangerous - it is. [Jonathan Palmer]

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---