Alphanumeric String Sorting In Java (Implementation)

Alphanumeric is a combination of alphabetic and numeric characters (sometimes shortened to alphameric). In computing, the alphanumeric Strings can be seen very common to represent various codes etc.

Sorting the alphanumeric strings can sometimes be a trouble by using regular sort techniques. To have a proper meaning, these characters can neither be sorted numerically or alphabetically alone.

Take an example of following Strings:

“NUM10071″, “NUM9999″, “9997″, “9998″, “9996″, “9996F”

If we Sort them alphabetically, it becomes

9996, 9996F, 9997, 9998,NUM10071, NUM9999

If you observe the last two Strings, NUM10071 has come in front of NUM9999, which might not be the order we wanted to sort to. Considering NUM as the prefix, and that we wanted to sort rest of the numbers in ascending order, the proper meaningful sort would have been as follows:

9996, 9996F, 9997, 9998,NUM9999, NUM10071

If you are storing these codes in a database, writing the SQL to sort these String alphanumerically might be a huge performance issue.

So, in this tutorial, i will present you how to do the alphanumeric sorting in Java language, in a meaningful way.

Before I started writing this code, I had googled over to see the algorithms that could be applied, and I found a page by Sam Allen (http://dotnetperls.com/alphanumeric-sorting) who had implemented the same feature in C# recently.

My solution is inspired by his algorithm and I have converted the solution to Java with some changes. So I would like to appreceiate his work.

Having said that, the following is a properly tested working code that I wrote in Java that can sort Alphanumeric Strings.

package com.kushal.utils;

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

/**
 * @author Kushal Paudyal
 * www.sanjaal.com/java
 * Last Modified On 16th July 2009
 *
 * This class is used to sort alphanumeric strings.
 *
 * My solution is inspired from a similar C# implementation available at
 * http://dotnetperls.com/alphanumeric-sorting written by Sam Allen
 */
public class AlphanumericSorting implements Comparator {
	/**
	 * The compare method that compares the alphanumeric strings
	 */
	public int compare(Object firstObjToCompare, Object secondObjToCompare) {
		String firstString = firstObjToCompare.toString();
		String secondString = secondObjToCompare.toString();

		if (secondString == null || firstString == null) {
			return 0;
		}

		int lengthFirstStr = firstString.length();
		int lengthSecondStr = secondString.length();

		int index1 = 0;
		int index2 = 0;

		while (index1 < lengthFirstStr && index2 < lengthSecondStr) {
			char ch1 = firstString.charAt(index1);
			char ch2 = secondString.charAt(index2);

			char[] space1 = new char[lengthFirstStr];
			char[] space2 = new char[lengthSecondStr];

			int loc1 = 0;
			int loc2 = 0;

			do {
				space1[loc1++] = ch1;
				index1++;

				if (index1 < lengthFirstStr) {
					ch1 = firstString.charAt(index1);
				} else {
					break;
				}
			} while (Character.isDigit(ch1) == Character.isDigit(space1[0]));

			do {
				space2[loc2++] = ch2;
				index2++;

				if (index2 < lengthSecondStr) {
					ch2 = secondString.charAt(index2);
				} else {
					break;
				}
			} while (Character.isDigit(ch2) == Character.isDigit(space2[0]));

			String str1 = new String(space1);
			String str2 = new String(space2);

			int result;

			if (Character.isDigit(space1[0]) && Character.isDigit(space2[0])) {
				Integer firstNumberToCompare = new Integer(Integer
						.parseInt(str1.trim()));
				Integer secondNumberToCompare = new Integer(Integer
						.parseInt(str2.trim()));
				result = firstNumberToCompare.compareTo(secondNumberToCompare);
			} else {
				result = str1.compareTo(str2);
			}

			if (result != 0) {
				return result;
			}
		}
		return lengthFirstStr - lengthSecondStr;
	}

	/**
	 * Testing the alphanumeric sorting
	 */
	public static void main(String[] args) {
		String[] alphaNumericStringArray = new String[] { "NUM10071",
				"NUM9999", "9997", "9998", "9996", "9996F" };

		/*
		 * Arrays.sort method can take an unsorted array and a comparator
		 * to give a final sorted array.
		 *
		 * The sorting is done according to the comparator that we have
		 * provided.
		 */
		Arrays.sort(alphaNumericStringArray, new AlphanumericSorting());

		for (int i = 0; i < alphaNumericStringArray.length; i++) {
			System.out.println(alphaNumericStringArray[i]);
		}

	}

}

=================
Here is the output:

9996
9996F
9997
9998
NUM9999
NUM10071

Originally posted 2009-07-16 09:14:48.