Sort algorithm problems on java comparable

Question

I want to do a specific sort. I am using java's comparable interface which means the return of my compare method must return -1 +1 or 0 depending on the equality of the two compared, then I am sorting using Collections. My trouble comes from how I wish to compare.

I have a key that is made up of either of the following

[keyName]  
[siteName].[keyName]  
[siteName].[pageName].[keyName]

so as an example "mysite.alampshade.color"

the tricky part is the sites must be sorted first, followed by keyname, followed by pageName. but firstly by the keynames, then site name, in the order of the number of sections to the property. Sorry. its a little complicated, an example may help. here is the order they must be:

alpha  
beta  
charlie  
sitea.alpha  
sitea.charlie  
sitea.pagea.beta  
sitea.pageb.beta  
sitea.pagea.charlie  
siteb.alpha  
siteb.delta  
siteb.pagef.alpha  
siteb.pageb.echo  
siteb.pageb.golf  
siteb.pagea.hotel  
siteb.pageb.hotel  
siteb.pagec.hotel

I have tried many different ways and have thrown away code a few times but still cant get it perfect. some pseudocode would be of great help if not some java.

EDIT: to add another possibly simplier to understand example the following is sorted how I need it

a  
b  
c  
z  
a.b  
a.c  
a.d  
a.z  
a.b.a  
a.c.a  
a.b.b  
a.b.c  
a.c.c  
a.a.d  
b.a  
b.b  
b.z  
b.a.a  
b.b.a  
b.a.b  
c.c.f

You say "firstly the order of the number of sections" but you list sitea.pagea.charlie before siteb.alpha . Which is it? — Will
– Will, Commented Mar 21, 2013 at 14:14
@MarkW I've updated my answer, it was incomplete and Roger pointed it out. Now it should be good. I've also commented my code so that it's more readable. — LaGrandMere
– LaGrandMere, Commented Mar 21, 2013 at 15:31

pedromarce · Accepted Answer · 2013-03-21 22:15:52Z

2

Another option, making it recursive you avoid the problem if there is ever more entries.

import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List;

public class SortTest {
    public static void main(String[] args) {
        String[] test = new String[]{
            "a",
            "b",
            "b.a",
            "b.a.a",
            "a.a.a",
            "a.b.a",
            "a.a",
            "a.b",
            "b.a.b",
            "b.b.a"
        };

        Arrays.sort(test, new Comparator<String>() {

        int compareComplexList(List<String> a, List<String> b, List<int[]> positions, int order ) {

          int minimum = a.size() < b.size() ? a.size() - 1 : b.size() - 1;   

          if (a.get(positions.get(minimum)[order]).compareTo(b.get(positions.get(minimum)[order])) != 0)
                return a.get(positions.get(minimum)[order]).compareTo(b.get(positions.get(minimum)[order]));
          else if (order < minimum - 1) return compareComplexList(a,b, positions, ++order);
          else return Double.compare(a.size(),b.size());
        }

        public int compare(String a, String b) {
          List<String> partsA = Arrays.asList(a.split("\\."));
          List<String> partsB = Arrays.asList(b.split("\\."));
          List<int[]>  orders = new ArrayList<int[]>();

          orders.add(new int[] {0});
          orders.add(new int[] {0,1});
          orders.add(new int[] {0,2,1});

          return compareComplexList(partsA, partsB, orders,0);
        }
        });
        System.out.println("Sorted: "+Arrays.toString(test));
    }

}

edited Mar 21, 2013 at 22:15

answered Mar 21, 2013 at 16:44

pedromarce

5,6692 gold badges30 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

pedromarce Over a year ago

I am using java 6, on java 7 you should be ok to go with Integer.compare which would be much better.

Mark W Over a year ago

Thanks. this is nicely done, but does not quite sort in order I want. This sorts number of parts first, followed by part 1 followed by part 2 followed by part 3. I need 2 and 3 swapped, and then prioritise part1 sort order over number of parts sort order

Mark W Over a year ago

its a pig of an algorithm. I have tried many times, even from fresh a few times

pedromarce Over a year ago

Another try, you have to pass fields to be considered, and probably catch exceptions if there are more entries than expected, but should be good... hopefully :)

Joey · Accepted Answer · 2013-03-22 08:31:43Z

2

Should be good now.

public int compare(String a, String b) {
String[] partsA = a.split("\\.");
String[] partsB = b.split("\\.");

// If first term is different, we exit.
if (partsA[0].compareTo(partsB[0]) != 0) return partsA[0].compareTo(partsB[0]);

// Else, first term is identical.
else {
    // Same number of parts
    if (partsA.length == partsB.length) {
        // 2 parts, we compare the 2nd part.
        if (partsA.length == 2) {
            return partsA[1].compareTo(partsB[1]);
        // 3 parts, we compare the 3rd part first, then the 2nd part        
        } else {
            if (partsA[2].compareTo(partsB[2]) != 0) return partsA[2].compareTo(partsB[2]);
            return partsA[1].compareTo(partsB[1]);
        }

    // Different number of parts
    } else {
        // If A has only 1 part, it's first
        if (partsA.length == 1) return -1;
        // If B has only 1 part, it's first
        if (partsB.length == 1) return 1;

        // Case 2 vs 3 parts, we compare the 3rd part with the 2nd part of the other. If it's equal, the shorter is first.
        if (partsA.length == 3) {
            if (partsA[2].compareTo(partsB[1]) != 0) return partsA[2].compareTo(partsB[1]);
            else return 1;
        } else {
            if (partsA[1].compareTo(partsB[2]) != 0) return partsA[1].compareTo(partsB[2]);
            else return -1;
        }           
    }
}
}

edited Mar 22, 2013 at 8:31

Joey

357k88 gold badges704 silver badges699 bronze badges

answered Mar 21, 2013 at 14:15

LaGrandMere

10.4k1 gold badge36 silver badges42 bronze badges

10 Comments

Vincent van der Weele Over a year ago

This seems to be right now. I couldn't get it to work with a loop, so this doesn't look nice, but there is little to do about that...

Kent Over a year ago

what is String.compare(foo, bar)?

Roger Lindsjö Over a year ago

Doesn't the first if return the wrong answer comparing "sitea.pagea.keya" with "siteb.keya"?

LaGrandMere Over a year ago

@RogerLindsjö you're right ! There's a mistake in it. I'm correcting it rigth now. Thanks :)

Mark W Over a year ago

there is no String.compare(String String) method. Is that 1.7?

|

OldCurmudgeon · Accepted Answer · 2013-03-21 17:23:42Z

1

My other answer started getting too gnarly. Here's a better, more natural solution:

public class StrangeComparator {
  private static class Entry implements Comparable<Entry> {
    // What to split with.
    static final String dot = Pattern.quote(".");
    // The parts.
    final String key;
    final String page;
    final String site;

    public Entry(String s) {
      String [] parts = s.split(dot);
      switch (parts.length) {
        case 1:
          key = parts[0];
          page = "";
          site = "";
          break;

        case 2:
          key = parts[1];
          page = "";
          site = parts[0];
          break;

        case 3:
          key = parts[2];
          page = parts[1];
          site = parts[0];
          break;

        default:
          throw new IllegalArgumentException("There must be at least one part to an entry.");
      }
    }

    @Override
    public int compareTo(Entry t) {
      int diff = site.compareTo(t.site);
      if ( diff == 0 ) {
        diff = page.compareTo(t.page);
      }
      if ( diff == 0 ) {
        diff = key.compareTo(t.key);
      }
      return diff;
    }

    @Override
    public String toString () {
      return (site.length() > 0 ? site + "." : "")
              + (page.length() > 0 ? page + "." : "")
              + key;
    }
  }

  public void test() {
    String[] test = new String[]{
      "alpha",
      "beta",
      "charlie",
      "zeta", // Added to demonstrate correctness.
      "sitea.alpha",
      "sitea.charlie",
      "sitea.pagea.beta",
      "sitea.pageb.beta",
      "sitea.pagea.charlie",
      "siteb.alpha",
      "siteb.delta",
      "siteb.pagef.alpha",
      "siteb.pageb.echo",
      "siteb.pageb.golf",
      "siteb.pagea.hotel",
      "siteb.pageb.hotel",
      "siteb.pagec.hotel"
    };
    Arrays.sort(test);
    System.out.println("Normal sort: " + Separator.separate("\n", "\n", test));
    Entry[] entries = new Entry[test.length];
    for ( int i = 0; i < test.length; i++ ) {
      entries[i] = new Entry(test[i]);
    }
    Arrays.sort(entries);
    System.out.println("Special sort: " + Separator.separate("\n", "\n", entries));
  }

  public static void main(String args[]) {
    new StrangeComparator().test();
  }
}

Output order is:

alpha
beta
charlie
zeta
sitea.alpha
sitea.charlie
sitea.pagea.beta
sitea.pagea.charlie
sitea.pageb.beta
siteb.alpha
siteb.delta
siteb.pagea.hotel
siteb.pageb.echo
siteb.pageb.golf
siteb.pageb.hotel
siteb.pagec.hotel
siteb.pagef.alpha

Which kinda does what you say but doesn't match your example.

edited Mar 21, 2013 at 17:23

answered Mar 21, 2013 at 17:07

OldCurmudgeon

66k18 gold badges126 silver badges220 bronze badges

4 Comments

Mark W Over a year ago

thats almost it. I just need sitea.charlie after sitea.alpha And also siteb.delta after siteb.alpha

OldCurmudgeon Over a year ago

@MarkW - How does that look now? compareTo now compares in order site,page,key, not as you stated.

OldCurmudgeon Over a year ago

@MarkW - I've checked this with your new test data and it is correct with that.

Mark W Over a year ago

a few compile errors in 1.6. What's "Seperator"? - looks like it may work. Your sorting the array in a loop first by size. @pedromarce managed it inside the comparator class which I'd prefer. So I have awarded answer to him. But I like your thinking +1

OldCurmudgeon · Accepted Answer · 2013-03-21 15:03:45Z

0

Here's an alternative - if a component is found to contain less that 3 parts then parts are added at the start to take up the slack. It then uses a sort order array to define which columns should be compared next:

  public void test() {
    String[] test = new String[]{
      "alpha",
      "beta",
      "charlie",
      "zeta", // Added to demonstrate correctness.
      "sitea.alpha",
      "sitea.charlie",
      "sitea.pagea.beta",
      "sitea.pageb.beta",
      "sitea.pagea.charlie",
      "siteb.alpha",
      "siteb.delta",
      "siteb.pagef.alpha",
      "siteb.pageb.echo",
      "siteb.pageb.golf",
      "siteb.pagea.hotel",
      "siteb.pageb.hotel",
      "siteb.pagec.hotel"
    };
    Arrays.sort(test);
    System.out.println("Normal sort: "+Arrays.toString(test));
    Arrays.sort(test, new Comparator<String>() {
      // How many columns to pad to.
      final int padTo = 3;
      // What to pad with.
      final String padWith = "";
      // What order to compare the resultant columns in.
      final int[] order = {0, 2, 1};

      @Override
      public int compare(String s1, String s2) {
        String[] s1parts = padArray(s1.split(Pattern.quote(".")), padTo, padWith);
        String[] s2parts = padArray(s2.split(Pattern.quote(".")), padTo, padWith);
        int diff = 0;
        for ( int i = 0; diff == 0 && i < order.length; i++ ) {
          diff = s1parts[order[i]].compareTo(s2parts[order[i]]);
        }
        return diff;
      }

      String [] padArray(String[] array, int padTo, String padWith) {
        String [] padded = new String[padTo];
        for ( int i = 0; i < padded.length; i++ ) {
          padded[padded.length - i - 1] = i < array.length ? array[i]: padWith;
        }
        return padded;
      }
    });
    System.out.println("Special sort: "+Arrays.toString(test));
  }

prints (more or less):

Normal sort: [alpha,
 beta,
 charlie,
 sitea.alpha,
 sitea.charlie,
 sitea.pagea.beta,
 sitea.pagea.charlie,
 sitea.pageb.beta,
 siteb.alpha,
 siteb.delta,
 siteb.pagea.hotel,
 siteb.pageb.echo,
 siteb.pageb.golf,
 siteb.pageb.hotel,
 siteb.pagec.hotel,
 siteb.pagef.alpha,
 zeta]
Special sort: [alpha,
 beta,
 charlie,
 sitea.alpha,
 sitea.charlie,
 siteb.alpha,
 siteb.delta,
 zeta,
 siteb.pagef.alpha,
 sitea.pagea.beta,
 sitea.pageb.beta,
 sitea.pagea.charlie,
 siteb.pageb.echo,
 siteb.pageb.golf,
 siteb.pagea.hotel,
 siteb.pageb.hotel,
 siteb.pagec.hotel]

There does seem to be some ambiguity in your requirements but this code is structured so you can, with trivial tweaks, achieve most interpretations of your comparison quite simply.

edited Mar 21, 2013 at 15:03

answered Mar 21, 2013 at 14:39

OldCurmudgeon

66k18 gold badges126 silver badges220 bronze badges

3 Comments

Kent Over a year ago

did you compare your output to OP's example output?

OldCurmudgeon Over a year ago

Yes - thus my "ambiguity" comment and the addition of the "zeta" value to demonstrate the ambiguities. Ahh!! I see OP wants site,key,page - I have given key, page, site. I will tweak.

Mark W Over a year ago

yeah sorry guys it is a little confusing. if you have any questions I'll be happy to try to clear it up.

Collectives™ on Stack Overflow

Sort algorithm problems on java comparable

4 Answers 4

4 Comments

10 Comments

4 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

10 Comments

4 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related