Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!nx01.iad01.newshosting.com!newshosting.com!69.16.185.21.MISMATCH!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 02 Dec 2011 07:58:23 -0600
Date: Fri, 02 Dec 2011 05:58:17 -0800
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:8.0) Gecko/20111105 Thunderbird/8.0
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: Verifying a list is alphabetized
References: <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <207hd7h05rmodleca7qv41h73luek13qmm@4ax.com>
In-Reply-To: <207hd7h05rmodleca7qv41h73luek13qmm@4ax.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <LKmdnf5NRegdREXTnZ2dnUVZ_rudnZ2d@earthlink.com>
Lines: 40
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.194.31
X-Trace: sv3-l2KJNz22j/LS3XZ+zDCk+rA23yWcDkn1Q6hbBXZSf+p3PRKrKLW9szcCA51hyBvseM/MMpxrQa/wVeR!Hby5JcYYPLN/TWgXEzOOYqh+y7MzYDdGfCTRZ0ikU/HFcD2sRSbRM1Bs4BjtHhj5AAbpVoTJfDK+!vQKtPP91WJ+FruPDidMYiQfgD01ScELiS94ozpmoha9MwA==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2643
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10423

On 12/2/2011 1:43 AM, Roedy Green wrote:
> On Wed, 30 Nov 2011 07:52:49 -0800 (PST), laredotornado
> <laredotornado@zipmail.com>  wrote, quoted or indirectly quoted someone
> who said :
>
>> 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?
...
>     /**
>      * Is this List already in order according to its Comparable
> interface?
>      *
>      * @param list List of Comparable objects.
>      *
>      * @return true if array already in order.
>      */
>     public static <T extends Comparable<? super T>> boolean inOrder(
> List<T> list )
>         {
>         final int length = list.size();
>         for ( int i = 1; i < length; i++ )
>             {
>             if ( list.get( i ).compareTo( list.get( i - 1 ) ) < 0 )
>                 {
>                 return false;
>                 }
>             }
>         return true;
>         }


This will not be the quickest way unless the List happens to have fast
indexed access. For a length N linked list, it will take O(N*N) time.

Generally, if you are scanning a List that is not known to implement
RandomAccess, it is better use Iterator-based methods as much as
possible. They are almost as fast as indexed access for RandomAccess
lists, and much faster for the other List implementations.

Patricia