Java String String Comparator

Question

I have a method that returns a String list to be sorted. However, I ran into the problem of sorting old strings and wondered if anyone could help implement the Comparator or point me in the direction of one.

The list will return something list:

State Lower Legislative District 1 State Lower Legislative District 11 State Lower Legislative District 12 ... State Lower Legislative District 2 ... State Lower Legislative District 100 ... State Upper Legislative District 1 State Upper Legislative District 11 ... 

So, first I need to do a basic String sort, but then I need to sort by number. The sort number should always be tracked and may be 2 or 3 digits.

(Edit). My initial thought is to split the string into a space, run StringUtils.isNumeric into parts of a number, and then sort. However, it seems to me that this is a little for me.

Can anyone help?

Answer 1

There is an article about this about horror coding. This is called natural sorting , where you efficiently treat a group of digits as a single "character". See this question for some Java implementations.

Sort for people: the natural sort order

The default sorting functions in almost every programming language are poorly suited for human consumption. What I mean? Well, consider the difference between sorting file names in Windows Explorer and sorting the same files using Array.Sort() code:

continued ...

Answer 2

I wrote a variation on String.CompareTo that compares the length of numbers found on two lines. When dialing two numbers with the same length, the alphanumeric comparison resumes as usual. It also skips leading zeros.

 public static int compareNatural(String a, String b) { int la = a.length(); int lb = b.length(); int ka = 0; int kb = 0; while (true) { if (ka == la) return kb == lb ? 0 : -1; if (kb == lb) return 1; if (a.charAt(ka) >= '0' && a.charAt(ka) <= '9' && b.charAt(kb) >= '0' && b.charAt(kb) <= '9') { int na = 0; int nb = 0; while (ka < la && a.charAt(ka) == '0') ka++; while (ka + na < la && a.charAt(ka + na) >= '0' && a.charAt(ka + na) <= '9') na++; while (kb < lb && b.charAt(kb) == '0') kb++; while (kb + nb < lb && b.charAt(kb + nb) >= '0' && b.charAt(kb + nb) <= '9') nb++; if (na > nb) return 1; if (nb > na) return -1; if (ka == la) return kb == lb ? 0 : -1; if (kb == lb) return 1; } if (a.charAt(ka) != b.charAt(kb)) return a.charAt(ka) - b.charAt(kb); ka++; kb++; } } 

Answer 3

One way is to use a simple regular expression to parse interest fields in your comparator, and then compare them manually. Here's an untested example:

 private static final Pattern pattern = Pattern.compile("^State (Lower|Upper) Legislative District (\\d+)$"); public int compare(String a, String b) { Matcher matcher1 = pattern.matcher(a); Matcher matcher2 = pattern.matcher(b); if( matcher1.matches() && matcher2.matches() ) { //compare upper/lower int upperLowerComparison = matcher1.group(1).compareTo(matcher2.group(1)); if ( upperLowerComparison != 0 ) { return upperLowerComparison; } //number comparison return Integer.valueOf(matcher1.group(2)).compareTo(Integer.valueOf(matcher2.group(2)); } //...what to do if they don't match? } 

Answer 4

You have two options. The first is to create a class that has two fields - a name and a number. Of course, first analyze the name and numbers. Then in the comparator, first compare the name and then the number. The second is to perform in-place parsing in the compare method. Choose which one suits you best.

Answer 5

Take a look at this implementation:

 public static int naturalCompare(String a, String b, boolean ignoreCase) { if (ignoreCase) { a = a.toLowerCase(); b = b.toLowerCase(); } int aLength = a.length(); int bLength = b.length(); int minSize = Math.min(aLength, bLength); char aChar, bChar; boolean aNumber, bNumber; boolean asNumeric = false; int lastNumericCompare = 0; for (int i = 0; i < minSize; i++) { aChar = a.charAt(i); bChar = b.charAt(i); aNumber = aChar >= '0' && aChar <= '9'; bNumber = bChar >= '0' && bChar <= '9'; if (asNumeric) if (aNumber && bNumber) { if (lastNumericCompare == 0) lastNumericCompare = aChar - bChar; } else if (aNumber) return 1; else if (bNumber) return -1; else if (lastNumericCompare == 0) { if (aChar != bChar) return aChar - bChar; asNumeric = false; } else return lastNumericCompare; else if (aNumber && bNumber) { asNumeric = true; if (lastNumericCompare == 0) lastNumericCompare = aChar - bChar; } else if (aChar != bChar) return aChar - bChar; } if (asNumeric) if (aLength > bLength && a.charAt(bLength) >= '0' && a.charAt(bLength) <= '9') // as number return 1; // a has bigger size, thus b is smaller else if (bLength > aLength && b.charAt(aLength) >= '0' && b.charAt(aLength) <= '9') // as number return -1; // b has bigger size, thus a is smaller else return lastNumericCompare; else return aLength - bLength; } 

It should be fast, without any regular expressions or array manipulation, just a few flags and many cases.

This should sort any combination of numbers inside the lines and properly support numbers that are equal and moving.

Answer 6

A simple implementation will be like this (this works with any line ending with a number):

 public class SplitComparator implements Comparator<String> { static class Pair implements Comparable<Pair> { private String name; private Integer number; public Pair(String value) { value = value.trim(); this.name = value.substring( 0, value.lastIndexOf(" ") ); this.number = Integer.valueOf( value.substring( value.lastIndexOf(" ") + 1, value.length() ) ); } @Override public int compareTo( Pair right) { int result = this.name.compareTo( right.name ); if ( result == 0 ) { result = this.number.compareTo( right.number ); } return result; } } @Override public int compare(String left, String right) { return new Pair( left ).compareTo( new Pair( right ) ); } public static void main( String ... args ) { String[] values = { "State Lower Legislative District 1", "State Lower Legislative District 11", "State Upper Legislative District 1", "State Upper Legislative District 11"}; SplitComparator comparator = new SplitComparator(); System.out.println( comparator.compare( values[1] , values[0]) ); System.out.println( comparator.compare( values[0] , values[1]) ); System.out.println( comparator.compare( values[0] , values[3]) ); } } 

Answer 7

I usually do this by prefixing zeros to a number and treat the whole object as a string. then sort it.

See this:

 public abstract class MyNumberComparator { protected int doCompare(final String number1, final String number2) { String strNumber1 = fillUpLeftWithZeros(number1, 30); String strNumber2 = fillUpLeftWithZeros(number2, 30); return strNumber1.toUpperCase().compareTo(strNumber2.toUpperCase()); } }