what is natural order ?

Discussion in 'Java' started by gk, Nov 3, 2006.

  1. gk

    gk Guest

    TreeSet maintains its elements in their natural order, hence iterating
    will produce "Apple Banana Cricket " instead of "Apple Cricket Banana"


    what is natural order in the above ?

    does it want to say, treeset always sorts automatically by
    ALPHABATICALLY ?
    gk, Nov 3, 2006
    #1
    1. Advertising

  2. Re: what is natural order ?

    gk wrote:
    > TreeSet maintains its elements in their natural order, hence iterating
    > will produce "Apple Banana Cricket " instead of "Apple Cricket Banana"
    >
    >
    > what is natural order in the above ?
    >
    > does it want to say, treeset always sorts automatically by
    > ALPHABATICALLY ?


    Yes, in this case - as it contains strings. String implements
    comparable, which offers natural ordering. In case of strings, the
    natural ordering implies alphabetical sorting. You might want to take a
    look at Comparable Interface for more information on this.

    http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html

    -cheers,
    Manish
    Manish Pandit, Nov 3, 2006
    #2
    1. Advertising

  3. gk

    Eric Sosman Guest

    Re: what is natural order ?

    Manish Pandit wrote:
    > gk wrote:
    >
    >>TreeSet maintains its elements in their natural order, hence iterating
    >>will produce "Apple Banana Cricket " instead of "Apple Cricket Banana"
    >>
    >>
    >>what is natural order in the above ?
    >>
    >>does it want to say, treeset always sorts automatically by
    >>ALPHABATICALLY ?

    >
    >
    > Yes, in this case - as it contains strings. String implements
    > comparable, which offers natural ordering. In case of strings, the
    > natural ordering implies alphabetical sorting. [...]


    Almost. The natural ordering for String objects is their
    lexicographic order according to the Unicode values of their
    individual characters, so (for example) "Aïda" comes after
    "Axolotl". For an even more blatant violation of alphabetical
    order, note that "Zebra" precedes "aardvark".

    Also, "alphabetical order" varies from place to place, even
    if you consider only languages written in Latin alphabets. As
    far as I know (I'm no expert on this, just someone who once got
    a bit of a scolding from a person who was), everybody agrees on
    the ordering of the twenty-six unaccented letters, but the
    treatment of accented letters is subject to national and linguistic
    variation.

    See also java.text.Collator and allied classes.

    --
    Eric Sosman
    lid
    Eric Sosman, Nov 3, 2006
    #3
  4. gk

    Oliver Wong Guest

    "gk" <> wrote in message
    news:...
    > TreeSet maintains its elements in their natural order, hence iterating
    > will produce "Apple Banana Cricket " instead of "Apple Cricket Banana"
    >
    >
    > what is natural order in the above ?


    It might be clearer to talk about what is NOT natural order.

    In some cases, you can provide a sorting algorithm with a comparator.
    The comparator defines an ordering. For example, you might create a
    Comparator<Integer> which orders all odd integers before all even integers,
    so that the the order of {1,2,3,4,5} would be: (1,3,5,2,4). In other words,
    by using a Comparator, you can invent any kind of ordering you want.

    When you DON'T use a comparator, it implies you want the natural
    ordering of the elements, instead of your custom ordering.

    - Oliver
    Oliver Wong, Nov 3, 2006
    #4
  5. gk

    Mark Rafn Guest

    gk <> wrote:
    >TreeSet maintains its elements in their natural order, hence iterating
    >will produce "Apple Banana Cricket " instead of "Apple Cricket Banana"


    Natural order is the ordering provided by the compareTo() methods
    of the elements in the collection (all of which must implement Comparable).

    For String, this is asciibetical (more specifically, compared according to the
    unicode value of each character).

    >what is natural order in the above ?


    "Apple Banana Cricket".

    >does it want to say, treeset always sorts automatically by
    >ALPHABATICALLY ?


    No. TreeSet can store Comparable objects other than String. Each class
    defines it's own natural ordering in the compareTo() method. And further, no.
    String's natural ordering is not alphabetical, it's based on character values,
    meaning that if you have mixed upper and lowercase, you'd get "Banana apple
    cricket".

    If you want some other sort order, you need to instantiate the TreeMap with a
    Comparator that does what you want. The String.CASE_INSENSITIVE_ORDER
    Comparator is handy :)
    --
    Mark Rafn <http://www.dagon.net/>
    Mark Rafn, Nov 3, 2006
    #5
  6. gk

    Chris Uppal Guest

    Re: what is natural order ?

    Eric Sosman wrote:

    > Almost. The natural ordering for String objects is their
    > lexicographic order according to the Unicode values of their
    > individual characters, so (for example) "Aïda" comes after
    > "Axolotl". For an even more blatant violation of alphabetical
    > order, note that "Zebra" precedes "aardvark".


    All true, and undoubtedly all that the OP needs to know.

    But it may be (midly) interesting to note that -- although String /claim/ to
    sort lexicographically according to the Unicode code points -- they /actually/
    sort by the UTF-16 values. And that doesn't produce the same sort order for
    Unicode characters outside the 16-bit range.


    > Also, "alphabetical order" varies from place to place, even
    > if you consider only languages written in Latin alphabets. As
    > far as I know (I'm no expert on this, just someone who once got
    > a bit of a scolding from a person who was), everybody agrees on
    > the ordering of the twenty-six unaccented letters,


    For interest: there are exceptions. Or at least, there are according to the
    Unicode people. Spanish (they say) traditionally considers ll to be a digraph
    falling between l and m.

    -- chris
    Chris Uppal, Nov 3, 2006
    #6
  7. gk

    Tom Forsmo Guest

    Re: what is natural order ?

    Eric Sosman wrote:
    > Almost. The natural ordering for String objects is their
    > lexicographic order according to the Unicode values of their
    > individual characters, so (for example) "Aïda" comes after
    > "Axolotl". For an even more blatant violation of alphabetical
    > order, note that "Zebra" precedes "aardvark".


    I have allways though of natural ordering as the way we humans would
    order strings, e.g.

    string1
    string2
    string...
    string9
    string10
    string11
    ..
    string20
    string21

    and other similar sort order, instead of the typical

    string1
    string10
    string11
    ...
    string2
    string20
    string21

    etc and other similar types of sorting problems

    Is there a name for the "human sort order"? and does there exists an
    implementation of it. Perhaps a name could be "semantic sort order".
    I realise that it would require quite a big implementation with many
    special case rules that in no way can be generalised and made into a
    single algorithm like lexical or natural orders.

    tom
    Tom Forsmo, Nov 3, 2006
    #7
  8. gk

    Oliver Wong Guest

    Re: what is natural order ?

    "Tom Forsmo" <> wrote in message
    news:...
    >
    > I have allways though of natural ordering as the way we humans would order
    > strings, e.g.
    >
    > string1
    > string2
    > string...
    > string9
    > string10
    > string11
    > ..
    > string20
    > string21
    >
    > Is there a name for the "human sort order"? and does there exists an
    > implementation of it. Perhaps a name could be "semantic sort order".
    > I realise that it would require quite a big implementation with many
    > special case rules that in no way can be generalised and made into a
    > single algorithm like lexical or natural orders.


    There may be a name for the particular sorting you've shown above
    (though the sort order is ambiguous, because there are some corner cases you
    haven't demonstrated in that example), but I doubt that there exists a
    "human sort order", as different humans are likely to sort things in
    different orders.

    See Chris' post about how a Spanish speaking person would likely sort
    strings in different order than an English speaking person, for example.

    - Oliver
    Oliver Wong, Nov 3, 2006
    #8
  9. gk

    Eric Sosman Guest

    Re: what is natural order ?

    Tom Forsmo wrote On 11/03/06 15:59,:
    > Eric Sosman wrote:
    >
    >> Almost. The natural ordering for String objects is their
    >>lexicographic order according to the Unicode values of their
    >>individual characters, so (for example) "Aïda" comes after
    >>"Axolotl". For an even more blatant violation of alphabetical
    >>order, note that "Zebra" precedes "aardvark".

    >
    >
    > I have allways though of natural ordering as the way we humans would
    > order strings, e.g.
    >
    > string1
    > string2
    > string...
    > string9
    > string10
    > string11
    > ..
    > string20
    > string21
    >
    > and other similar sort order, instead of the typical
    >
    > string1
    > string10
    > string11
    > ...
    > string2
    > string20
    > string21
    >
    > etc and other similar types of sorting problems
    >
    > Is there a name for the "human sort order"? and does there exists an
    > implementation of it. Perhaps a name could be "semantic sort order".
    > I realise that it would require quite a big implementation with many
    > special case rules that in no way can be generalised and made into a
    > single algorithm like lexical or natural orders.


    You might be interested in

    http://sourcefrog.net/projects/natsort/

    (Yes, that's "frog" as in "Kermit.")

    --
    Eric Sosman, Nov 3, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Simone Winkler

    conversion: natural -> time

    Simone Winkler, Apr 1, 2004, in forum: VHDL
    Replies:
    1
    Views:
    1,809
    Jim Lewis
    Apr 1, 2004
  2. Paul
    Replies:
    1
    Views:
    13,153
    Rogan Dawes
    Sep 14, 2004
  3. Paul

    Natural sort order

    Paul, Sep 14, 2004, in forum: Java
    Replies:
    1
    Views:
    592
    Stefan Schulz
    Sep 14, 2004
  4. Alan Davies

    Natural order sort

    Alan Davies, Sep 11, 2003, in forum: Ruby
    Replies:
    2
    Views:
    103
    Alan Davies
    Sep 15, 2003
  5. filippo
    Replies:
    13
    Views:
    189
    John Bokma
    Jun 16, 2006
Loading...

Share This Page