EN
Java - how to sort alphanumeric array of Strings - natural order sorting
10 points
How do I sort {"10", "1", "2"} into {"1", "2", "10"}
Example:
xxxxxxxxxx1
String[] original = {"10", "1", "2"}; // I have2
String[] sorted = {"1", "2", "10"}; // expectedProblem with default Arrays.sort
xxxxxxxxxx1
// When I use:2
String[] original = {"10", "1", "2"};3
Arrays.sort(original);4
// I get:5
System.out.println(Arrays.toString(original)); // [1, 10, 2]xxxxxxxxxx1
import java.util.Comparator;2
3
// Java alphanumeric sort4
// unsorted array: [10, 1, 2]5
// simple Arrays.sort: [1, 10, 2]6
// alphanumeric sort: [1, 2, 10]7
//8
public final class AlphanumericSortComparator<T> implements Comparator<T> {9
10
public static final Comparator<String> NUMERICAL_ORDER11
= new AlphanumericSortComparator<>(false);12
public static final Comparator<String> CASE_INSENSITIVE_NUMERICAL_ORDER13
= new AlphanumericSortComparator<>(true);14
15
private final boolean caseInsensitive;16
17
private AlphanumericSortComparator(boolean caseInsensitive) {18
this.caseInsensitive = caseInsensitive;19
}20
21
int compareRight(String a, String b) {22
int bias = 0;23
int ia = 0;24
int ib = 0;25
26
// The longest run of digits wins. That aside, the greatest27
// value wins, but we can't know that it will until we've scanned28
// both numbers to know that they have the same magnitude, so we29
// remember it in BIAS.30
for (;; ia++, ib++) {31
char ca = charAt(a, ia);32
char cb = charAt(b, ib);33
34
if (!Character.isDigit(ca) && !Character.isDigit(cb)) {35
return bias;36
} else if (!Character.isDigit(ca)) {37
return -1;38
} else if (!Character.isDigit(cb)) {39
return +1;40
} else if (ca < cb) {41
if (bias == 0) {42
bias = -1;43
}44
} else if (ca > cb) {45
if (bias == 0)46
bias = +1;47
} else if (ca == 0 && cb == 0) {48
return bias;49
}50
}51
}52
53
public int compare(T o1, T o2) {54
String a = o1.toString();55
String b = o2.toString();56
57
int ia = 0, ib = 0;58
int nza = 0, nzb = 0;59
char ca, cb;60
int result;61
62
while (true) {63
// only count the number of zeroes leading the last number compared64
nza = nzb = 0;65
66
ca = charAt(a, ia);67
cb = charAt(b, ib);68
69
// skip over leading zeros70
while (ca == '0') {71
if (ca == '0') {72
nza++;73
} else {74
// only count consecutive zeroes75
nza = 0;76
}77
78
// if the next character isn't a digit, then we've had a run79
// of only zeros80
// we still need to treat this as a 0 for comparison purposes81
if (!Character.isDigit(charAt(a, ia+1)))82
break;83
84
ca = charAt(a, ++ia);85
}86
87
while (cb == '0') {88
if (cb == '0') {89
nzb++;90
} else {91
// only count consecutive zeroes92
nzb = 0;93
}94
95
// if the next character isn't a digit, then we've had a run96
// of only zeros97
// we still need to treat this as a 0 for comparison purposes98
if (!Character.isDigit(charAt(b, ib+1)))99
break;100
101
cb = charAt(b, ++ib);102
}103
104
// process run of digits105
if (Character.isDigit(ca) && Character.isDigit(cb)) {106
if ((result = compareRight(a.substring(ia), b107
.substring(ib))) != 0) {108
return result;109
}110
}111
112
if (ca == 0 && cb == 0) {113
// The strings compare the same. Perhaps the caller114
// will want to call strcmp to break the tie.115
return nza - nzb;116
}117
118
if (ca < cb) {119
return -1;120
} else if (ca > cb) {121
return +1;122
}123
124
++ia;125
++ib;126
}127
}128
129
private char charAt(String s, int i) {130
if (i >= s.length()) {131
return 0;132
} else {133
return caseInsensitive ?134
Character.toUpperCase(s.charAt(i)) : s.charAt(i);135
}136
}137
}138
Code example:
xxxxxxxxxx1
import java.util.Arrays;2
import java.util.Comparator;3
4
public class JavaSortSortAlphanumericStringExample1 {5
6
public static void main(String[] args) {7
8
Comparator<String> numericalOrder9
= AlphanumericSortComparator.NUMERICAL_ORDER;10
11
{12
String[] arr = {"10", "1", "2"};13
System.out.println("# Example 1");14
// [10, 1, 2]15
System.out.println(Arrays.toString(arr));16
Arrays.sort(arr);17
// [1, 10, 2]18
System.out.println(Arrays.toString(arr));19
}20
21
{22
String[] arr = {"10", "1", "2"};23
System.out.println("# Example 2");24
// [10, 1, 2]25
System.out.println(Arrays.toString(arr));26
Arrays.sort(arr, numericalOrder);27
// [1, 2, 10]28
System.out.println(Arrays.toString(arr));29
}30
}31
}
Output:
xxxxxxxxxx1
# Example 12
[10, 1, 2]3
[1, 10, 2]4
# Example 25
[10, 1, 2]6
[1, 2, 10]Code example:
xxxxxxxxxx1
import java.util.Arrays;2
import java.util.Comparator;3
4
public class JavaSortSortAlphanumericStringExample2 {5
6
public static void main(String[] args) {7
8
Comparator<String> numericalOrder9
= AlphanumericSortComparator.NUMERICAL_ORDER;10
11
{12
String[] arr = {13
"ABC_2",14
"ABC_11",15
"ABC_1",16
"ABC_12",17
"ABC_22",18
"ABC_5",19
"ABC_3",20
"ABC_21"21
};22
23
System.out.println("# Example 1");24
25
// [ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]26
System.out.println(Arrays.toString(arr));27
28
Arrays.sort(arr);29
30
// [ABC_1, ABC_11, ABC_12, ABC_2, ABC_21, ABC_22, ABC_3, ABC_5]31
System.out.println(Arrays.toString(arr));32
}33
34
{35
String[] arr = {36
"ABC_2",37
"ABC_11",38
"ABC_1",39
"ABC_12",40
"ABC_22",41
"ABC_5",42
"ABC_3",43
"ABC_21"44
};45
46
System.out.println("# Example 2");47
48
// [ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]49
System.out.println(Arrays.toString(arr));50
51
Arrays.sort(arr, numericalOrder);52
53
// [ABC_1, ABC_2, ABC_3, ABC_5, ABC_11, ABC_12, ABC_21, ABC_22]54
System.out.println(Arrays.toString(arr));55
}56
}57
}Output:
xxxxxxxxxx1
# Example 12
[ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]3
[ABC_1, ABC_11, ABC_12, ABC_2, ABC_21, ABC_22, ABC_3, ABC_5]4
# Example 25
[ABC_2, ABC_11, ABC_1, ABC_12, ABC_22, ABC_5, ABC_3, ABC_21]6
[ABC_1, ABC_2, ABC_3, ABC_5, ABC_11, ABC_12, ABC_21, ABC_22]Code example:
xxxxxxxxxx1
import java.util.Arrays;2
import java.util.Comparator;3
4
public class JavaSortSortAlphanumericStringExample3 {5
6
public static void main(String[] args) {7
8
Comparator<String> numericalOrder9
= AlphanumericSortComparator.NUMERICAL_ORDER;10
11
Comparator<String> caseInsensitiveNumericalOrder12
= AlphanumericSortComparator.CASE_INSENSITIVE_NUMERICAL_ORDER;13
14
{15
String[] arr = {16
"abc_2",17
"abc_11",18
"abc_1",19
"ABC_12",20
"ABC_22",21
"abc_5",22
"ABC_3",23
"ABC_21"24
};25
26
System.out.println("# Example 1");27
28
// [abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]29
System.out.println(Arrays.toString(arr));30
31
Arrays.sort(arr);32
33
// [ABC_12, ABC_21, ABC_22, ABC_3, abc_1, abc_11, abc_2, abc_5]34
System.out.println(Arrays.toString(arr));35
}36
37
{38
String[] arr = {39
"abc_2",40
"abc_11",41
"abc_1",42
"ABC_12",43
"ABC_22",44
"abc_5",45
"ABC_3",46
"ABC_21"47
};48
System.out.println("# Example 2");49
50
// [abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]51
System.out.println(Arrays.toString(arr));52
53
Arrays.sort(arr, numericalOrder);54
55
// [ABC_3, ABC_12, ABC_21, ABC_22, abc_1, abc_2, abc_5, abc_11]56
System.out.println(Arrays.toString(arr));57
}58
59
{60
String[] arr = {61
"abc_2",62
"abc_11",63
"abc_1",64
"ABC_12",65
"ABC_22",66
"abc_5",67
"ABC_3",68
"ABC_21"69
};70
71
System.out.println("# Example 3");72
73
// [abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]74
System.out.println(Arrays.toString(arr));75
76
Arrays.sort(arr, caseInsensitiveNumericalOrder);77
78
// [abc_1, abc_2, ABC_3, abc_5, abc_11, ABC_12, ABC_21, ABC_22]79
System.out.println(Arrays.toString(arr));80
}81
}82
}Output:
xxxxxxxxxx1
# Example 12
[abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]3
[ABC_12, ABC_21, ABC_22, ABC_3, abc_1, abc_11, abc_2, abc_5]4
# Example 25
[abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]6
[ABC_3, ABC_12, ABC_21, ABC_22, abc_1, abc_2, abc_5, abc_11]7
# Example 38
[abc_2, abc_11, abc_1, ABC_12, ABC_22, abc_5, ABC_3, ABC_21]9
[abc_1, abc_2, ABC_3, abc_5, abc_11, ABC_12, ABC_21, ABC_22]