Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #10517
| From | Gene Wirchenko <genew@ocis.net> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Verifying a list is alphabetized |
| Date | 2011-12-04 21:34 -0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <uqlod795uc9mu7mvva3e3kt2kmlor1hbcm@4ax.com> (permalink) |
| References | <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <jb5k7n$g4u$1@dont-email.me> <4ed9732b$0$294$14726298@news.sunsite.dk> <jbd5k5$86c$1@dont-email.me> <b5sld7ltif6oi2tke3q2fkr5vnr2cc6nkc@4ax.com> |
On Sat, 03 Dec 2011 20:05:24 -0800, Roedy Green
<see_website@mindprod.com.invalid> 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.
Ordered either way. If you try to sort something that is in
reverse order, it is also a pathological case. This makes Quicksort
O(n squared) because of this worst case.
>Most of the time when I sort things, they are already sorted. Nothing
>has changed since the last sort, or when I manually edit files I
>naturally keep them in order.
Then an insertion sort will do.
>You also check inorder in an assert, not as a prelude to sorting. If
>it is not in order, something went wrong.
It depends on your needs.
Sincerely,
Gene Wirchenko
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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