Re: Verifying a list is alphabetized

From:

Patricia Shanahan <pats@acm.org>

Newsgroups:

comp.lang.java.programmer

Date:

Fri, 02 Dec 2011 05:58:17 -0800

Message-ID:

<LKmdnf5NRegdREXTnZ2dnUVZ_rudnZ2d@earthlink.com>

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