 |
This page is being moved The latest version of this page is available at http://www.davekoelle.com/alphanum.html |
The Alphanum Algorithm
Standard alphanumeric sorting algorithms sort numbers by ASCII value, not by numeric value. This produces unacceptable results that are confusing to new software users. The Alphanum Algorithm sorts alphanumerics in the more traditional and expected order.
The Problem
Standard alphabetic sorting algorithms have a major shortcoming: They put numeric strings in ASCII order instead of numeric order. In ASCII order, "1000" comes before "2"... and "399" is followed by "4", then by "40", then by "400". Many people have grown accustomed to this, but as software becomes increasingly utilized by nontechnical people, this type of ordering is unacceptable.
The Solution
I created the Alphanum Algorithm to solve this problem. The Alphanum Algorithm sorts numeric values in numeric order, while still sorting strings in ASCII order. It works equally well with mixed strings: "PC Series 5000" and "PC Series 600" will sort as numerically expected.
Implementation
I have implemented the Alphanum algorithm as a Java Comparator: AlphanumComparator.java.
To use a comparator
to sort a list, use the static sort(List,Comparator)
method of java.util.Collections. You may also use the
Perl and C++ versions. These programs may be used freely as long as they are kept
intact, including comments.
Demonstration
Here's a side-by-side comparison of the standard ASCII sort and the Alphanum sort. Which do you like better? Which do you think your customers or users would like better?
Discussion
Take a look through the sorted lists above. You will notice that the standard sort gets into trouble with the first few data items. The 10X model should preceed the 1000X model, and the 20X model should preceed the 200X model! Imagine if this were a catalog of your machines or levels of service -- which ordering do you think would instill more trust among your viewers?
We see the same ordering problems with the "Allegia" systems, followed by the "Alpha" systems. My favorite examples in these lists are the "Xiph Xlater" systems. The standard sort has all of them sorted incorrectly! Finally at the end is a list of 60 filenames. The standard-sort list ends in "z9.html", whereas the Alphanum-sort list ends with the actual largest-valued filename, "z130.html".
Disclaimer: Sorting requires the java.util.Collections class, which was introduced in JDK1.2 (known by the marketing name "Java2"), which is not the lowest common denominator for Java implementations in Web browsers. To make this demo available to the largest possible audience, the applet above is not actually performing the sorting - I've cut and pasted the values from an actual run of the following applet, which you may run in your Java AppletViewer: alphanum.zip (contains AlphanumComparator.java, two demo applets, and HTML pages for running the demo applets).
How it Works
The algorithm breaks strings into chunks, where a chunk contains either all alphabetic characters, or all numeric characters. These chunks are then compared against each other. If both chunks contain numbers, a numerical comparison is used. If either chunk contains characters, the ASCII comparison is used.
Computational Cost
The applet above also shows how much time it takes to sort the list: Approximately 10ms for a standard sort, and 40ms for the Alphanum sort. The list contains 100 items. While it takes a little longer to sort the list using Alphanum, the difference is minimal and nearly unnoticable. This algorithm might have been too costly for computers in the past, but today the computational cost is not an issue.
Conclusion
Wouldn't it be great if the applications sorted lists in an expected, natural order? Do your part in making software and websites more usable, use this algorithm to sort lists appropriately!