Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Verifying a list is alphabetized
Date: Sat, 03 Dec 2011 09:02:47 -0500
Organization: A noiseless patient Spider
Lines: 41
Message-ID: <jbda6g$nh$1@dont-email.me>
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>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 3 Dec 2011 14:02:56 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="HSlJAUb3pGXi3i7ZL/HoAw"; logging-data="753"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19D0vTCjKW6eUSs0vpr1Pyd"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:8.0) Gecko/20111105 Thunderbird/8.0
In-Reply-To: <jbd5k5$86c$1@dont-email.me>
Cancel-Lock: sha1:CI6s3jOJMvyfa67BGu73uCtHrb8=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10466

On 12/3/2011 7:44 AM, Eric Sosman wrote:
> On 12/2/2011 7:54 PM, Arne Vajhøj wrote:
>> On 11/30/2011 11:05 AM, Knute Johnson wrote:
>>> On 11/30/2011 7:52 AM, laredotornado wrote:
>>>> I'm using Java 1.6. Given a java.util.List of Strings, what is the
>>>> quickest way to verify that the list is sorted in ascending order?
>>>>
>>>> Thanks, - Dave
>>>
>>> If it could possibly unsorted, I'd just sort it. How big is this list
>>> anyway?
>>
>> If it is small it does not matter.
>>
>> But I would not recommend an O(nlogn) solution for a O(n)
>> problem unless there is a note in 72 pt red blinking
>> on top of it.
>
> What is the big-Oh complexity of Collections.sort(List<String>)
> on an already-sorted list?
>[...]

     Just for fun, I tried it out.  For a twenty-element ArrayList,
Vector, Stack, or LinkedList, Collections.sort() uses

     19 comparisons if the List is in strictly increasing order,

     19 comparisons if the List is in non-decreasing order but
        with equal elements,

     19 comparisons if the List is in strictly decreasing order,

     70 comparisons (!) if the List is in non-increasing order but
       with equal elements.  (Likely data-dependent.)

     Conclusion: I think using the color red for the 72-point
blinking note is overkill.  Try white, on a white background. :)

-- 
Eric Sosman
esosman@ieee-dot-org.invalid