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

Re: Using Java Classes to Sort a Small Array Quickly

From	markspace <-@.>
Newsgroups	comp.lang.java.programmer
Subject	Re: Using Java Classes to Sort a Small Array Quickly
Date	2011-09-12 19:49 -0700
Organization	A noiseless patient Spider
Message-ID	<j4mgb0$h1c$1@dont-email.me> (permalink)
References	(3 earlier) <j4jala$dkh$1@dont-email.me> <MPG.28d76557830521d69896ba@202.177.16.121> <fuhs67lrl26ubtv16brfg56c4kueldb28k@4ax.com> <4e6e8f47$0$308$14726298@news.sunsite.dk> <j4mblo$p46$1@dont-email.me>

Show all headers | View raw

> On 9/12/2011 7:01 PM, Arne Vajhøj wrote:
>> No - big O for algorithms is usual average case not worst case.

I'm pretty sure that is not correct.  Quoting Wikipedia:

"Informally, especially in computer science, the Big O notation often is 
permitted to be somewhat abused to describe an asymptotic tight bound 
where using Big Theta Θ notation might be more factually appropriate in 
a given context."

That is to say, Big O is the upper bound.  Big Theta is the average case 
or the expected case.

<http://en.wikipedia.org/wiki/Big_O_notation>

>> I am sure you can find plenty of quotes for quicksort being
>> O(nlogn) and not O(n^2).

On 9/12/2011 6:29 PM, Eric Sosman wrote:
> Quicksort takes O(n*log n) *average* time, O(n*n) *worst case*
> time.

Both of these are also incorrect, I think.  The sort time for quick sort 
is O(n log n) for RANDOM data.  This can be proven.  The worst case is 
O(n^2) and that's for already sorted data, a not unreasonable input.  So 
the n log n number for quicksort is for a particular arrangement of 
data, not the actual upper bound.

The random data argument is a bit like the spaghetti sort.  It works 
well for certain types of input, like spaghetti, not so well with other 
types of data.

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

Thread

Using Java Classes to Sort a Small Array Quickly KevinSimonson <kvnsmnsn@hotmail.com> - 2011-08-31 19:48 -0700
  Re: Using Java Classes to Sort a Small Array Quickly markspace <-@.> - 2011-08-31 20:39 -0700
    Re: Using Java Classes to Sort a Small Array Quickly bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-09-01 09:18 +0100
    Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:38 -0700
      Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-01 03:50 -0700
    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
  Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 00:25 -0400
    Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 00:54 -0400
    Re: Using Java Classes to Sort a Small Array Quickly bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-09-01 09:20 +0100
      Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 08:06 -0400
    Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:43 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Robert Klemme <shortcutter@googlemail.com> - 2011-09-01 08:32 +0200
  Re: Using Java Classes to Sort a Small Array Quickly RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-09-01 10:08 +0100
    Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-01 04:02 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:37 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 04:53 -0700
  Re: Using Java Classes to Sort a Small Array Quickly Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-01 09:05 -0500

csiph-web