Aug
7

Alphanumeric Sorting in AS3 Paul

Actionscript

Sorting a list of strings that contain numbers (alphanumeric strings) can be a major headache in AS3. Lets say you have a list of five filenames you want to sort and display in a datagrid.

var filenames : Array = [
"range106.xml",
"range1.xml",
"range11.xml",
"range9.xml",
"range12.xml"];
filenames.sort();
trace(filenames);

You end up with this:

"range1.xml"
"range106.xml"
"range11.xml"
"range12.xml"
"range9.xml"

What? Thats not right! What is going on here?

To a computer this looks correct, but because computers interpret text differently than humans it looks wrong to us. If you read down the list of filenames one letter at a time you can see how the computer is sorting our strings, comparing one character against another until it finds a pair that are different and then sorting based on that. This is how “range106.xml” ends up above “range11.xml”. In the 7th column, 0 is less than 1.

Since we’re not computers, we actually interpret the filenames above as two discrete pieces of information; the word “range” and the number following it. Clearly the built method of sorting strings isn’t going to solve this problem for us. We’ll need to come up with an algorithm to sort alphanumeric strings ourselves.

After some Googling I discovered that such an algorithm already exists (they usually do!) and was written by Dave Koelle way back in 1997. He has the algorithm implemented in a healthy list of languages, but AS3 was nowhere to be found.

After a trivial port from the Java version I had a working alpha numeric sort in ActionScript:

public class AlphaNumericSort 
{
	private static function isDigit(ch : String) : Boolean
	{
		var code : int = ch.charCodeAt( 0 );
		return code >= 48 && code <= 57;
	}

	/** Length of string is passed in for improved efficiency (only need to calculate it once) **/
	private static function getChunk(s : String, slength : int, marker : int) : String
	{
		var result : String = "";
		var c : String = s.charAt( marker );
		result += c;
		marker++;
		if (isDigit( c ))
		{
			while (marker < slength)
			{
				c = s.charAt( marker );
				if (!isDigit( c ))
				{
					break;
				}
				result += c ;
				marker++;
			}
		} 
		else
		{
			while (marker < slength)
			{
				c = s.charAt( marker );
				if (isDigit( c ))
				{
					break;
				}
				result += c;
				marker++;
			}
		}
		return result;
	}
	
	/**
	 * Comparison function to sort a list of Strings alphanumerically.
	 */
	public static function compare(s1 : String, s2 : String) : int
	{
		var thisMarker : int = 0;
		var thatMarker : int = 0;
		var s1Length : int = s1.length;
		var s2Length : int = s2.length;

		while (thisMarker < s1Length && thatMarker < s2Length)
		{
			var thisChunk : String = getChunk( s1, s1Length, thisMarker );
			thisMarker += thisChunk.length;

			var thatChunk : String = getChunk( s2, s2Length, thatMarker );
			thatMarker += thatChunk.length;

			// If both chunks contain numeric characters, sort them numerically
			var result : int = 0;
			if (isDigit( thisChunk.charAt( 0 ) ) && isDigit( thatChunk.charAt( 0 ) ))
			{
				// Simple chunk comparison by length.
				var thisChunkLength : int = thisChunk.length;
				result = thisChunkLength - thatChunk.length;
				// If equal, the first different number counts
				if (result == 0)
				{
					for (var i : int = 0; i < thisChunkLength; i++)
					{
						result = thisChunk.charCodeAt( i ) - thatChunk.charCodeAt( i );
						if (result != 0)
						{
							return result;
						}
					}
				}
			} 
			else
			{
				if (thisChunk < thatChunk) 
				{ 
					result = -1; 
				} 
				else if (thisChunk > thatChunk) 
				{ 
					result = 1; 
				} 
				else 
				{ 
					result = 0; 
				}
			}

			if (result != 0)
			{
				return result;
			}
		}

		return s1Length - s2Length;
	}
}

Using the same example as above, lets re-sort our list using the custom comparison function.

var filenames : Array = ["range106.xml","range1.xml","range11.xml","range9.xml","range12.xml"];
filenames.sort(AlphaNumericSort.compare);
trace(filenames);

Success? You betcha!

"range1.xml"
"range9.xml"
"range11.xml"
"range12.xml"
"range106.xml"

In the words of Enzo from Reboot, “Whoa! Alphanumeric!”

You can download the AS3 AlphaNumericSort method here. Please feel free to contact me at plemarquand (at) gmail (dot) com if you encounter any bugs. All credit goes to Dave Koelle for the original implementation!

License: LGPL – Free to use and distribute

This entry was posted on Saturday, August 7th, 2010 at 10:08 am and is filed under Actionscript. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.