Home Communities
IT Knowledge
Inspiration
Languages
EN

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

10 points
Created by:
371

## 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);

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]``````