Sort on a string that may contain a number

Question

I need to write a Java Comparator class that compares Strings, however with one twist. If the two strings being compared are the same at the beginning and the end, and the middle part that differs is an integer, then compare based on the numeric values of those integers. For example, I want the following strings to end up in the order they're shown:

• aaa
• bbb 3 ccc
• bbb 12 ccc
• ccc 11
• ddd
• eee 3 ddd jpeg2000 eee
• eee 12 ddd jpeg2000 eee

As you can see, there might be other integers in the string, so I can't just use regular expressions to break out any integer. I'm thinking of just walking the strings from the beginning until I find a bit that doesn't match, then walking in from the end until I find a bit that doesn't match, and then comparing the bit in the middle to the regular expression "[0-9]+", and if it compares, then doing a numeric comparison, otherwise doing a lexical comparison.

Is there a better way?

Update I don't think I can guarantee that the other numbers in the string, the ones that may match, don't have spaces around them, or that the ones that differ do have spaces.

Answer 1

The most "correct" (though this is subjective) algorithm I can think of should focus on alphabetical and numeric characters according to the Unicode standard, should perform locale-aware sorting for the alphabetical portions, and mathematical ordering of the numeric portions.

1. Extract the list of alphabetical or numeric strings from each string. One way to do this is with the Unicode-aware regex [\p{Ll}\p{Lu}]+|\p{Nd}+. For example, this turns the string 3abk,-Cd43 into the list [3, abk, Cd, 43]
2. Compare the resulting lists of strings lexicographically (i.e. element-by-element) using the following comparison rules for the elements:
   • If comparing an alphabetical string with a numeric string, numeric is always less
   • If comparing two numeric strings, parse both as integers and compare as integers
   • If comparing two alphabetical strings, use a Collator with strength SECONDARY to compare them (this performs a locale-aware, case-insensitive comparison)
3. If the lists are not lexicographically equal, return that comparison result
4. If the lists are lexicographically equal, return the result of the naive comparison of the original strings to handle things like punctuation

I haven't found a Java library that implements this exact algorithm, so here is my implementation:

import java.text.Collator;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class NaturalComparator implements Comparator<String> {
    Pattern pattern;
    Collator collator;

    public NaturalComparator() {
        pattern = Pattern.compile("[\\p{Ll}\\p{Lu}]+|\\p{Nd}+");
        collator = Collator.getInstance();
        collator.setStrength(Collator.SECONDARY);
    }

    public int compare(String str1, String str2) {
        Matcher matcher1 = pattern.matcher(str1);
        Matcher matcher2 = pattern.matcher(str2);

        while (true) {
            boolean found1 = matcher1.find();
            boolean found2 = matcher2.find();
            if (found1 && !found2) return 1; // equal so far, but str2 has fewer groups
            if (!found1 && found2) return -1; // equal so far, but str1 has fewer groups
            if (!found1 && !found2) break; // no more groups

            String group1 = matcher1.group();
            String group2 = matcher2.group();

            Integer int1;
            try {
                int1 = Integer.parseInt(group1);
            } catch (NumberFormatException e) {
                int1 = null;
            }
            Integer int2;
            try {
                int2 = Integer.parseInt(group2);
            } catch (NumberFormatException e) {
                int2 = null;
            }

            if (int1 != null && int2 != null) { // both numeric
                int result = int1.compareTo(int2);
                if (result != 0) return result;
            }
            if (int1 != null) return -1; // group1 is numeric, group2 is not
            if (int2 != null) return 1; // group2 is numeric, group1 is not

            int result = collator.compare(group1, group2); // both alphabetical, use collator
            if (result != 0) return result;
        }

        // strings are group-wise equal, so fall back to naive comparison to sort by punctuation, etc.
        return str1.compareTo(str2);
    }
}

Answer 2

modification of this answer

---

• case insensitive order (1000a is less than 1000X)
• leading zeros go first (0.0010 is less than 0.01)
• nulls handling

implementation:

import static java.lang.Math.pow;

import java.util.Comparator;

public class AlphanumComparator implements Comparator<String> {
    
    public static final AlphanumComparator ALPHANUM_COMPARATOR = new AlphanumComparator();
    private static char[] upperCaseCache = new char[(int) pow(2, 16)];
    private boolean nullIsLess;
    
    public AlphanumComparator() {
    }
    
    public AlphanumComparator(boolean nullIsLess) {
        this.nullIsLess = nullIsLess;
    }
    
    @Override
    public int compare(String s1, String s2) {
        if (s1 == s2)
            return 0;
        if (s1 == null)
            return nullIsLess ? -1 : 1;
        if (s2 == null)
            return nullIsLess ? 1 : -1;
        
        int i1 = 0;
        int i2 = 0;
        int len1 = s1.length();
        int len2 = s2.length();
        while (true) {
            // handle the case when one string is longer than another
            if (i1 == len1)
                return i2 == len2 ? 0 : -1;
            if (i2 == len2)
                return 1;
            
            char ch1 = s1.charAt(i1);
            char ch2 = s2.charAt(i2);
            if (isDigit(ch1) && isDigit(ch2)) {
                // skip leading zeros
                while (i1 < len1 && s1.charAt(i1) == '0')
                    i1++;
                while (i2 < len2 && s2.charAt(i2) == '0')
                    i2++;
                // leading zeros go first
                if (i1 != i2)
                    return i2 - i1;

                // find the ends of the numbers
                int end1 = i1;
                int end2 = i2;
                while (end1 < len1 && isDigit(s1.charAt(end1)))
                    end1++;
                while (end2 < len2 && isDigit(s2.charAt(end2)))
                    end2++;
                
                // if the lengths are different, then the longer number is bigger
                int diglen1 = end1 - i1;
                int diglen2 = end2 - i2;
                if (diglen1 != diglen2)
                    return diglen1 - diglen2;
                
                // compare numbers digit by digit
                while (i1 < end1) {
                    ch1 = s1.charAt(i1);
                    ch2 = s2.charAt(i2);
                    if (ch1 != ch2)
                        return ch1 - ch2;
                    i1++;
                    i2++;
                }
            } else {
                ch1 = toUpperCase(ch1);
                ch2 = toUpperCase(ch2);
                if (ch1 != ch2)
                    return ch1 - ch2;
                i1++;
                i2++;
            }
        }
    }
    
    private boolean isDigit(char ch) {
        return ch >= 48 && ch <= 57;
    }
    
    private char toUpperCase(char ch) {
        char cached = upperCaseCache[ch];
        if (cached == 0) {
            cached = Character.toUpperCase(ch);
            upperCaseCache[ch] = cached;
        }
        return cached;
    }
}

sorted list

"10X Radonius",
"20X Radonius",
"20X Radonius Prime",
"30X Radonius",
"40X Radonius",
"200X Radonius",
"1000a Radonius Maximus",
"1000X Radonius Maximus",
"Allegia 6R Clasteron",
"Allegia 50 Clasteron",
"Allegia 50B Clasteron",
"Allegia 51 Clasteron",
"Allegia 500 Clasteron",
"Alpha 0.000100",
"Alpha 0.001",
"Alpha 0.002 001",
"Alpha 0.01",
"Alpha 0.01 0001",
"Alpha 1",
"Alpha 2",
"Alpha 2A",
"Alpha 2A-900",
"Alpha 2A-8000",
"Alpha 200",
"Callisto Morphamax",
"Callisto Morphamax 500",
"Callisto Morphamax 600",
"Callisto Morphamax 700",
"Callisto Morphamax 5000",
"Callisto Morphamax 6000 SE",
"Callisto Morphamax 6000 SE2",
"Callisto Morphamax 7000",
"Xiph Xlater 5",
"Xiph Xlater 40",
"Xiph Xlater 50",
"Xiph Xlater 58",
"Xiph Xlater 300",
"Xiph Xlater 500",
"Xiph Xlater 2000",
"Xiph Xlater 5000",
"Xiph Xlater 10000",
null

Answer 3

Only a few years late, but here's an elegant and short solution:

Collections.sort(b, new Comparator<String>(){
        @Override
        public int compare(String a, String b){
            if(a.equals(b)) return 0;
            for(int i = 0; i < Math.min(a.length(), b.length()); i++){
                char aChar = a.charAt(i), bChar = b.charAt(i);
                int comp = Character.compare(aChar, bChar);
                if(comp == 0) continue;
                return comp;
            }
            return a.length() < b.length() ? -1 : 1;
        }
    });

Answer 4

The Alphanum Algorithm

From the website

"People sort strings with numbers differently than software. Most sorting algorithms compare ASCII values, which produces an ordering that is inconsistent with human logic. Here's how to fix it."

Edit: Here's a link to the Java Comparator Implementation from that site.

Answer 5

The implementation I propose here is simple and efficient. It does not allocate any extra memory, directly or indirectly by using regular expressions or methods such as substring(), split(), toCharArray(), etc.

This implementation first goes across both strings to search for the first characters that are different, at maximal speed, without doing any special processing during this. Specific number comparison is triggered only when these characters are both digits.

public static final int compareNatural (String s1, String s2)
{
   // Skip all identical characters
   int len1 = s1.length();
   int len2 = s2.length();
   int i;
   char c1, c2;
   for (i = 0, c1 = 0, c2 = 0; (i < len1) && (i < len2) && (c1 = s1.charAt(i)) == (c2 = s2.charAt(i)); i++);
   
   // Check end of string
   if (c1 == c2)
      return(len1 - len2);

   // Check digit in first string
   if (Character.isDigit(c1))
   {
      // Check digit only in first string 
      if (!Character.isDigit(c2))
         return(1);
      
      // Scan all integer digits
      int x1, x2;
      for (x1 = i + 1; (x1 < len1) && Character.isDigit(s1.charAt(x1)); x1++);
      for (x2 = i + 1; (x2 < len2) && Character.isDigit(s2.charAt(x2)); x2++);
      
      // Longer integer wins, first digit otherwise
      return(x2 == x1 ? c1 - c2 : x1 - x2);
   }
   
   // Check digit only in second string
   if (Character.isDigit(c2))
      return(-1);
   
   // No digits
   return(c1 - c2);
}

Answer 6

Instead of reinventing the wheel, I'd suggest to use a locale-aware Unicode-compliant string comparator that has built-in number sorting from the ICU4J library.

import com.ibm.icu.text.Collator;
import com.ibm.icu.text.RuleBasedCollator;

import java.util.Arrays;
import java.util.List;
import java.util.Locale;

public class CollatorExample {
    public static void main(String[] args) {
        // Make sure to choose correct locale: in Turkish uppercase of "i" is "İ", not "I"
        RuleBasedCollator collator = (RuleBasedCollator) Collator.getInstance(Locale.US);
        collator.setNumericCollation(true); // Place "10" after "2"
        collator.setStrength(Collator.PRIMARY); // Case-insensitive
        List<String> strings = Arrays.asList("10", "20", "A20", "2", "t1ab", "01", "T010T01", "t1aB",
            "_2", "001", "_200", "1", "A 02", "t1Ab", "a2", "_1", "t1A", "_01",
            "100", "02", "T0010T01", "t1AB", "10", "A01", "010", "t1a"
        );
        strings.sort(collator);
        System.out.println(String.join(", ", strings));
        // Output: _1, _01, _2, _200, 01, 001, 1,
        // 2, 02, 10, 10, 010, 20, 100, A 02, A01, 
        // a2, A20, t1A, t1a, t1ab, t1aB, t1Ab, t1AB,
        // T010T01, T0010T01
    }
}

Answer 7

Adding on to the answer made by @stanislav. A few problems I faced while using the answer provided was:

1. Capital and small letters are separated by the characters between their ASCII codes. This breaks the flow when the strings being sorted have _ or other characters which are between small letters and capital letters in ASCII.
2. If two strings are the same except for the leading zeroes count being different, the function returns 0 which will make the sort depend on the original positions of the string in the list.

These two issues have been fixed in the new code. And I made a few function instead of a few repetitive set of code. The differentCaseCompared variable keeps track of whether if two strings are the same except for the cases being different. If so the value of the first different case characters subtracted is returned. This is done to avoid the issue of having two strings differing by case returned as 0.

public class NaturalSortingComparator implements Comparator<String> {

    @Override
    public int compare(String string1, String string2) {
        int lengthOfString1 = string1.length();
        int lengthOfString2 = string2.length();
        int iteratorOfString1 = 0;
        int iteratorOfString2 = 0;
        int differentCaseCompared = 0;
        while (true) {
            if (iteratorOfString1 == lengthOfString1) {
                if (iteratorOfString2 == lengthOfString2) {
                    if (lengthOfString1 == lengthOfString2) {
                        // If both strings are the same except for the different cases, the differentCaseCompared will be returned
                        return differentCaseCompared;
                    }
                    //If the characters are the same at the point, returns the difference between length of the strings
                    else {
                        return lengthOfString1 - lengthOfString2;
                    }
                }
                //If String2 is bigger than String1
                else
                    return -1;
            }
            //Check if String1 is bigger than string2
            if (iteratorOfString2 == lengthOfString2) {
                return 1;
            }

            char ch1 = string1.charAt(iteratorOfString1);
            char ch2 = string2.charAt(iteratorOfString2);

            if (Character.isDigit(ch1) && Character.isDigit(ch2)) {
                // skip leading zeros
                iteratorOfString1 = skipLeadingZeroes(string1, lengthOfString1, iteratorOfString1);
                iteratorOfString2 = skipLeadingZeroes(string2, lengthOfString2, iteratorOfString2);

                // find the ends of the numbers
                int endPositionOfNumbersInString1 = findEndPositionOfNumber(string1, lengthOfString1, iteratorOfString1);
                int endPositionOfNumbersInString2 = findEndPositionOfNumber(string2, lengthOfString2, iteratorOfString2);

                int lengthOfDigitsInString1 = endPositionOfNumbersInString1 - iteratorOfString1;
                int lengthOfDigitsInString2 = endPositionOfNumbersInString2 - iteratorOfString2;

                // if the lengths are different, then the longer number is bigger
                if (lengthOfDigitsInString1 != lengthOfDigitsInString2)
                    return lengthOfDigitsInString1 - lengthOfDigitsInString2;

                // compare numbers digit by digit
                while (iteratorOfString1 < endPositionOfNumbersInString1) {

                    if (string1.charAt(iteratorOfString1) != string2.charAt(iteratorOfString2))
                        return string1.charAt(iteratorOfString1) - string2.charAt(iteratorOfString2);

                    iteratorOfString1++;
                    iteratorOfString2++;
                }
            } else {
                // plain characters comparison
                if (ch1 != ch2) {
                    if (!ignoreCharacterCaseEquals(ch1, ch2))
                        return Character.toLowerCase(ch1) - Character.toLowerCase(ch2);

                    // Set a differentCaseCompared if the characters being compared are different case.
                    // Should be done only once, hence the check with 0
                    if (differentCaseCompared == 0) {
                        differentCaseCompared = ch1 - ch2;
                    }
                }

                iteratorOfString1++;
                iteratorOfString2++;
            }
        }
    }

    private boolean ignoreCharacterCaseEquals(char character1, char character2) {

        return Character.toLowerCase(character1) == Character.toLowerCase(character2);
    }

    private int findEndPositionOfNumber(String string, int lengthOfString, int end) {

        while (end < lengthOfString && Character.isDigit(string.charAt(end)))
            end++;

        return end;
    }

    private int skipLeadingZeroes(String string, int lengthOfString, int iteratorOfString) {

        while (iteratorOfString < lengthOfString && string.charAt(iteratorOfString) == '0')
            iteratorOfString++;

        return iteratorOfString;
    }
}

The following is a unit test I used.

public class NaturalSortingComparatorTest {

    private int NUMBER_OF_TEST_CASES = 100000;

    @Test
    public void compare() {

        NaturalSortingComparator naturalSortingComparator = new NaturalSortingComparator();

        List<String> expectedStringList = getCorrectStringList();
        List<String> testListOfStrings = createTestListOfStrings();
        runTestCases(expectedStringList, testListOfStrings, NUMBER_OF_TEST_CASES, naturalSortingComparator);

    }

    private void runTestCases(List<String> expectedStringList, List<String> testListOfStrings,
                              int numberOfTestCases, Comparator<String> comparator) {

        for (int testCase = 0; testCase < numberOfTestCases; testCase++) {
            Collections.shuffle(testListOfStrings);
            testListOfStrings.sort(comparator);
            Assert.assertEquals(expectedStringList, testListOfStrings);
        }
    }

    private List<String> getCorrectStringList() {
        return Arrays.asList(
                "1", "01", "001", "2", "02", "10", "10", "010",
                "20", "100", "_1", "_01", "_2", "_200", "A 02",
                "A01", "a2", "A20", "t1A", "t1a", "t1AB", "t1Ab",
                "t1aB", "t1ab", "T010T01", "T0010T01");
    }

    private List<String> createTestListOfStrings() {
        return Arrays.asList(
                "10", "20", "A20", "2", "t1ab", "01", "T010T01", "t1aB",
                "_2", "001", "_200", "1", "A 02", "t1Ab", "a2", "_1", "t1A", "_01",
                "100", "02", "T0010T01", "t1AB", "10", "A01", "010", "t1a");
    }

}

Suggestions welcome! I am not sure whether adding the functions changes anything other than the readability part of things.

P.S: Sorry to add another answer to this question. But I don't have enough reps to comment on the answer which I modified for my use.

Answer 8

Here is the solution with the following advantages over Alphanum Algorithm:

1. 3.25x times faster (tested on the data from 'Epilogue' chapter of Alphanum description)
2. Does not consume extra memory (no string splitting, no numbers parsing)
3. Processes leading zeros correctly (e.g. "0001" equals "1", "01234" is less than "4567")

public class NumberAwareComparator implements Comparator<String>
{
    @Override
    public int compare(String s1, String s2)
    {
        int len1 = s1.length();
        int len2 = s2.length();
        int i1 = 0;
        int i2 = 0;
        while (true)
        {
            // handle the case when one string is longer than another
            if (i1 == len1)
                return i2 == len2 ? 0 : -1;
            if (i2 == len2)
                return 1;

            char ch1 = s1.charAt(i1);
            char ch2 = s2.charAt(i2);
            if (Character.isDigit(ch1) && Character.isDigit(ch2))
            {
                // skip leading zeros
                while (i1 < len1 && s1.charAt(i1) == '0')
                    i1++;
                while (i2 < len2 && s2.charAt(i2) == '0')
                    i2++;

                // find the ends of the numbers
                int end1 = i1;
                int end2 = i2;
                while (end1 < len1 && Character.isDigit(s1.charAt(end1)))
                    end1++;
                while (end2 < len2 && Character.isDigit(s2.charAt(end2)))
                    end2++;

                int diglen1 = end1 - i1;
                int diglen2 = end2 - i2;

                // if the lengths are different, then the longer number is bigger
                if (diglen1 != diglen2)
                    return diglen1 - diglen2;

                // compare numbers digit by digit
                while (i1 < end1)
                {
                    if (s1.charAt(i1) != s2.charAt(i2))
                        return s1.charAt(i1) - s2.charAt(i2);
                    i1++;
                    i2++;
                }
            }
            else
            {
                // plain characters comparison
                if (ch1 != ch2)
                    return ch1 - ch2;
                i1++;
                i2++;
            }
        }
    }
}

Answer 9

I created a project to compare the different implementations. It is far from complete, but it is a starting point.

Answer 10

I had a similar problem where my strings had space-separated segments inside. I solved it in this way:

public class StringWithNumberComparator implements Comparator<MyClass> {

@Override
public int compare(MyClass o1, MyClass o2) {
    if (o1.getStringToCompare().equals(o2.getStringToCompare())) {
        return 0;
    }
    String[] first = o1.getStringToCompare().split(" ");
    String[] second = o2.getStringToCompare().split(" ");
    if (first.length == second.length) {
        for (int i = 0; i < first.length; i++) {

            int segmentCompare = StringUtils.compare(first[i], second[i]);
            if (StringUtils.isNumeric(first[i]) && StringUtils.isNumeric(second[i])) {

                segmentCompare = NumberUtils.compare(Integer.valueOf(first[i]), Integer.valueOf(second[i]));
                if (0 != segmentCompare) {
                    // return only if uneven numbers in case there are more segments to be checked
                    return segmentCompare;
                }
            }
            if (0 != segmentCompare) {
                return segmentCompare;
            }
        }
    } else {
        return StringUtils.compare(o1.getDenominazione(), o2.getDenominazione());
    }

    return 0;
}

As you can see I have used Apaches StringUtils.compare() and NumberUtils.compere() as a standard help.

Answer 11

The Alphanum algrothim is nice, but it did not match requirements for a project I'm working on. I need to be able to sort negative numbers and decimals correctly. Here is the implementation I came up. Any feedback would be much appreciated.

public class StringAsNumberComparator implements Comparator<String> {

    public static final Pattern NUMBER_PATTERN = Pattern.compile("(\\-?\\d+\\.\\d+)|(\\-?\\.\\d+)|(\\-?\\d+)");

    /**
     * Splits strings into parts sorting each instance of a number as a number if there is
     * a matching number in the other String.
     * 
     * For example A1B, A2B, A11B, A11B1, A11B2, A11B11 will be sorted in that order instead
     * of alphabetically which will sort A1B and A11B together.
     */
    public int compare(String str1, String str2) {
        if(str1 == str2) return 0;
        else if(str1 == null) return 1;
        else if(str2 == null) return -1;

        List<String> split1 = split(str1);
        List<String> split2 = split(str2);
        int diff = 0;

        for(int i = 0; diff == 0 && i < split1.size() && i < split2.size(); i++) {
            String token1 = split1.get(i);
            String token2 = split2.get(i);

            if((NUMBER_PATTERN.matcher(token1).matches() && NUMBER_PATTERN.matcher(token2).matches()) {
                diff = (int) Math.signum(Double.parseDouble(token1) - Double.parseDouble(token2));
            } else {
                diff = token1.compareToIgnoreCase(token2);
            }
        }
        if(diff != 0) {
            return diff;
        } else {
            return split1.size() - split2.size();
        }
    }

    /**
     * Splits a string into strings and number tokens.
     */
    private List<String> split(String s) {
        List<String> list = new ArrayList<String>();
        try (Scanner scanner = new Scanner(s)) {
            int index = 0;
            String num = null;
            while ((num = scanner.findInLine(NUMBER_PATTERN)) != null) {
                int indexOfNumber = s.indexOf(num, index);
                if (indexOfNumber > index) {
                    list.add(s.substring(index, indexOfNumber));
                }
                list.add(num);
                index = indexOfNumber + num.length();
            }
            if (index < s.length()) {
                list.add(s.substring(index));
            }
        }
        return list;
    }
}

PS. I wanted to use the java.lang.String.split() method and use "lookahead/lookbehind" to keep the tokens, but I could not get it to work with the regular expression I was using.

Answer 12

My problem was that I have lists consisting of a combination of alpha numeric strings (eg C22, C3, C5 etc), alpha strings (eg A, H, R etc) and just digits (eg 99, 45 etc) that need sorting in the order A, C3, C5, C22, H, R, 45, 99. I also have duplicates that need removing so I only get a single entry.

I'm also not just working with Strings, I'm ordering an Object and using a specific field within the Object to get the correct order.

A solution that seems to work for me is :

SortedSet<Code> codeSet;
codeSet = new TreeSet<Code>(new Comparator<Code>() {

private boolean isThereAnyNumber(String a, String b) {
    return isNumber(a) || isNumber(b);
}

private boolean isNumber(String s) {
    return s.matches("[-+]?\\d*\\.?\\d+");
}

private String extractChars(String s) {
    String chars = s.replaceAll("\\d", "");
    return chars;
}

private int extractInt(String s) {
    String num = s.replaceAll("\\D", "");
    return num.isEmpty() ? 0 : Integer.parseInt(num);
}

private int compareStrings(String o1, String o2) {

    if (!extractChars(o1).equals(extractChars(o2))) {
        return o1.compareTo(o2);
    } else
        return extractInt(o1) - extractInt(o2);
}

@Override
public int compare(Code a, Code b) {

    return isThereAnyNumber(a.getPrimaryCode(), b.getPrimaryCode()) 
            ? isNumber(a.getPrimaryCode()) ? 1 : -1 
                : compareStrings(a.getPrimaryCode(), b.getPrimaryCode());
                }
            });

It 'borrows' some code that I found here on Stackoverflow plus some tweaks of my own to get it working just how I needed it too.

Due to trying to order Objects, needing a comparator as well as duplicate removal, one negative fudge I had to employ was I first have to write my Objects to a TreeMap before writing them to a Treeset. It may impact performance a little but given that the lists will be a max of about 80 Codes, it shouldn't be a problem.

Answer 13

I came up with a quite simple implementation in Java using regular expressions:

public static Comparator<String> naturalOrdering() {
    final Pattern compile = Pattern.compile("(\\d+)|(\\D+)");
    return (s1, s2) -> {
        final Matcher matcher1 = compile.matcher(s1);
        final Matcher matcher2 = compile.matcher(s2);
        while (true) {
            final boolean found1 = matcher1.find();
            final boolean found2 = matcher2.find();
            if (!found1 || !found2) {
                return Boolean.compare(found1, found2);
            } else if (!matcher1.group().equals(matcher2.group())) {
                if (matcher1.group(1) == null || matcher2.group(1) == null) {
                    return matcher1.group().compareTo(matcher2.group());
                } else {
                    return Integer.valueOf(matcher1.group(1)).compareTo(Integer.valueOf(matcher2.group(1)));
                }
            }
        }
    };
}

Here is how it works:

final List<String> strings = Arrays.asList("x15", "xa", "y16", "x2a", "y11", "z", "z5", "x2b", "z");
strings.sort(naturalOrdering());
System.out.println(strings);

[x2a, x2b, x15, xa, y11, y16, z, z, z5]

Answer 14

Although the question asked a java solution, for anyone who wants a scala solution:

object Alphanum {

   private[this] val regex = "((?<=[0-9])(?=[^0-9]))|((?<=[^0-9])(?=[0-9]))"

   private[this] val alphaNum: Ordering[String] = Ordering.fromLessThan((ss1: String, ss2: String) => (ss1, ss2) match {
     case (sss1, sss2) if sss1.matches("[0-9]+") && sss2.matches("[0-9]+") => sss1.toLong < sss2.toLong
     case (sss1, sss2) => sss1 < sss2
   })

   def ordering: Ordering[String] = Ordering.fromLessThan((s1: String, s2: String) => {
     import Ordering.Implicits.infixOrderingOps
     implicit val ord: Ordering[List[String]] = Ordering.Implicits.seqDerivedOrdering(alphaNum)

     s1.split(regex).toList < s2.split(regex).toList
   })

}

Answer 15

My 2 cents.Is working well for me. I am mainly using it for filenames.

    private final boolean isDigit(char ch)
        {
            return ch >= 48 && ch <= 57;
        }


        private int compareNumericalString(String s1,String s2){

            int s1Counter=0;
            int s2Counter=0;
            while(true){
                if(s1Counter>=s1.length()){
                    break;
                }
                if(s2Counter>=s2.length()){
                    break;
                }
                char currentChar1=s1.charAt(s1Counter++);
                char currentChar2=s2.charAt(s2Counter++);
                if(isDigit(currentChar1) &&isDigit(currentChar2)){
                    String digitString1=""+currentChar1;
                    String digitString2=""+currentChar2;
                    while(true){
                        if(s1Counter>=s1.length()){
                            break;
                        }
                        if(s2Counter>=s2.length()){
                            break;
                        }

                        if(isDigit(s1.charAt(s1Counter))){
                            digitString1+=s1.charAt(s1Counter);
                            s1Counter++;
                        }

                        if(isDigit(s2.charAt(s2Counter))){
                            digitString2+=s2.charAt(s2Counter);
                            s2Counter++;
                        }

                        if((!isDigit(s1.charAt(s1Counter))) && (!isDigit(s2.charAt(s2Counter)))){
                            currentChar1=s1.charAt(s1Counter);
                            currentChar2=s2.charAt(s2Counter);
                            break;
                        }
                    }
                    if(!digitString1.equals(digitString2)){
                        return Integer.parseInt(digitString1)-Integer.parseInt(digitString2);
                    }
                }

                if(currentChar1!=currentChar2){
                    return currentChar1-currentChar2;
                }

            }
            return s1.compareTo(s2);
        }

Answer 16

Prior to discovering this thread, I implemented a similar solution in javascript. Perhaps my strategy will find you well, despite different syntax. Similar to above, I parse the two strings being compared, and split them both into arrays, dividing the strings at continuous numbers.

...
var regex = /(\d+)/g,
    str1Components = str1.split(regex),
    str2Components = str2.split(regex),
...

I.e., 'hello22goodbye 33' => ['hello', 22, 'goodbye ', 33]; Thus, you can walk through the arrays' elements in pairs between string1 and string2, do some type coercion (such as, is this element really a number?), and compare as you walk.

Working example here: http://jsfiddle.net/F46s6/3/

Note, I currently only support integer types, though handling decimal values wouldn't be too hard of a modification.

Answer 17

interesting problem, and here my proposed solution:

import java.util.Collections;
import java.util.Vector;

public class CompareToken implements Comparable<CompareToken>
{
    int valN;
    String valS;
    String repr;

    public String toString() {
    return repr;
    }

    public CompareToken(String s) {
    int l = 0;
    char data[] = new char[s.length()];
    repr = s;
    valN = 0;
    for (char c : s.toCharArray()) {
        if(Character.isDigit(c))
        valN = valN * 10 + (c - '0');
        else
        data[l++] = c;
    }

    valS = new String(data, 0, l);
    }

    public int compareTo(CompareToken b) {
    int r = valS.compareTo(b.valS);
    if (r != 0)
        return r;

    return valN - b.valN;
    }


    public static void main(String [] args) {
    String [] strings = {
        "aaa",
        "bbb3ccc",
        "bbb12ccc",
        "ccc 11",
        "ddd",
        "eee3dddjpeg2000eee",
        "eee12dddjpeg2000eee"
    };

    Vector<CompareToken> data = new Vector<CompareToken>();
    for(String s : strings)
        data.add(new CompareToken(s));
    Collections.shuffle(data);

    Collections.sort(data);
    for (CompareToken c : data)
        System.out.println ("" + c);
    }

}

Answer 18

Interesting little challenge, I enjoyed solving it.

Here is my take at the problem:

String[] strs =
{
  "eee 5 ddd jpeg2001 eee",
  "eee 123 ddd jpeg2000 eee",
  "ddd",
  "aaa 5 yy 6",
  "ccc 555",
  "bbb 3 ccc",
  "bbb 9 a",
  "",
  "eee 4 ddd jpeg2001 eee",
  "ccc 11",
  "bbb 12 ccc",
  "aaa 5 yy 22",
  "aaa",
  "eee 3 ddd jpeg2000 eee",
  "ccc 5",
};

Pattern splitter = Pattern.compile("(\\d+|\\D+)");

public class InternalNumberComparator implements Comparator
{
  public int compare(Object o1, Object o2)
  {
    // I deliberately use the Java 1.4 syntax, 
    // all this can be improved with 1.5's generics
    String s1 = (String)o1, s2 = (String)o2;
    // We split each string as runs of number/non-number strings
    ArrayList sa1 = split(s1);
    ArrayList sa2 = split(s2);
    // Nothing or different structure
    if (sa1.size() == 0 || sa1.size() != sa2.size())
    {
      // Just compare the original strings
      return s1.compareTo(s2);
    }
    int i = 0;
    String si1 = "";
    String si2 = "";
    // Compare beginning of string
    for (; i < sa1.size(); i++)
    {
      si1 = (String)sa1.get(i);
      si2 = (String)sa2.get(i);
      if (!si1.equals(si2))
        break;  // Until we find a difference
    }
    // No difference found?
    if (i == sa1.size())
      return 0; // Same strings!

    // Try to convert the different run of characters to number
    int val1, val2;
    try
    {
      val1 = Integer.parseInt(si1);
      val2 = Integer.parseInt(si2);
    }
    catch (NumberFormatException e)
    {
      return s1.compareTo(s2);  // Strings differ on a non-number
    }

    // Compare remainder of string
    for (i++; i < sa1.size(); i++)
    {
      si1 = (String)sa1.get(i);
      si2 = (String)sa2.get(i);
      if (!si1.equals(si2))
      {
        return s1.compareTo(s2);  // Strings differ
      }
    }

    // Here, the strings differ only on a number
    return val1 < val2 ? -1 : 1;
  }

  ArrayList split(String s)
  {
    ArrayList r = new ArrayList();
    Matcher matcher = splitter.matcher(s);
    while (matcher.find())
    {
      String m = matcher.group(1);
      r.add(m);
    }
    return r;
  }
}

Arrays.sort(strs, new InternalNumberComparator());

This algorithm need much more testing, but it seems to behave rather nicely.

[EDIT] I added some more comments to be clearer. I see there are much more answers than when I started to code this... But I hope I provided a good starting base and/or some ideas.

Answer 19

Short answer: based on the context, I can't tell whether this is just some quick-and-dirty code for personal use, or a key part of Goldman Sachs' latest internal accounting software, so I'll open by saying: eww. That's a rather funky sorting algorithm; try to use something a bit less "twisty" if you can.

Long answer:

The two issues that immediately come to mind in your case are performance, and correctness. Informally, make sure it's fast, and make sure your algorithm is a total ordering.

(Of course, if you're not sorting more than about 100 items, you can probably disregard this paragraph.) Performance matters, as the speed of the comparator will be the largest factor in the speed of your sort (assuming the sort algorithm is "ideal" to the typical list). In your case, the comparator's speed will depend mainly on the size of the string. The strings seem to be fairly short, so they probably won't dominate as much as the size of your list.

Turning each string into a string-number-string tuple and then sorting this list of tuples, as suggested in another answer, will fail in some of your cases, since you apparently will have strings with multiple numbers appearing.

The other problem is correctness. Specifically, if the algorithm you described will ever permit A > B > ... > A, then your sort will be non-deterministic. In your case, I fear that it might, though I can't prove it. Consider some parsing cases such as:

  aa 0 aa
  aa 23aa
  aa 2a3aa
  aa 113aa
  aa 113 aa
  a 1-2 a
  a 13 a
  a 12 a
  a 2-3 a
  a 21 a
  a 2.3 a

Answer 20

On Linux glibc provides strverscmp(), it's also available from gnulib for portability. However truly "human" sorting has lots of other quirks like "The Beatles" being sorted as "Beatles, The". There is no simple solution to this generic problem.

Answer 21

Ian Griffiths of Microsoft has a C# implementation he calls Natural Sorting. Porting to Java should be fairly easy, easier than from C anyway!

UPDATE: There seems to be a Java example on eekboom that does this, see the "compareNatural" and use that as your comparer to sorts.

Answer 22

If you're writing a comparator class, you should implement your own compare method that will compare two strings character by character. This compare method should check if you're dealing with alphabetic characters, numeric characters, or mixed types (including spaces). You'll have to define how you want a mixed type to act, whether numbers come before alphabetic characters or after, and where spaces fit in etc.

Answer 23

I realize you're in java, but you can take a look at how StrCmpLogicalW works. It's what Explorer uses to sort filenames in Windows. You can look at the WINE implementation here.

Answer 24

I think you'll have to do the comparison on a character-by-character fashion. Grab a character, if it's a number character, keep grabbing, then reassemble to characters into a single number string and convert it into an int. Repeat on the other string, and only then do the comparison.

Answer 25

In your given example, the numbers you want to compare have spaces around them while the other numbers do not, so why would a regular expression not work?

bbb 12 ccc

vs.

eee 12 ddd jpeg2000 eee

Answer 26

Split the string into runs of letters and numbers, so "foo 12 bar" becomes the list ("foo", 12, "bar"), then use the list as the sort key. This way the numbers will be ordered in numerical order, not alphabetical.