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

Insertion Sort Implementation In Java – Working Code Example

Insertion Sort Animation. Image Credit: Wikipedia / Creative Commons

Algorithm:

  • Take one element, compare with the one next to it and put in the order it belongs to, thus forming a partially sorted list.
  • Iterate through the list, one item at a time until no input elements remain.

Pseudo code is given below:

for i ← 1 to length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1

Complexity:

  • Best Case: O(n) – For already sorted list
  • Average Case: O(n^2)
  • Worst Case: O(n^2)

Notes / Usage:

  • Insertion Sort is:
    • Stable
    • Takes O(1) extra space for swapping
    • In-Place Sorting – No extra memory is required
  • One real life usage of this kind of sorting is sorting a deck of cards.

Java Implementation Code:

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
* @author Kushal Paudyal
* www.icodejava.com
* Created On -  Feb 26, 2014
* Last Modified On - Feb 26, 2014
*/
public class InsertionSort {

public static void main(String args[]) {
    int[] numberArray = { 5, 4, 7, 3, 3, 9, 0, 1, 2, 8, 6, -5 };

    sort(numberArray);

}

public static void sort(int[] numberArray) {

     System.out.println("Input Array: " + Arrays.toString(numberArray));

     for (int i = 1; i < numberArray.length; i++) { 			
         for (int j = i; j > 0; j--) {
             // Start comparing data with adjacent one and swap if smaller
             if (numberArray[j] < numberArray[j - 1]) {
             swap(numberArray, j, j - 1);
         }
     }
}

System.out.println("Sorted Array: " + Arrays.toString(numberArray));

}

/**
* Swaps data from an array.
*/
private static void swap(int[] array, int firstIndex, int secondIndex) {
   if (array == null || firstIndex < 0 || firstIndex > array.length 
     || secondIndex < 0 || secondIndex > array.length) {
    return;
   }
   int temp = array[firstIndex];
   array[firstIndex] = array[secondIndex];
   array[secondIndex] = temp;

}

}


Output of running above program:

Input Array: [5, 4, 7, 3, 3, 9, 0, 1, 2, 8, 6, -5]
Sorted Array: [-5, 0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9]

Quick Sort Implementation In Java – Working Sample Code Example

Quick Sort is a sorting technique which uses Divide and Conquer mechanism to do the sorting. The algorithm for Quick Sort which is also sometimes known with it’s alternative name of “Partition Exchange Sort” is given below:

Quick Sort Algorithm:

  1. Pick an element from the list as Pivot, usually the middle one.
  2. Re-arrange elements with elements smaller than pivot on one side and greater that pivot on the other side.
  3. Recursively apply this to the smaller partition and larger partitions separately.

Algorithm Complexity:

  • Best Case: nlogn
  • Worst Case: n^2
  • Average Case: nlogn

Java Implementation:

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 24, 2014
 * Last Modified On - Feb 24, 2014
 */
public class QuickSort {

	public static void main(String args[]) {
		int[] items = { 0, 5, -1, 2, 3, 9, 7, 12, 5, 4 };
		sort(items);
	}

	public static void sort(int[] items) {
		if (items == null || items.length <= 0) {
			return;
		}

		System.out.println("Input Array: " + Arrays.toString(items));
		quickSort(items, 0, items.length - 1);
		System.out.println("Sorted Array: " + Arrays.toString(items));

	}
	
	/**
	 * Recursively apply quickSort - one for partition smaller than pivot -
	 * another for partition bigger than pivot
	 */
	public static void quickSort(int items[], int start, int end) {
		if (start >= end) {
			return;
		}

		int pivot = partition(items, start, end);

		if (start < pivot - 1) {
			quickSort(items, start, pivot - 1);
		}

		if (end > pivot) {

			quickSort(items, pivot, end);
		}

		
	}

	/**
	 * Reorganizes the given list so all elements less than the first are before
	 * it and all greater elements are after it.
	 */
	private static int partition(int[] items, int start, int end) {

		int pivot = items[(start + end) / 2];
		while (start <= end) {
			while (items[start] < pivot) {
				start++;
			}
			while (items[end] > pivot) {
				end--;
			}

			if (start <= end) {
				swap(items, start, end);
				start++;
				end--;
			}
		}
		return start;

	}



	/**
	 * Swaps data from an array. 
	 */
	private static void swap(int[] array, int firstIndex, int secondIndex) {
		if (array == null || firstIndex < 0 || firstIndex > array.length
				|| secondIndex < 0 || secondIndex > array.length) {
			return;
		}
		int temp = array[firstIndex];
		array[firstIndex] = array[secondIndex];
		array[secondIndex] = temp;

	}

}

The output of running above program is:

Input Array: [0, 5, -1, 2, 3, 9, 7, 12, 5, 4]
Sorted Array: [-1, 0, 2, 3, 4, 5, 5, 7, 9, 12]