Arrays class sort method

Discussion in 'Java' started by fox_fire, Apr 25, 2004.

  1. fox_fire

    fox_fire Guest

    The API documentation for the Arrays class sort(Object[] a,
    Comparator c) method says:

    "The sorting algorithm is a modified mergesort (in which the merge is
    omitted if the highest element in the low sublist is less than the lowest
    element in the high sublist). "



    I believe this is causing a problem with my program. It uses this method
    to quickly sort a rather LARGE array of words (somewhere around 20,000)
    into an order specified by a comparator. I use a Comparator because I sort
    the words based on only one of the characters (by position 2, for
    instance), not lexicographically.

    The API says it won't merge the last time "if the highest element in the
    low sublist is less than the lowest element in the high sublist." Well, I
    keep getting output that is separated into 2 large, sorted groups of
    words. It didn't seem to perform the last merge because it fit the
    criteria above. I don't understand _WHY_ the sort method makes this
    exception. The thing isn't sorted completely if you don't perform the last
    merge, even if the bottom and top elements of the two lists are in order.
    fox_fire, Apr 25, 2004
    #1
    1. Advertising

  2. fox_fire

    Roedy Green Guest

    On Sun, 25 Apr 2004 18:02:36 -0400, "fox_fire" <>
    wrote or quoted :

    >I believe this is causing a problem with my program. It uses this method
    >to quickly sort a rather LARGE array of words (somewhere around 20,000)
    >into an order specified by a comparator. I use a Comparator because I sort
    >the words based on only one of the characters (by position 2, for
    >instance), not lexicographically.


    I am quite sure that is NOT your problem. I have never known the sort
    to fail and I use it hundreds of times a day. That paragraph you read
    is just a handwaving overview of the tournament algorithm.

    Your problem is most likely that your Comparator is screwed up.

    Please post your Comparator.

    You can try out your Comparator on many other sorts I have provided.
    This should prove to you the problem lies in your Comparator.

    See http://mindprod.com/jgloss/sort.html

    The most common error is using == to compare non-interned Strings.

    see http://mindprod.com/jgloss/comparator.htm

    By the way, your problem is exactly what RadixSort excels at. See
    http://mindprod.com/jgloss/radixsort.html

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 25, 2004
    #2
    1. Advertising

  3. fox_fire

    Chris Uppal Guest

    fox_fire wrote:

    > "The sorting algorithm is a modified mergesort (in which the merge is
    > omitted if the highest element in the low sublist is less than the lowest
    > element in the high sublist). "


    > I believe this is causing a problem with my program.


    Remember that mergesort works by sorting the sub-lists first, /then/ merging
    them. So the sublists are always sorted, and the test that the
    documentation mentions is only a simple optimisation.

    -- chris
    Chris Uppal, Apr 26, 2004
    #3
  4. fox_fire

    fox_fire Guest

    This is my comparator

    public class StringComparator implements Comparator
    {
    private int position;

    public StringComparator(int aPosition)
    {
    position = aPosition;
    }

    public int compare(Object o1, Object o2)
    {
    if (o1 == null || o2 == null)
    return 0;

    String s1 = (String) o1;
    String s2 = (String) o2;

    if ((position + 1) > s1.length())
    s1 = fixLength(s1);

    if ((position + 1) > s2.length())
    s1 = fixLength(s2);


    Character c1 = new Character(s1.charAt(position));
    Character c2 = new Character(s2.charAt(position));

    return c1.compareTo(c2);
    }

    public boolean equals(Object other)
    {
    Comparator otherComp = (Comparator) other;
    return (otherComp.compare("Abc", "Def") == compare("Abc", "Def"));
    }

    public String fixLength(String str)
    {
    int spaces = (position + 1) - str.length();

    for (int i = 0; i < spaces; i++)
    str += " ";

    return str;
    }
    }
    fox_fire, Apr 26, 2004
    #4
  5. fox_fire

    Rogan Dawes Guest

    fox_fire wrote:

    > This is my comparator
    >
    > public class StringComparator implements Comparator
    > {
    > private int position;
    >
    > public StringComparator(int aPosition)
    > {
    > position = aPosition;
    > }
    >
    > public int compare(Object o1, Object o2)
    > {
    > if (o1 == null || o2 == null)
    > return 0;


    Well, this might be one problem: You are saying that o1 and o2 are equal
    if EITHER of them are null, not if BOTH are null.
    >
    > String s1 = (String) o1;
    > String s2 = (String) o2;
    >
    > if ((position + 1) > s1.length())
    > s1 = fixLength(s1);
    >
    > if ((position + 1) > s2.length())
    > s1 = fixLength(s2);


    I would look very carefully at your fixLength function. I'm not entirely
    sure what you are trying to achieve with it.
    >
    >
    > Character c1 = new Character(s1.charAt(position));
    > Character c2 = new Character(s2.charAt(position));
    >
    > return c1.compareTo(c2);
    > }
    >
    > public boolean equals(Object other)
    > {
    > Comparator otherComp = (Comparator) other;
    > return (otherComp.compare("Abc", "Def") == compare("Abc", "Def"));
    > }


    And this is an interesting definition of "equals"! ;-)
    >
    > public String fixLength(String str)
    > {
    > int spaces = (position + 1) - str.length();
    >
    > for (int i = 0; i < spaces; i++)
    > str += " ";
    >
    > return str;
    > }
    > }
    >
    >



    --
    Rogan Dawes
    nntp_AT_dawes*DOT*za-DOT-net
    Rogan Dawes, Apr 26, 2004
    #5
  6. fox_fire

    Roedy Green Guest

    On Mon, 26 Apr 2004 11:35:40 -0400, "fox_fire" <>
    wrote or quoted :

    > s1 = fixLength(s1);
    >
    > if ((position + 1) > s2.length())
    > s1 = fixLength(s2);
    >


    oops
    s2 = fixLength(s2);

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 26, 2004
    #6
  7. fox_fire

    Roedy Green Guest

    On Mon, 26 Apr 2004 11:35:40 -0400, "fox_fire" <>
    wrote or quoted :

    >public boolean equals(Object other)
    > {
    > Comparator otherComp = (Comparator) other;
    > return (otherComp.compare("Abc", "Def") == compare("Abc", "Def"));
    > }


    leave this out. equals is for comparing two Comparators. The default
    is fine. See http://mindprod.com/jgloss/Comparator.html

    Please digest the advice given before asking for more.


    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 26, 2004
    #7
  8. fox_fire

    Roedy Green Guest

    On Mon, 26 Apr 2004 11:35:40 -0400, "fox_fire" <>
    wrote or quoted :

    >public String fixLength(String str)
    > {
    > int spaces = (position + 1) - str.length();
    >
    > for (int i = 0; i < spaces; i++)
    > str += " ";
    >
    > return str;
    > }


    This is a slow way to append some spaces.

    Here is another.

    public String fixLength(String str)
    {
    int spaces = (position + 1) - str.length();

    return str + blanks.substring( 0, spaces );
    }

    private static final String blanks = " ";

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 26, 2004
    #8
  9. fox_fire

    Roedy Green Guest

    On Mon, 26 Apr 2004 11:35:40 -0400, "fox_fire" <>
    wrote or quoted :

    >Character c1 = new Character(s1.charAt(position));
    > Character c2 = new Character(s2.charAt(position));
    >
    > return c1.compareTo(c2);


    You can do this with char instead of Character making it much much
    faster. Comparators are called millions of times, so they are usually
    bottlenecks.


    return s1.charAt( position ) - s1.charAt( position );

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 26, 2004
    #9
  10. fox_fire

    Roedy Green Guest

    On Mon, 26 Apr 2004 11:35:40 -0400, "fox_fire" <>
    wrote or quoted :

    >if ((position + 1) > s1.length())
    > s1 = fixLength(s1);
    >
    > if ((position + 1) > s2.length())
    > s1 = fixLength(s2);
    >
    >
    > Character c1 = new Character(s1.charAt(position));
    > Character c2 = new Character(s2.charAt(position));


    instead of modifying the String to append spaces try extracting the
    characters this way:

    char c1 = ((position) >= s1.length()) ? ' ':s1.charAt(position);
    char c2 = ((position) >= s2.length()) ? ' ':s2.charAt(position);
    return c1 - c2;


    This code is very quick.

    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 26, 2004
    #10
  11. fox_fire

    fox_fire Guest

    I tried everything you said but it doesn't make the sorting work any
    better. I guess it makes it faster but the order still gets messed up. I
    also used other sorting algorithms (including a different Merge Sort
    implementation) and the same results were obtained. I hvae already tested
    my comparator and i can't find a test case in which it doesn't work.
    fox_fire, Apr 27, 2004
    #11
  12. fox_fire

    Roedy Green Guest

    On Mon, 26 Apr 2004 20:59:43 -0400, "fox_fire" <>
    wrote or quoted :

    >I tried everything you said but it doesn't make the sorting work any
    >better. I guess it makes it faster but the order still gets messed up. I
    >also used other sorting algorithms (including a different Merge Sort
    >implementation) and the same results were obtained. I hvae already tested
    >my comparator and i can't find a test case in which it doesn't work.


    your comparator had half a dozen problems. I think it improbable you
    would have fixed them all in one go without introducing at least one
    new bug.

    Let's have a look at your new improved comparator.


    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Apr 27, 2004
    #12
  13. "fox_fire" <> wrote in
    news::

    > This is my comparator
    >
    > public class StringComparator implements Comparator
    > {
    > private int position;
    >
    > public StringComparator(int aPosition)
    > {
    > position = aPosition;
    > }
    >
    > public int compare(Object o1, Object o2)
    > {
    > if (o1 == null || o2 == null)
    > return 0;
    >
    > String s1 = (String) o1;
    > String s2 = (String) o2;
    >
    > if ((position + 1) > s1.length())
    > s1 = fixLength(s1);
    >
    > if ((position + 1) > s2.length())
    > s1 = fixLength(s2);


    I believe that should be: s2 = fix...



    --
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GCS d++ s+:- a+ C+ UL++++ P+ L+ E- W+ N++ o- K++ w+ O+ M !V PS+ PE Y+ PGP t+ !5 X- R- tv--- b++
    DI++ D+ G++ e++ h---- r+++ y+++
    ------END GEEK CODE BLOCK------
    Tris Orendorff, Apr 29, 2004
    #13
    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. Philipp
    Replies:
    21
    Views:
    1,111
    Philipp
    Jan 20, 2009
  2. Navin
    Replies:
    1
    Views:
    675
    Ken Schaefer
    Sep 9, 2003
  3. Replies:
    9
    Views:
    403
    whisperjim
    Nov 27, 2008
  4. Replies:
    0
    Views:
    253
  5. Domenico Discepola

    multi-field array sort using Sort::Fields method

    Domenico Discepola, Apr 27, 2004, in forum: Perl Misc
    Replies:
    6
    Views:
    293
    Uri Guttman
    Apr 28, 2004
Loading...

Share This Page