Complex sorting of Java ArrayList

Question

I have the following strings stored in trendList variable. I do a sort, but the data doesn't come out sorted properly.

i.e. ACLK_SCRN_200MHZ_DATAB_S0_P1:8 should come before ACLK_SCRN_200MHZ_DATAB_S0_P10:8

since 1 < 10, and so on with the rest of the strings.

Question: How do I do this alphanumeric sorting to get the correct order?

Do I have to make my own function? What would that look like?

List<String> trendList = new ArrayList<String>(80000);

Collections.sort(trendList);

ACLK_SCRN_200MHZ_DATAB_S0_P0:8
ACLK_SCRN_200MHZ_DATAB_S0_P10:8
ACLK_SCRN_200MHZ_DATAB_S0_P11:8
ACLK_SCRN_200MHZ_DATAB_S0_P12:8
ACLK_SCRN_200MHZ_DATAB_S0_P13:8
ACLK_SCRN_200MHZ_DATAB_S0_P14:8
ACLK_SCRN_200MHZ_DATAB_S0_P15:8
ACLK_SCRN_200MHZ_DATAB_S0_P1:8
ACLK_SCRN_200MHZ_DATAB_S0_P2:8
ACLK_SCRN_200MHZ_DATAB_S0_P3:8
ACLK_SCRN_200MHZ_DATAB_S0_P4:8
ACLK_SCRN_200MHZ_DATAB_S0_P5:8
ACLK_SCRN_200MHZ_DATAB_S0_P6:8
ACLK_SCRN_200MHZ_DATAB_S0_P7:8
ACLK_SCRN_200MHZ_DATAB_S0_P8:8
ACLK_SCRN_200MHZ_DATAB_S0_P9:8
ACLK_SCRN_200MHZ_DATAB_S1_P0:8
ACLK_SCRN_200MHZ_DATAB_S1_P10:8
ACLK_SCRN_200MHZ_DATAB_S1_P11:8
ACLK_SCRN_200MHZ_DATAB_S1_P12:8
ACLK_SCRN_200MHZ_DATAB_S1_P13:8
ACLK_SCRN_200MHZ_DATAB_S1_P14:8
ACLK_SCRN_200MHZ_DATAB_S1_P15:8
ACLK_SCRN_200MHZ_DATAB_S1_P1:8
ACLK_SCRN_200MHZ_DATAB_S1_P2:8
ACLK_SCRN_200MHZ_DATAB_S1_P3:8
ACLK_SCRN_200MHZ_DATAB_S1_P4:8
ACLK_SCRN_200MHZ_DATAB_S1_P5:8
MLC_C_SAMPLE
MLC_SAMPLE
SWR
TOUCHDOWN
TEST_REV

You could write a regex and use a custom string comparator on the numbers. However, it would make more sense to implement an object that parses these strings and implement a custom `compareTo()` method or `Comparator` on the objects. — Andrew Mao, Feb 28 '13 at 19:43

score 1 · Answer 1 · answered Feb 28 '13 at 19:42

You're getting that result because it's comparing the strings using just the default String.compareTo, which uses the raw character codes. ':' appears after '0'-'9' so it collates afterward.

You'll need to supply your own Comparator and call

Collections.sort(trendList, new CustomComparator());

Alex · Answer 2 · 2013-03-01T05:59:20.183

You can do like this with your own Comparator:

class TrendListComparator implements Comparator<String> {
     // retrieve the P and S
     final Pattern p = Pattern.compile(".*_S(\\d+)_P(\\d+).*");
     public int compare(String str1, String str2) {
         Matcher m1 = p.matcher(str1);
         Matcher m2 = p.matcher(str2);
         if (m1.matches() && m2.matches()) {
             Integer s1 = Integer.valueOf(m.group(1));
             Integer p1 = Integer.valueOf(m.group(2));
             Integer s2 = Integer.valueOf(m.group(1));
             Integer p2 = Integer.valueOf(m.group(2));
             // compare
             return s1.equals(s2) ? p1.compareTo(p2) : s1.compareTo(s2);
         } else {
             return str1.compareTo(str2); // standard sort if no P and S
         }
     }
}

Collections.sort(trendList, new TrendListComparator());

You can see a running example here: http://ideone.com/AleOEy

You can even do it with only one Matcher and reuse it all along during the same sort:

class TrendListComparator implements Comparator<String> {
     // retrieve the P and S
     final Matcher m = Pattern.compile(".*_S(\\d+)_P(\\d+).*_S(\\d+)_P(\\d+).*").matcher("");
     public int compare(String str1, String str2) {
         if (m.reset(str1 + str2).matches()) {
             Integer s1 = Integer.valueOf(m.group(1));
             Integer p1 = Integer.valueOf(m.group(2));
             Integer s2 = Integer.valueOf(m.group(3));
             Integer p2 = Integer.valueOf(m.group(4));
             // compare
             return s1.equals(s2) ? p1.compareTo(p2) : s1.compareTo(s2);
         } else {
             return str1.compareTo(str2); // standard sort if no P and S
         }
     }
}

See: http://ideone.com/EsfFPj

Hey, I really like this code but how would error checking occur? Like checking to see if there is an integer in the string? I keep getting "errored" out! — Mark Kennedy, Feb 28 '13 at 20:17
@user1022944 You can see a running example here: http://ideone.com/AleOEy — Alex, Mar 01 '13 at 04:48

rgettman · Answer 3 · 2013-02-28T19:51:16.493

You can create your own class that implements the Comparator<String> interface. In the compare method, you will need to parse your string and extract the numbers from the relevant parts of the string that need to be sorted by numbers. The method should return a number less than 0 if s1 is less than s2, 0 if s1 is equal to s2, and greater than 0 if s1 is greater than s2.

public class MyTrendListComparator implements Comparator<String>
{
    public int compare(String s1, String s2)
    {
        // Parse and compare here.
    }
}

Then pass an instance of your comparator to Collections.sort:

Collections.sort(trendList, new MyTrendListComparator());

score 0 · Answer 4 · answered Feb 28 '13 at 19:45

You can pass a custom comparator in to the Collections.sort() function:

Collections.sort(trendList, new Comparator<String>() {

    @Override
    public int compare(String s1, String s2) {
        int sValue1 = s1.split(...) // split the strings to retrieve their values
        int sValue2 = // ...
        int pValue1 = // ...
        int pValue2 = // ...
        if (sValue1 > sValue2) { return 1; }
        if (sValue1 < sValue2) { return -1; }
        if (pValue1 > pValue2) { return 1; }
        if (pValue 1 < pValue2) { return -1; }
        return 0;
    }

});

Aubin · Answer 5 · 2013-02-28T21:05:11.057

Here is the code:

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

public class CustomSorter {
   public static void main( String[] args ) {
      String[] data = {
         "ACLK_SCRN_200MHZ_DATAB_S0_P0:8",
         "ACLK_SCRN_200MHZ_DATAB_S0_P10:8",
         ...
         "ACLK_SCRN_200MHZ_DATAB_S1_P4:8",
         "ACLK_SCRN_200MHZ_DATAB_S1_P5:8",
      };
      List<String> trendList = Arrays.asList( data );
      Collections.sort( trendList, new Comparator< String >(){
         @Override public int compare( String o1, String o2 ){
            String[] p1 = o1.split( "_S\\d+_P" );
            String[] p2 = o2.split( "_S\\d+_P" );
            if( p1.length != 2 ) {
               throw new IllegalStateException("Unexpected item: '"+o1+"'");
            }
            if( p2.length != 2 ) {
               throw new IllegalStateException("Unexpected item: '"+o1+"'");
            }
            final int i1;
            try{
               i1 = Integer.parseInt(p1[1].substring(0,p1[1].indexOf(':')));
            } catch( NumberFormatException x ) {
               throw new IllegalStateException( "Unexpected item: '"+o1+"'");
            }
            final int i2;
            try{
               i2 = Integer.parseInt(p2[1].substring(0,p2[1].indexOf(':')));
            } catch( NumberFormatException x ) {
               throw new IllegalStateException("Unexpected item: '"+o2+"'");
            }
            int cmp = p1[0].compareTo( p2[0] );
            if( cmp == 0 ) {
               cmp = i1 - i2;
            }
            return cmp;
         }});
      for( String entry : trendList ) {
         System.out.println( entry );
      }
   }
}

and the outputs:

ACLK_SCRN_200MHZ_DATAB_S0_P0:8
ACLK_SCRN_200MHZ_DATAB_S0_P1:8
ACLK_SCRN_200MHZ_DATAB_S0_P2:8
ACLK_SCRN_200MHZ_DATAB_S0_P3:8
ACLK_SCRN_200MHZ_DATAB_S0_P4:8
ACLK_SCRN_200MHZ_DATAB_S0_P5:8
ACLK_SCRN_200MHZ_DATAB_S0_P6:8
ACLK_SCRN_200MHZ_DATAB_S0_P7:8
ACLK_SCRN_200MHZ_DATAB_S0_P8:8
ACLK_SCRN_200MHZ_DATAB_S0_P9:8
ACLK_SCRN_200MHZ_DATAB_S0_P10:8
ACLK_SCRN_200MHZ_DATAB_S0_P11:8
ACLK_SCRN_200MHZ_DATAB_S0_P12:8
ACLK_SCRN_200MHZ_DATAB_S0_P13:8
ACLK_SCRN_200MHZ_DATAB_S0_P14:8
ACLK_SCRN_200MHZ_DATAB_S0_P15:8
ACLK_SCRN_200MHZ_DATAB_S1_P0:8
ACLK_SCRN_200MHZ_DATAB_S1_P1:8
ACLK_SCRN_200MHZ_DATAB_S1_P2:8
ACLK_SCRN_200MHZ_DATAB_S1_P3:8
ACLK_SCRN_200MHZ_DATAB_S1_P4:8
ACLK_SCRN_200MHZ_DATAB_S1_P5:8
ACLK_SCRN_200MHZ_DATAB_S1_P10:8
ACLK_SCRN_200MHZ_DATAB_S1_P11:8
ACLK_SCRN_200MHZ_DATAB_S1_P12:8
ACLK_SCRN_200MHZ_DATAB_S1_P13:8
ACLK_SCRN_200MHZ_DATAB_S1_P14:8
ACLK_SCRN_200MHZ_DATAB_S1_P15:8

`ACLK_SCRN_200MHZ_DATAB_S12` will come before `ACLK_SCRN_200MHZ_DATAB_S2` if you don't check also the `S\\d+` number. — Alex, Feb 28 '13 at 20:12
This is very good. ONE last problem. What if there is a string which doesn't contain "_" or ":", but I still want that properly sorted? It seems substring( 0, p1[1].indexOf( ':' )) would break the code, since indexOf would return -1. What then would I reassign i1 and i2? — Mark Kennedy, Feb 28 '13 at 21:03
Error handling added. Please post an exhaustive specification of the input strings. — Aubin, Feb 28 '13 at 21:05
It's supposed to sort all string cases (NOT just ones containing ":" or "_"). Also, it's not helpful to just error out, but actually sort all strings. I posted a few sample cases that I sorted by hand, but would like the program to do. THANKS!!! — Mark Kennedy, Feb 28 '13 at 21:13
I did something like if(p1[1].indexOf( ':' ) == -1 || p2[1].indexOf(':' ) == -1) return 1; At least then it doesn't error out, but it doesn't correctly sort, either! — Mark Kennedy, Feb 28 '13 at 21:14
Also, I'm not assuming that two strings, say, ACLK_SCRN_200MHZ_DATAB_S0_P8:8 and ACLK_SCRN_200MHZ_DATAB_S1_P0:8, are already sorted .. i.e. "S0" < "S1". This code ONLY sorts based on the numbers between the colons. I'm looking for a function which sorts the colon part AS WELL AS the string part — Mark Kennedy, Feb 28 '13 at 21:29
Nevermind, I found the solution here - http://stackoverflow.com/questions/104599/sort-on-a-string-that-may-contain-a-number — Mark Kennedy, Feb 28 '13 at 22:17

Complex sorting of Java ArrayList

5 Answers5