EN
Java - how to sort alphanumeric array of Strings - natural order sorting
10
points
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
- Java - how do I sort String[] in natural order?
- Java - sort alphanumeric array of Strings
- Java - how to sort alphanumeric array of Strings when Arrays.sort does not work eg 1 10 2 vs 1 2 10?