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

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

Answer 2

I use this C# implementation.

Answer 3

By different language do you mean natural alphabetic order in the typical alphabet of any given language?

There's no one algorithm that can do this - it depends entirely on the language and its alphabet. Different languages, I am sure, have different ways of sorting things. Many languages don't even have alphabets, as we think of them. Chinese, for example... I'm not sure how their dictionaries are arranged, but it definitely isn't by spelling.

You'll have to write (or find a library of) natural sorting algorithms for each language you want to implement.

Answer 4

For MySQL, I personally use code from a Drupal module, which is available at http://cvs.drupal.org/viewvc.py/drupal/contributions/modules/natsort/natsort.install.mysql?revision=1.3.2.1&view=markup

Basically, you execute the posted SQL script to create functions, and then use ORDER BY natsort_canon(field_name, 'natural')

Here's a readme about the function: http://cvs.drupal.org/viewvc.py/drupal/contributions/modules/natsort/README.txt?hideattic=0&revision=1.4&view=markup

Answer 5

If the OP is asking about idomatic sorting expressions, then not all languages have a natural expression built in. For c I'd go to <stdlib.h> and use qsort. Something on the lines of :

/* non-functional mess deleted */

to sort the arguments into lexical order. Unfortunately this idiom is rather hard to parse for those not used the ways of c.

---

Suitably chastened by the downvote, I actually read the linked article. Mea culpa.

In anycase the original code did not work, except in the single case I tested. Damn. Plain vanilla c does not have this function, nor is it in any of the usual libraries.

The code below sorts the command line arguments in the natural way as linked. Caveat emptor as it is only lightly tested.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int naturalstrcmp(const char **s1, const char **s2);

int main(int argc, char **argv){
  /* Sort the command line arguments in place */
  qsort(&argv[1],argc-1,sizeof(char*),
    (int(*)(const void *, const void *))naturalstrcmp);

  while(--argc){
    printf("%s\n",(++argv)[0]);
  };
}

int naturalstrcmp(const char **s1p, const char **s2p){
  if ((NULL == s1p) || (NULL == *s1p)) {
    if ((NULL == s2p) || (NULL == *s2p)) return 0;
    return 1;
  };
  if ((NULL == s2p) || (NULL == *s2p)) return -1;

  const char *s1=*s1p;
  const char *s2=*s2p;

  do {
    if (isdigit(s1[0]) && isdigit(s2[0])){ 
      /* Compare numbers as numbers */
      int c1 = strspn(s1,"0123456789"); /* Could be more efficient here... */
      int c2 = strspn(s2,"0123456789");
      if (c1 > c2) {
    return 1;
      } else if (c1 < c2) {
    return -1;
      };
      /* the digit strings have equal length, so compare digit by digit */
      while (c1--) {
    if (s1[0] > s2[0]){
      return 1;
    } else if (s1[0] < s2[0]){
      return -1;
    }; 
    s1++;
    s2++;
      };
    } else if (s1[0] > s2[0]){
      return 1;
    } else if (s1[0] < s2[0]){
      return -1;
    }; 
    s1++;
    s2++;
  } while ( (s1!='\0') || (s2!='\0') );
  return 0;
}

This approach is pretty brute force, but it is simple and can probably be duplicated in any imperative language.

Answer 6

In C++ I use this example code to do natural sorting. The code requires the boost library.

Answer 7

I just use StrCmpLogicalW. It does exactly what Jeff is wanting, since it's the same API that explorer uses. Admittedly, it's not portable.

In C++:

bool NaturalLess(const wstring &lhs, const wstring &rhs)
{
    return StrCmpLogicalW(lhs.c_str(), rhs.c_str()) < 0;
}

vector<wstring> strings;
// ... load the strings
sort(strings.begin(), strings.end(), &NaturalLess);

Answer 8

Here's a cleanup of the code in the article the question linked to:

def sorted_nicely(strings): 
    "Sort strings the way humans are said to expect."
    return sorted(strings, key=natural_sort_key)

def natural_sort_key(key):
    import re
    return [int(t) if t.isdigit() else t for t in re.split(r'(\d+)', key)]

But actually I haven't had occasion to sort anything this way.

Answer 9

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()

Answer 10

Just a link to some nice work in Common Lisp by Eric Normand:

http://www.lispcast.com/wordpress/2007/12/human-order-sorting/

Answer 11

For Tcl, the -dict (dictionary) option to lsort:

% lsort -dict {a b 1 c 2 d 13}
1 2 13 a b c d

Answer 12

Note that for most such questions, you can just consult the Rosetta Code Wiki. I adapted my answer from the entry for sorting integers.

In a system's programming language doing something like this is generally going to be uglier than with a specialzed string-handling language. Fortunately for Ada, the most recent version has a library routine for just this kind of task.

For Ada 2005 I believe you could do something along the following lines (warning, not compiled!):

type String_Array is array(Natural range <>) of Ada.Strings.Unbounded.Unbounded_String;
function "<" (L, R : Ada.Strings.Unbounded.Unbounded_String) return boolean is
begin
   --// Natural ordering predicate here. Sorry to cheat in this part, but
   --// I don't exactly grok the requirement for "natural" ordering. Fill in 
   --// your proper code here.
end "<";
procedure Sort is new Ada.Containers.Generic_Array_Sort 
  (Index_Type   => Natural;
   Element_Type => Ada.Strings.Unbounded.Unbounded_String,
   Array_Type   => String_Array
  );

Example use:

    using Ada.Strings.Unbounded;

    Example : String_Array := (To_Unbounded_String ("Joe"),
                               To_Unbounded_String ("Jim"),
                               To_Unbounded_String ("Jane"),
                               To_Unbounded_String ("Fred"),
                               To_Unbounded_String ("Bertha"),
                               To_Unbounded_String ("Joesphus"),
                               To_Unbounded_String ("Jonesey"));
begin
    Sort (Example);
    ...
end;

Answer 13

In C, this solution correctly handles numbers with leading zeroes:

#include <stdlib.h>
#include <ctype.h>

/* like strcmp but compare sequences of digits numerically */
int strcmpbynum(const char *s1, const char *s2) {
  for (;;) {
    if (*s2 == '\0')
      return *s1 != '\0';
    else if (*s1 == '\0')
      return 1;
    else if (!(isdigit(*s1) && isdigit(*s2))) {
      if (*s1 != *s2)
        return (int)*s1 - (int)*s2;
      else
        (++s1, ++s2);
    } else {
      char *lim1, *lim2;
      unsigned long n1 = strtoul(s1, &lim1, 10);
      unsigned long n2 = strtoul(s2, &lim2, 10);
      if (n1 > n2)
        return 1;
      else if (n1 < n2)
        return -1;
      s1 = lim1;
      s2 = lim2;
    }
  }
}

If you want to use it with qsort, use this auxiliary function:

static int compare(const void *p1, const void *p2) {
  const char * const *ps1 = p1;
  const char * const *ps2 = p2;
  return strcmpbynum(*ps1, *ps2);
}

And you can do something on the order of

char *lines = ...;
qsort(lines, next, sizeof(lines[0]), compare);

Answer 14

Python, using itertools:

def natural_key(s):
    return tuple(
        int(''.join(chars)) if isdigit else ''.join(chars)
        for isdigit, chars in itertools.groupby(s, str.isdigit)
    )

Result:

>>> natural_key('abc-123foo456.xyz')
('abc-', 123, 'foo', 456, '.xyz')

Sorting:

>>> sorted(['1.1.1', '1.10.4', '1.5.0', '42.1.0', '9', 'banana'], key=natural_key)
['1.1.1', '1.5.0', '1.10.4', '9', '42.1.0', 'banana']