Natural Sorting algorithm

Question

How do you sort an array of strings naturally in different programming languages? Post your implementation and what language it is in in the answer.

Answer 1

Here's how you can get explorer-like behaviour in Python:

#!/usr/bin/env python """ >>> items = u'a1 a003 b2 a2 a10 1 10 20 2 c100'.split() >>> items.sort(explorer_cmp) >>> for s in items: ...     print s, 1 2 10 20 a1 a2 a003 a10 b2 c100 >>> items.sort(key=natural_key, reverse=True) >>> for s in items: ...     print s, c100 b2 a10 a003 a2 a1 20 10 2 1 """ import re  def natural_key(astr):     """See http://www.codinghorror.com/blog/archives/001018.html"""     return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', astr)]  def natural_cmp(a, b):     return cmp(natural_key(a), natural_key(b))  try: # use explorer's comparison function if available     import ctypes     explorer_cmp = ctypes.windll.shlwapi.StrCmpLogicalW except (ImportError, AttributeError):     # not on Windows or old python version     explorer_cmp = natural_cmp          if __name__ == '__main__':     import doctest; doctest.testmod() 

To support Unicode strings, .isdecimal() should be used instead of .isdigit().

.isdigit() may also fail (return value that is not accepted by int()) for a bytestring on Python 2 in some locales e.g., '\xb2' ('²') in cp1252 locale on Windows.

Answer 2

JavaScript

Array.prototype.alphanumSort = function(caseInsensitive) {   for (var z = 0, t; t = this[z]; z++) {     this[z] = [], x = 0, y = -1, n = 0, i, j;      while (i = (j = t.charAt(x++)).charCodeAt(0)) {       var m = (i == 46 || (i >=48 && i <= 57));       if (m !== n) {         this[z][++y] = "";         n = m;       }       this[z][y] += j;     }   }    this.sort(function(a, b) {     for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) {       if (caseInsensitive) {         aa = aa.toLowerCase();         bb = bb.toLowerCase();       }       if (aa !== bb) {         var c = Number(aa), d = Number(bb);         if (c == aa && d == bb) {           return c - d;         } else return (aa > bb) ? 1 : -1;       }     }     return a.length - b.length;   });    for (var z = 0; z < this.length; z++)     this[z] = this[z].join(""); } 

Source