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

Re: Verifying a list is alphabetized

Date	2011-12-04 12:18 -0800
From	Patricia Shanahan <pats@acm.org>
Newsgroups	comp.lang.java.programmer
Subject	Re: Verifying a list is alphabetized
References	(1 earlier) <jb5k7n$g4u$1@dont-email.me> <4ed9732b$0$294$14726298@news.sunsite.dk> <jbd5k5$86c$1@dont-email.me> <b5sld7ltif6oi2tke3q2fkr5vnr2cc6nkc@4ax.com> <jbfpru$ksi$2@localhost.localdomain>
Message-ID	<WPidnXX0kcoMSEbTnZ2dnUVZ_q6dnZ2d@earthlink.com> (permalink)

Show all headers | View raw

On 12/4/2011 4:42 AM, Martin Gregorie wrote:
> On Sat, 03 Dec 2011 20:05:24 -0800, Roedy Green wrote:
>
>> On Sat, 03 Dec 2011 07:44:48 -0500, Eric Sosman
>> <esosman@ieee-dot-org.invalid>  wrote, quoted or indirectly quoted
>> someone who said :
>>
>>>      What is the big-Oh complexity of Collections.sort(List<String>)
>>> on an already-sorted list?
>>
>> IIRC QuickSort goes a bit bananas if the file is already sorted.  ISTR
>> some sort doing some random swaps at the start to make sure that does
>> not happen.  It does do a check first if things are in order.
>>
> I'm a little wary of quicksort's claim of superior speed in every
> situation.

I would be a lot wary of that claim if I ever saw it made. As pointed
out at the start of its Wikiedia article, it "on average, makes O(nlog
n) (big O notation) comparisons to sort n items. In the worst case, it
makes O(n2) comparisons, though this behavior is rare. Quicksort is
often faster in practice than other O(nlog n) algorithms"

The key words here are "on average" and "often faster". To test those
claims, it would be necessary to do many runs, in many different
situations, with different inputs.

However, I think the java.util developers made the right call in
deciding not to use it. Given that there are very effective algorithms
that are truly O(n log(n)), not just on average, why not use one of them?

Patricia

Thread

Verifying a list is alphabetized laredotornado <laredotornado@zipmail.com> - 2011-11-30 07:52 -0800
  Re: Verifying a list is alphabetized Knute Johnson <nospam@knutejohnson.com> - 2011-11-30 08:05 -0800
    Re: Verifying a list is alphabetized Lew <lewbloch@gmail.com> - 2011-11-30 11:18 -0800
    Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:54 -0500
      Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-03 07:44 -0500
        Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-03 09:02 -0500
        Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 20:05 -0800
          Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 22:13 -0800
            Re: Verifying a list is alphabetized Tom Anderson <twic@urchin.earth.li> - 2011-12-04 21:47 +0000
          Re: Verifying a list is alphabetized Martin Gregorie <martin@address-in-sig.invalid> - 2011-12-04 12:42 +0000
            Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 12:18 -0800
              Re: Verifying a list is alphabetized Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-04 13:17 -0800
                Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 15:32 -0800
                Re: Verifying a list is alphabetized markspace <-@.> - 2011-12-04 15:59 -0800
                Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 16:14 -0800
                Re: Verifying a list is alphabetized markspace <-@.> - 2011-12-04 17:12 -0800
                Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-04 21:17 -0500
            Re: Verifying a list is alphabetized Tom Anderson <twic@urchin.earth.li> - 2011-12-04 22:11 +0000
              Re: Verifying a list is alphabetized Martin Gregorie <martin@address-in-sig.invalid> - 2011-12-04 23:41 +0000
              Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-12 01:39 -0800
          Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-04 08:47 -0500
          Re: Verifying a list is alphabetized Gene Wirchenko <genew@ocis.net> - 2011-12-04 21:34 -0800
  Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-11-30 12:52 -0800
    Re: Verifying a list is alphabetized laredotornado <laredotornado@zipmail.com> - 2011-12-01 06:43 -0800
  Re: Verifying a list is alphabetized Joshua Maurice <joshuamaurice@gmail.com> - 2011-11-30 13:16 -0800
  Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-02 01:43 -0800
    Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-02 05:58 -0800
      Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:55 -0500
      Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 02:54 -0800
        Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-03 06:17 -0800
    Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 03:10 -0800
  Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:52 -0500

csiph-web