How to sort Alpha Numeric Strings in Java

[NOTE: This article was originally published in my another blog and has been migrated over here]

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 appreciate 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.icodejava.com
 * 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


Update:
I got an email from one of the readers asking me if I could modify the program above so that it would treat zero padded numbers as the same such as “01”, “001” or “1” would be the same. The following is a modified version of this program that can do this. I just added a method to remove padding in the comparator.

Hello, first off, thank you for the code at: http://sanjaal.com/java/tag/sample-alphanumeric-sorting/ It is great to finally find a comparator that actually sorts 0,1,2,3,…10,12,20,…etc. The one problem is it also sorts 0,1,01,02,2,3,4…etc. Is there anyway you could update it to recognize the initial zeros and ignore them so that 000001 would be treated as 1? Again, many thanks and hope to hear back from you!

package com.kushal.utils;

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

/**
 * @author Kushal Paudyal www.icodejava.com 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 = removePadding(firstObjToCompare.toString());
		String secondString = removePadding(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;
	}

	/**
	 * The purpose of this method is to remove any zero padding for numbers.
	 * 
	 * Otherwise returns the input string.
	 * 
	 * 
	 * @param string
	 * @return
	 */
	private String removePadding(String string) {
		String result="";
		try{
			result+= Integer.parseInt(string.trim());
		} catch (Exception e) {
			result= string;
		}
		return result;
	}

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

		/*
		 * 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]);
		}

	}

}

Following is the output of running this program. Note that the zero padded elements of equal value are sorted as stable meaning they appear in the same order as the input.

0001
01
1
001
9996
9996F
9997
9998

Tagged , , , , , , . Bookmark the permalink.

One Response to Bubble Sorting A String Array in Ascending And Descending Order

  1. Ririn says:

    Thanks buat script codenya, membantu saya mengerkajan tugas saya

Leave a Reply

Your email address will not be published. Required fields are marked *