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

Re: Using Java Classes to Sort a Small Array Quickly

Date	2011-09-13 21:51 -0400
From	Arne Vajhøj <arne@vajhoej.dk>
Newsgroups	comp.lang.java.programmer
Subject	Re: Using Java Classes to Sort a Small Array Quickly
References	(4 earlier) <MPG.28d76557830521d69896ba@202.177.16.121> <fuhs67lrl26ubtv16brfg56c4kueldb28k@4ax.com> <4e6e8f47$0$308$14726298@news.sunsite.dk> <j4mblo$p46$1@dont-email.me> <j4mgb0$h1c$1@dont-email.me>
Message-ID	<4e700893$0$311$14726298@news.sunsite.dk> (permalink)
Organization	SunSITE.dk - Supporting Open source

Show all headers | View raw

On 9/12/2011 10:49 PM, markspace wrote:
>> 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 don't think upper bound in this case means worst case.

See:
 
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

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

O(n*logn) is by far the most likely. Which is why that is usually given
as the big O for QS when it is not mentioning both average and worst
case.

But it is possible to have data with O(n^2).

Note that this worst case is only sorted data when using the
first or last element as pivot element. If you use the middle
element as pivot element, then QA works perfectly for sorted data.

(there are the same number of worst cases, but sorted is
just not one of them)

Arne

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