Thursday
Dec 31, 2009
1:11 pm
Javascript Sorting
Not too long ago, I was asked, as a theoretical question, how I might take a string of random alphabetical characters and sort them in order using Javascript. Thus, given NFARAKDMSLSJDQKJKCXLK, find a simple way to turn it into AACDDFJJKKKKLLMNQRSSX. It’s a pretty basic question for anyone who uses Javascript and I immediately thought of splitting and joining the string as an array (a quick and easy way to tokenize the string). However, for some reason, I completely forgot about the Array.sort() function that’s pretty much a universal across languages.
Instead, the first thing that came to mind was the last time I had to sort a collection and started thinking of Java sorting. In the work I’ve done, such sorting usually requires the use of comparators because the default sort order is often not the one that’s desired. As a case in point, we have a set of JSP pages for rendering content including archive and list pages that display in posting date or sequence order derived from the content. For example, here’s some code to sort by a custom “sequence” attribute using the Vignette Content Management API (this particular snippet is the work of the inimitable Yong Chen):
Comparator aComparator = new Comparator(){ public int compare(Object obj1, Object obj2) { int result=0; try { Integer s1 = (Integer) ((ContentInstance) obj1).getRelations(CT_RELATION_HEALTH_PLAN)[0].getAttribute("sequence").getValue(); Integer s2 = (Integer) ((ContentInstance) obj2).getRelations(CT_RELATION_HEALTH_PLAN)[0].getAttribute("sequence").getValue(); result=s1.compareTo(s2); } catch (com.vignette.as.client.exception.ApplicationException e) { } return result; } };
For debugging, I might break it out a little differently to avoid the multiple casts in a single line. I think the Vignette API is fairly robust, but I would still split the ContentInstance cast apart from the Java native Integer cast in this case. But that might just be me.
In any event, while Javascript can also use comparators without much loss of speed, for a task like the one delineated initially, a simple sort will do the job and the whole can even be condensed to a single line function like this:
function order(unsortedString) { return unsortedString.split("").sort().join(""); }
Depending on the browser, the sort function will be some variation on a quick sort or a merge sort. It depends on whether the browser architects chose a stable algorithm or opted for some other version based on various considerations. Mozilla used to use a quicksort prior to Firefox 3.5, but they opted for a merge sort instead in more recent versions. In the course of reading about sort implementations, I came across notes on timsort, Python’s default sort implementation, that I found particularly intriguing.
As an aside the return value for a comparator that works in Firefox may fail with Webkit (Chrome and Safari) since you need to return -1 instead of zero (and a boolean false will also fail). You can read more about Webkit’s Array.sort() handling.
With Java, it looks like this:
String unsorted = "xzya"; char[] content = unsorted.toCharArray(); java.util.Arrays.sort(content); String sorted = new String(content);
With Perl, you can do something like:
print (join “”, sort split //,$_)
In bash, this will do the same job:
echo “teststring” | grep -o . | sort -n |tr -d ‘\n’; echo
All in all, not only did I refresh my memory about good ways to sort strings and arrays in Javascript, I also learned some new things about sort algorithms and implementations of those algorithms.
