Languages
[Edit]
EN

Java - how to sort alphanumeric array of Strings - natural order sorting

10 points
Created by:
Marcin
15710

1. Overview

How do I sort {"10", "1", "2"} into {"1", "2", "10"}

Example:

String[] original = {"10", "1", "2"}; // I have
String[] sorted   = {"1", "2", "10"}; // expected

Problem with default Arrays.sort

// When I use:
String[] original = {"10", "1", "2"};
Arrays.sort(original);
// I get:
System.out.println(Arrays.toString(original)); // [1, 10, 2]

2. Alphanumeric Sort Comparator code

import java.util.Comparator;

// Java alphanumeric sort
// unsorted array:     [10, 1, 2]
// simple Arrays.sort: [1, 10, 2]
// alphanumeric sort:  [1, 2, 10]
//
public final class AlphanumericSortComparator<T> implements  Comparator<T> {

    public static final Comparator<String> NUMERICAL_ORDER
            = new AlphanumericSortComparator<>(false);
    public static final Comparator<String> CASE_INSENSITIVE_NUMERICAL_ORDER
            = new AlphanumericSortComparator<>(true);

    private final boolean caseInsensitive;

    private AlphanumericSortComparator(boolean caseInsensitive) {
        this.caseInsensitive = caseInsensitive;
    }

    int compareRight(String a, String b) {
        int bias = 0;
        int ia = 0;
        int ib = 0;

        // The longest run of digits wins.  That aside, the greatest
        // value wins, but we can't know that it will until we've scanned
        // both numbers to know that they have the same magnitude, so we
        // remember it in BIAS.
        for (;; ia++, ib++) {
            char ca = charAt(a, ia);
            char cb = charAt(b, ib);

            if (!Character.isDigit(ca) && !Character.isDigit(cb)) {
                return bias;
            } else if (!Character.isDigit(ca)) {
                return -1;
            } else if (!Character.isDigit(cb)) {
                return +1;
            } else if (ca < cb) {
                if (bias == 0) {
                    bias = -1;
                }
            } else if (ca > cb) {
                if (bias == 0)
                    bias = +1;
            } else if (ca == 0 && cb == 0) {
                return bias;
            }
        }
    }

    public int compare(T o1, T o2) {
        String a = o1.toString();
        String b = o2.toString();

        int ia = 0, ib = 0;
        int nza = 0, nzb = 0;
        char ca, cb;
        int result;

        while (true) {
            // only count the number of zeroes leading the last number compared
            nza = nzb = 0;

            ca = charAt(a, ia);
            cb = charAt(b, ib);

            // skip over leading zeros
            while (ca == '0') {
                if (ca == '0') {
                    nza++;
                } else {
                    // only count consecutive zeroes
                    nza = 0;
                }

                // if the next character isn't a digit, then we've had a run
                // of only zeros
                // we still need to treat this as a 0 for comparison purposes
                if (!Character.isDigit(charAt(a, ia+1)))
                    break;

                ca = charAt(a, ++ia);
            }

            while (cb == '0') {
                if (cb == '0') {
                    nzb++;
                } else {
                    // only count consecutive zeroes
                    nzb = 0;
                }

                // if the next character isn't a digit, then we've had a run
                // of only zeros
                // we still need to treat this as a 0 for comparison purposes
                if (!Character.isDigit(charAt(b, ib+1)))
                    break;

                cb = charAt(b, ++ib);
            }

            // process run of digits
            if (Character.isDigit(ca) && Character.isDigit(cb)) {
                if ((result = compareRight(a.substring(ia), b
                        .substring(ib))) != 0) {
                    return result;
                }
            }

            if (ca == 0 && cb == 0) {
                // The strings compare the same.  Perhaps the caller
                // will want to call strcmp to break the tie.
                return nza - nzb;
            }

            if (ca < cb) {
                return -1;
            } else if (ca > cb) {
                return +1;
            }

            ++ia;
            ++ib;
        }
    }

    private char charAt(String s, int i) {
        if (i >= s.length()) {
            return 0;
        } else {
            return caseInsensitive ?
                    Character.toUpperCase(s.charAt(i)) : s.charAt(i);
        }
    }
}

3. Alphanumeric Sort - simple example

Code example: 

import java.util.Arrays;
import java.util.Comparator;

public class JavaSortSortAlphanumericStringExample1 {

    public static void main(String[] args) {

        Comparator<String> numericalOrder
                = AlphanumericSortComparator.NUMERICAL_ORDER;

        {
            String[] arr = {"10", "1", "2"};
            System.out.println("# Example 1");
            // [10, 1, 2]
            System.out.println(Arrays.toString(arr));
            Arrays.sort(arr);
            // [1, 10, 2]
            System.out.println(Arrays.toString(arr));
        }

        {
            String[] arr = {"10", "1", "2"};
            System.out.println("# Example 2");
            // [10, 1, 2]
            System.out.println(Arrays.toString(arr));
            Arrays.sort(arr, numericalOrder);
            // [1, 2, 10]
            System.out.println(Arrays.toString(arr));
        }
    }
}


Output:

# Example 1
[10, 1, 2]
[1, 10, 2]
# Example 2
[10, 1, 2]
[1, 2, 10]

4. Alphanumeric Sort - complex example

Code example: 

import java.util.Arrays;
import java.util.Comparator;

public class JavaSortSortAlphanumericStringExample2 {

    public static void main(String[] args) {

        Comparator<String> numericalOrder
                = AlphanumericSortComparator.NUMERICAL_ORDER;

        {
            String[] arr = {
                    "ABC_2",
                    "ABC_11",
                    "ABC_1",
                    "ABC_12",
                    "ABC_22",
                    "ABC_5",
                    "ABC_3",
                    "ABC_21"
            };

            System.out.println("# Example 1");

            // [ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]
            System.out.println(Arrays.toString(arr));

            Arrays.sort(arr);

            // [ABC_1, ABC_11, ABC_12, ABC_2, ABC_21, ABC_22, ABC_3, ABC_5]
            System.out.println(Arrays.toString(arr));
        }

        {
            String[] arr = {
                    "ABC_2",
                    "ABC_11",
                    "ABC_1",
                    "ABC_12",
                    "ABC_22",
                    "ABC_5",
                    "ABC_3",
                    "ABC_21"
            };

            System.out.println("# Example 2");

            // [ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]
            System.out.println(Arrays.toString(arr));

            Arrays.sort(arr, numericalOrder);

            // [ABC_1, ABC_2, ABC_3, ABC_5, ABC_11, ABC_12, ABC_21, ABC_22]
            System.out.println(Arrays.toString(arr));
        }
    }
}

Output:

# Example 1
[ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]
[ABC_1, ABC_11, ABC_12, ABC_2, ABC_21, ABC_22, ABC_3, ABC_5]
# Example 2
[ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]
[ABC_1, ABC_2, ABC_3, ABC_5, ABC_11, ABC_12, ABC_21, ABC_22]

5. Alphanumeric Sort case insensitive numerical order example

Code example:

import java.util.Arrays;
import java.util.Comparator;

public class JavaSortSortAlphanumericStringExample3 {

    public static void main(String[] args) {

        Comparator<String> numericalOrder
                = AlphanumericSortComparator.NUMERICAL_ORDER;

        Comparator<String> caseInsensitiveNumericalOrder
                = AlphanumericSortComparator.CASE_INSENSITIVE_NUMERICAL_ORDER;

        {
            String[] arr = {
                    "abc_2",
                    "abc_11",
                    "abc_1",
                    "ABC_12",
                    "ABC_22",
                    "abc_5",
                    "ABC_3",
                    "ABC_21"
            };

            System.out.println("# Example 1");

            // [abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]
            System.out.println(Arrays.toString(arr));

            Arrays.sort(arr);

            // [ABC_12, ABC_21, ABC_22, ABC_3, abc_1, abc_11, abc_2, abc_5]
            System.out.println(Arrays.toString(arr));
        }

        {
            String[] arr = {
                    "abc_2",
                    "abc_11",
                    "abc_1",
                    "ABC_12",
                    "ABC_22",
                    "abc_5",
                    "ABC_3",
                    "ABC_21"
            };
            System.out.println("# Example 2");

            // [abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]
            System.out.println(Arrays.toString(arr));

            Arrays.sort(arr, numericalOrder);

            // [ABC_3, ABC_12, ABC_21, ABC_22, abc_1, abc_2, abc_5, abc_11]
            System.out.println(Arrays.toString(arr));
        }

        {
            String[] arr = {
                    "abc_2",
                    "abc_11",
                    "abc_1",
                    "ABC_12",
                    "ABC_22",
                    "abc_5",
                    "ABC_3",
                    "ABC_21"
            };

            System.out.println("# Example 3");

            // [abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]
            System.out.println(Arrays.toString(arr));

            Arrays.sort(arr, caseInsensitiveNumericalOrder);

            // [abc_1, abc_2, ABC_3, abc_5, abc_11, ABC_12, ABC_21, ABC_22]
            System.out.println(Arrays.toString(arr));
        }
    }
}

Output:

# Example 1
[abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]
[ABC_12, ABC_21, ABC_22, ABC_3, abc_1, abc_11, abc_2, abc_5]
# Example 2
[abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]
[ABC_3, ABC_12, ABC_21, ABC_22, abc_1, abc_2, abc_5, abc_11]
# Example 3
[abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]
[abc_1, abc_2, ABC_3, abc_5, abc_11, ABC_12, ABC_21, ABC_22]

Merged questions

  1. Java - how do I sort String[] in natural order?
  2. Java - sort alphanumeric array of Strings
  3. Java - how to sort alphanumeric array of Strings when Arrays.sort does not work eg 1 10 2 vs 1 2 10?

References

  1. Natural sort order - wiki
Native Advertising
50 000 ad impressions - 449$
🚀
Get your tech brand or product in front of software developers.
For more information contact us:
Red dot
Dirask - friendly IT community for everyone.

❤️💻 🙂

Join