Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #10365 > unrolled thread

Verifying a list is alphabetized

Back to article view | Back to comp.lang.java.programmer

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#10487

On 12/3/2011 11:05 PM, 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. [...]

     Since Collections.sort() does not use Quicksort (in fact, it
promises *not* to use Quicksort!), observations on Quicksort's
behavior, however interesting, do not bear on the issue at hand.

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

[toc] | [prev] | [next] | [standalone]

#10517

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

[toc] | [prev] | [next] | [standalone]

#10376

On 11/30/2011 7:52 AM, laredotornado wrote:
> Hi,
>
> 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?

If you just want to test, scan the list comparing consecutive pairs of
elements:

public static <T extends Comparable<? super T>> boolean isOrdered(
     List<T> data) {
   T oldElement = null;
   for (T currentElement : data) {
     if (oldElement != null
         && oldElement.compareTo(currentElement) > 0) {
       return false;
     }
     oldElement = currentElement;
   }
   return true;
}

If you want to achieve sortedness, you are unlikely to save time
compared to just doing the sort unconditionally.

Patricia

[toc] | [prev] | [next] | [standalone]

#10401

On Nov 30, 2:52 pm, Patricia Shanahan <p...@acm.org> wrote:
> On 11/30/2011 7:52 AM, laredotornado wrote:
>
> > Hi,
>
> > 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?
>
> If you just want to test, scan the list comparing consecutive pairs of
> elements:
>
> public static <T extends Comparable<? super T>> boolean isOrdered(
>      List<T> data) {
>    T oldElement = null;
>    for (T currentElement : data) {
>      if (oldElement != null
>          && oldElement.compareTo(currentElement) > 0) {
>        return false;
>      }
>      oldElement = currentElement;
>    }
>    return true;
>
> }
>
> If you want to achieve sortedness, you are unlikely to save time
> compared to just doing the sort unconditionally.
>
> Patricia

Great solution, Patricia.  Thanks, - Dave

[toc] | [prev] | [next] | [standalone]

#10379

On Nov 30, 7:52 am, laredotornado <laredotorn...@zipmail.com> wrote:
> Hi,
>
> 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?

Under which sort order / locale? The sorting of strings depends on
which language and culture and context.

Once you figure out which sort order you want to use (what is the
default anyway, depends on the current OS locale or something?), then
you could just iterate over the strings and compare each string to the
previous string and ensure that each adjacent pair is in sorted order.
That's O(n) where n is the length of the list, and you cannot do
better Big O than that. To be clear, this merely returns "is sorted" /
"not sorted", which is what you asked. It won't sort them.

[toc] | [prev] | [next] | [standalone]

#10414

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?

/*
 * [InOrder.java]
 *
 * Summary: Are arrays/collections already in order?.
 *
 * Copyright: (c) 2011 Roedy Green, Canadian Mind Products,
http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any
purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.5+
 *
 * Created with: JetBrains IntelliJ IDEA IDE
http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 2011-11-07 initial version
 */
package com.mindprod.common15;

import java.util.Comparator;
import java.util.List;

/**
 * Are arrays/collections already in order?.
 * <p/>
 * Generics for these methods were cannibalised from Arrays.sort and
Collections.sort.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.0 2011-11-07 initial version
 * @since 2011-11-07
 */
public final class InOrder
    {
    // -------------------------- PUBLIC STATIC METHODS
--------------------------

    /**
     * Is this array already in order according to its Comparable
interface?
     * Generics and arrays don't get along well.  We get unchecked
warnings here.
     * I don't know how to fix them. It may not be possible.
     *
     * @param array array of Comparable objects.
     *
     * @return true if array already in order.
     */
    @SuppressWarnings( { "unchecked" } )
    public static boolean inOrder( Comparable[] array )
        {
        for ( int i = 1; i < array.length; i++ )
            {
            if ( array[ i ].compareTo( array[ i - 1 ] ) < 0 )
                {
                return false;
                }
            }
        return true;
        }

    /**
     * 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;
        }

    /**
     * Is this array already in order according to a given Comparator?
     *
     * @param array      array of Objects.
     * @param comparator Comparator for objects in the array.
     *
     * @return true if array already in order.
     */
    public static <T> boolean inOrder( T[] array, Comparator<? super
T> comparator )
        {
        for ( int i = 1; i < array.length; i++ )
            {
            if ( comparator.compare( array[ i ], array[ i - 1 ] ) < 0
)
                {
                return false;
                }
            }
        return true;
        }

    /**
     * Is this List already in order according to a given Comparator?
     *
     * @param list       List of objects.
     * @param comparator Comparator for objects in the list.
     *
     * @return true if array already in order.
     */
    public static <T> boolean inOrder( List<T> list, Comparator<?
super T> comparator )
        {
        final int length = list.size();
        for ( int i = 1; i < length; i++ )
            {
            if ( comparator.compare( list.get( i ), list.get( i - 1 )
) < 0 )
                {
                return false;
                }
            }
        return true;
        }
    }
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
For me, the appeal of computer programming is that
even though I am quite a klutz,
I can still produce something, in a sense
perfect, because the computer gives me as many
chances as I please to get it right.
 

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#10449

On 12/2/2011 8:58 AM, Patricia Shanahan wrote:
> 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.

Surprised?

:-)

> 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.

Arne

[toc] | [prev] | [next] | [standalone]

#10463

On Fri, 02 Dec 2011 05:58:17 -0800, Patricia Shanahan <pats@acm.org>
wrote, quoted or indirectly quoted someone who said :

>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.

I forgot all about that. I had ArrayList in mind as the only
possibility. Will fix.

ISTR there is a way of knowing if a List can be indexed efficiently.  

Posting code is so often humiliating, but you learn quite a bit in the
process, and end up with higher quality code all over.  We need to
teach people to lose their fear of posting code.  You notice how
terrified newbies are of posting code.  I wonder why...
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
For me, the appeal of computer programming is that
even though I am quite a klutz,
I can still produce something, in a sense
perfect, because the computer gives me as many
chances as I please to get it right.
 

[toc] | [prev] | [next] | [standalone]

#10467

Roedy Green wrote:
> On Fri, 02 Dec 2011 05:58:17 -0800, Patricia Shanahan <pats@acm.org>
> wrote, quoted or indirectly quoted someone who said :
> 
>> 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.
> 
> I forgot all about that. I had ArrayList in mind as the only
> possibility. Will fix.
> 
> ISTR there is a way of knowing if a List can be indexed efficiently.  

Check for instanceof java.util.RandomAccess: "Marker interface used by
List implementations to indicate that they support fast (generally
constant time) random access. The primary purpose of this interface is
to allow generic algorithms to alter their behavior to provide good
performance when applied to either random or sequential access list."

For the inOrder check, I am not sure there would be enough performance
difference to make it worth checking - the general version should be
almost as fast as the indexed version for indexed lists. The sort of
situation in which I might use would be sort. The copy to an array is
unnecessary for RandomAccess.

> 
> Posting code is so often humiliating, but you learn quite a bit in the
> process, and end up with higher quality code all over.  We need to
> teach people to lose their fear of posting code.  You notice how
> terrified newbies are of posting code.  I wonder why...

I know the feeling. We've both been programming long enough to know how
often another programmer will pick up an issue - that is the point of
practices like pair programming and frequent code reviews.

I think newbies take it a bit personally, but sometimes criticism in
this group gets directed too much to the programmer rather than the program.

Patricia

[toc] | [prev] | [next] | [standalone]

#10464

On Fri, 02 Dec 2011 01:43:13 -0800, Roedy Green
<see_website@mindprod.com.invalid> 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?

improved version:

/*
 * [InOrder.java]
 *
 * Summary: Are arrays/collections already in order?.
 *
 * Copyright: (c) 2011 Roedy Green, Canadian Mind Products,
http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any
purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.5+
 *
 * Created with: JetBrains IntelliJ IDEA IDE
http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 2011-11-07 initial version
 *  1.1 2011-12-03 improve efficiency of List version for Linkedlist
or other List that does not index quickly.
 *                 The problem was pointed out by Patricia Shanahan.
 */
package com.mindprod.common15;

import java.util.Comparator;
import java.util.List;

/**
 * Are arrays/collections already in order?.
 * <p/>
 * Generics for these methods were cannibalised from Arrays.sort and
Collections.sort.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.1 2011-12-03 improve efficiency of List version for
Linkedlist or other List that does not index quickly.
 *                         The problem was pointed out by Patricia
Shanahan.
 * @since 2011-11-07
 */
public final class InOrder
    {
    // -------------------------- PUBLIC STATIC METHODS
--------------------------

    /**
     * Is this array already in order according to its Comparable
interface?
     * Generics and arrays don't get along well.  We get unchecked
warnings here.
     * I don't know how to fix them. It may not be possible.
     *
     * @param array array of Comparable objects.
     *
     * @return true if array already in order.
     */
    @SuppressWarnings( { "unchecked" } )
    public static boolean inOrder( Comparable[] array )
        {
        for ( int i = 1; i < array.length; i++ )
            {
            if ( array[ i ].compareTo( array[ i - 1 ] ) < 0 )
                {
                return false;
                }
            }
        return true;
        }

    /**
     * Is this List already in order according to its Comparable
interface?
     *
     * @param list List of Comparable objects, e.g. ArrayList or
LinkedList
     *
     * @return true if array already in order.
     */
    public static <T extends Comparable<? super T>> boolean inOrder(
List<T> list )
        {
        T prev = null;
        for ( T item : list )
            {
            if ( prev != null && item.compareTo( prev ) < 0 )
                {
                return false;
                }
            prev = item;
            }
        return true;
        }

    /**
     * Is this Array already in order according to a given Comparator?
     *
     * @param array      Array of Objects
     * @param comparator Comparator for objects in the array.
     *
     * @return true if Array already in order.
     */
    public static <T> boolean inOrder( T[] array, Comparator<? super
T> comparator )
        {
        for ( int i = 1; i < array.length; i++ )
            {
            if ( comparator.compare( array[ i ], array[ i - 1 ] ) < 0
)
                {
                return false;
                }
            }
        return true;
        }

    /**
     * Is this List already in order according to a given Comparator?
     *
     * @param list       List of objects. , e.g. ArrayList, LinkedList
     * @param comparator Comparator for objects in the list.
     *
     * @return true if array already in order.
     */
    public static <T> boolean inOrder( List<T> list, Comparator<?
super T> comparator )
        {
        T prev = null;
        for ( T item : list )
            {
            if ( prev != null && comparator.compare( item, prev ) < 0
)
                {
                return false;
                }
            }
        return true;
        }
    }
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
For me, the appeal of computer programming is that
even though I am quite a klutz,
I can still produce something, in a sense
perfect, because the computer gives me as many
chances as I please to get it right.
 

[toc] | [prev] | [next] | [standalone]

#10447

On 11/30/2011 10: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?

How would you check a list printed on paper manually?

Implement that in Java!

Arne

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web