Arrays class sort method

[fox_fire]

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.

 

[Roedy Green]

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

 

[Chris Uppal]

"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

 

[fox_fire]

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

 

[Rogan Dawes]

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"! ;-)

 

[Roedy Green]

s1 = fixLength(s1);

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

oops
s2 = fixLength(s2);

 

[Roedy Green]

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.

 

[Roedy Green]

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 = " ";

 

[Roedy Green]

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 );

 

[Roedy Green]

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.

 

[fox_fire]

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.

 

[Roedy Green]

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.

 

[Tris Orendorff]

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