9.1.08 Javascript Natural Sort Algorithm With Unicode Support

PROBLEM
Javascript is not capable of sorting Array’s that contain strings and numeric values as human readable.

SOLUTION Added in Version 0.2
Here’s a very simple “Natural Sort” implementation in 11 lines of Javascript code that shares the same core “chunking” concept as displayed in many implementations that appears to have been first adopted by Dave Koelle. The earliest concept of this type of parsing I’ve seen/worked with was String Tokenization aka Lexical Analysis.

DATE SORTING SUPPORT
Finally added the ability to sort off Date objects based off the .getTime() unix epoch timestamp comparisons. This will only work against valuation of fields that in their entirety can instantiate a valid Date object via the Date constructor. This means that any valid input string that can create a date via the Date constructor, i.e. new Date('10/10/2005') or new Date('Tue Sep 09 2008 20:32:28 GMT-0700 (Pacific Daylight Time)'), can work. The value cannot contain any other character that might throw the Date constructor off, i.e. a ‘10/10/2005 original’ will not work.

UNICODE SUPPORT
This sort algorithm works against UNICODE characters/scripts as well because it relies on the browser’s built in string comparison operators. I have a working demo of a this in action sorting a column in my http://www.overset.com/2008/08/30/animated-sortable-datagrid-jquery-plugin-jtps/ post.

I wanted to build a function that split each string to compare for sorting into an array in the appropriate order based off blocks of strings and blocks of numbers similar to how the String.split() functionality works. This is the core of the “chunking” so that you can do the sort comparison off portions of the string and rely on the browser’s built in < and > operators. Another goal was NOT to rely on the String.charCodeAt() and compare ASCII character values on a per-character basis. This seemed like complete overkill considering once each “chunk” can be properly sorted off the browser’s built-in comparison operators properly.

The approach I used was to treat everything as a string, delimitate the numeric and alpha portions of each string by the null char(0) and then split the string into an array off the null char(0) delimiter. This null char(0) will almost never appear in a string - and if it did we’d not really be able to do a comparison operation off of it.

Here’s the simple naturalSort function to be used to point the Array.sort() method to:

SPEED
Upon initial testing this function appears to be 60% faster than Brian Huisman’s Javascript implementation of Dave Koelle’s Alphanum algorithm when sorting against string fields of around 20 characters on average and 500 entries in the array. It appears to be the same speed when sorting against purely numeric integer-based array values at around 500 entries.

TESTED BROWSERS

An example of sorted arrays using this functionality:

['10/12/2008','10/11/2008','10/11/2007','10/12/2007'].sort(naturalSort);
['10/11/2007', '10/12/2007', '10/11/2008', '10/12/2008']

[0,100,7,1,5,"10aay","10abZ","10aby","asd","Asd","Asc"].sort(naturalSort)
[0, 1, 5, 7, "10aay", "10aby", "10abZ", 100, "Asc", "asd", "Asd"]

["$10002.00","$10001.00",10000].sort(naturalSort)
[10000, "$10001.00", "$10002.00"]

["1 Title - The Big Lebowski","1 Title - Gattaca","1 Title - Last Picture Show"].sort(naturalSort)
["1 Title - Gattaca", "1 Title - Last Picture Show", "1 Title - The Big Lebowski"]

[99.99,99.9,1.123,1.1].sort(naturalSort)
[1.1, 1.123, 99.9, 99.99]

NOTE
This function does case-insensitive sorting. This can easily be disabled by removing the .toLowerCase() calls on the x and y variables.


4 Comments
George Hindle @ 9.5.08 10am

Just a spelling mistake. Other than that the code looks good, any speed improvement has to be a good thing, even with chrome and v8 doing a lot of the work for us.

“The approach I used was to treat everything as a string, [b]deliminate[/b] the numeric and alpha portions …” Is this meant to be “eliminate”?

#436 311chars
Jim Palmer @ 9.6.08 4pm

@George

Thanks for catching this! I really meant delimitate which is an odd verb form of the noun “delimiter”. This was how I wanted to describe the “chunking” concept from Dave Koelle.

I’m also in the processes of adding intelligent sorting of dates as they can be converted from strings and testing for the fastest form of sorting. The idea, as you point out, is to rely on the browser - i.e. chrome/v8 - doing as much work for us as possible.

#440 451chars
Philippe Leone @ 9.17.08 9pm

Hello I have some questions about making terrain could you email me back.

Thank you,

Philippe

#463 99chars
claudiohs @ 10.24.08 11am

Very nice work.

#501 15chars



monetary contributions are always accepted $
0.235s