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

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

Re: Using Java Classes to Sort a Small Array Quickly

Show all headers | View raw

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. 
Mind you that I expected O(n) as being used as a general description of 
the complexity, not as upper bound. Yes, I was making a joke there, but 
there is a serious side to it:
Since the number range is limited to the maximum number of buckets and 
the size of the sequence is limited to the maximum capacity of a bucket, 
this is no general sort. But a specialized sort like that is not 
impractical at all, it's just of limited use. Say you've got a list of 
some ten thousands of books that need to be sorted by their price or 
number of pages whatsoever, then you'd have a pretty limited range of 
numbers (buckets). So given enough memory you could sort them very, very 
fast and if it's just for finding the median. If that's what you have to 
do very, very often it may be worth considering.
Linked Lists are also of limited use, so what? There are particular use 
cases where they can be the best data structure for the job.

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

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