Tips and Tricks: Sorting Strings Non-Lexicographically...

[SlightlyLoony]

"All right," said a reader who had read my post of a few days ago on sorting. "Suppose I need to sort something like this mess, the way a human would want it sorted?"

May 12, 2009
March 3, 10
Jan 09, 99
dec 25, 09
JAN 30, 2010

You didn't really think I'd let a little thing like a non-lexicographical sort stop me, did you?

There are several ways to approach this problem. The approach I chose here was to transform the values being compared into a normalized numeric string that would sort correctly in lexicographical order. Below I've shown the normalized string first, followed by the original input string:

20090512    May 12, 2009
20100303    March 3, 10
20090109    Jan 09, 99
20091225    dec 25, 09
20100130    JAN 30, 2010

So if I transform the strings on the left into the strings on the right, and then sort those lexicographically, then everything will be peachy keen and wonderful. That's what this code does:

// add some handy-dandy methods to the String class
String.prototype.right =
function(n) {
   return this.substring(Math.max(0, this.length - n));
};

String.prototype.left =
function(n) {
   return this.substring(0, n);
}

// test code
var data = ['May 12, 2009', 'March 3, 10', 'Jan 09, 99', 'dec 25, 09', 'JAN 30, 2010'];
data.sort(date_sort);
for (var i = 0; i < data.length; i++)
   gs.log(data);

// sort function
function date_sort(a, b) {
   var months = {jan:1,feb:2,mar:3,apr:4,may:5,jun:6,jul:7,aug:8,sep:9,oct:10,nov:11,dec:12};
   var na = normalize(a);
   var nb = normalize(b);
   return (na == nb) ? 0 : ((na > nb) ? 1 : -1);

   function normalize(x) {
      var parts = /([a-zA-Z]+) (\d+), (\d+)/.exec(x);
      var monthName = parts[1].toLowerCase().left(3);
      var month = pad0(months[monthName], 2);
      var day = pad0(parts[2], 2);
      var year = parts[3] - 0;
      if (year < 100)
         year = (year < 50) ? (2000 + year) : (1900 + year);
      year = pad0(year, 4);
      return year + month + day;
   }

   function pad0(x, n) {
      var y = '0000' + x;
      return y.right(n);
   }
}

Most of the work is done in the normalize function, which does the transformation described above. First a regular expression parses the input value into a month, day, and year. Then each part is transformed into either a 4 digit or a 2 digit number (adding leading zeros if necessary). Finally all the parts are concatenated to produce the result.

If you've been torturing yourself by reading my recent series of posts, most of this code should look at least vaguely familiar, and you should be able to figure out what it's doing. A couple of bits might need some explanation, though:

• 
  
• In the line var year = parts[3] - 0; the subtraction of zero is a trick to force the result to be a numeric value. I do this so that on the next line I can do a comparison to a numeric value, and be sure that the comparison will be done numerically, and not lexicographically (by coercing the value 100 to a string).
• The line return (na == nb) ? 0 : ((na > nb) ? 1 : -1); is a nested ternary expression. It's just a more compact way of writing this:
  

  
  if (na == nb)
     return 0;
  else {
     if (na > nb)
        return 1;
     else
        return -1;
  }