7

As I painfully try to find a good natural sorting algorithm written in JavaScript I then stumble upon a bunch of different implementations, & interesting blog posts & answers on Stack Overflow.

Each implementation provides its technical tricks, however the more I looked into it the more a question became very clear: "is there actually any language-agnostic specification regarding natural sorting ORDER of strings???"

I mean, if not, then how could one expect to write a piece of code that is actually "correct for everyone" or "agreed on by the community"? I would have expected a spec stating the result of the compromises/decisions made, at least for English, as it is simple (no accents/diacritics) ...

Note that I wrote "language-agnostic" as I would expect this spec to then be used to implement solutions in different languages, not only in javascript or C# or Java.

Resources:

Improve this question
7
  • 3
    “Natural Sorting” is “whatever sorting a user without any knowledge of ASCII would expect”. As such it's too subjective for an universal spec. And there are definitively a lot of corner cases one could debate endlessly about, and some parts that are difficult to get right, mostly regarding internationalization. Just draft your own algorithm, but beware of xkcd.com/927 – amon Sep 26 '14 at 13:17
  • 2
    "too subjective for an universal spec", one could argue that any spec is subjective ;) "there are definitively a lot of corner cases one could debate endlessly about" yes that's why I'd want a spec so that these corner cases are covered, whether or not one think the wrong decision was taken. But as the cartoon you linked suggests, we may end up with a dozen of specs instead of one universally used. Is this better to not have any at all though? (I cannot find any...) – Adrien Be Sep 26 '14 at 13:29
  • 1
    Are you asking about sort algorithms or sort order? Algorithms for sorting are well understood and widely implemented in every language you're likely to use. The particular order that you want to sort things into depends heavily on your situation, but is usually tied to the character set you're using. – Caleb Sep 26 '14 at 16:47
  • 3
    Natural sort depends on the human language and the context of what you're sorting. Consider sorting kanji, or arabic text, or the former combined with latin characters. A "natural" sort of month names would probably be "Jan, Feb, ..." rather than "April, December, ...". The context matters too much for there to be an objective spec – Daenyth Sep 26 '14 at 21:38
  • 1
    @Daenyth Agreed, but I'd still like to be able to use a "context-free" string sorting implem that follows a "context-free" spec. Then I would expect different "context-specific" specifications to appear (ie. natural sorting for file names). All I'm saying here is "it'd be nice not to have to reinvent the wheel every time I want to sort a list of strings", maybe this is a frustration I have only because I'm doing this in javascript but I feel that this issue has been around for a while, see Jeff Atwood's article from 2007 blog.codinghorror.com/sorting-for-humans-natural-sort-order – Adrien Be Sep 29 '14 at 8:17
14

The algorithms for determining which string comes first when comparing two strings are called collation algorithms and the sort order they produce is called the collation order.

Unfortunately, there is no agreed upon global collation order. To make matters worse, the correct sorting order is not only language dependent, but can even differ between different contexts.
One example of language difference is that in German the accented characters are ordered immediately after their unaccented counterparts (ö comes immediately after o), but in Swedish the accented characters come right at the end of the alphabet (ö comes after z). And as for usage differences, phone books and dictionaries can have different sort orders.

Although there is no global collation order, there are collation orders that generally give a reasonable order independent of the natural language that the words are written in and there are collation algorithms that can be tailored to either give a reasonable sort order or to give the absolute correct order for a given culture and usage.

One such algorithm is the "Unicode Collation Algorithm", which can be found at http://www.unicode.org/reports/tr10/. This algorithm can be tailored for a wide range of collation orders and comes with a default configuration that gives a reasonable ordering for all Unicode codepoints. The algorithm does not depend on any particular programming language.
The introduction section of the standard gives a nice overview of the difficulties in correctly collating text.

Another algorithm is described in ISO standard 14651.

Besides the various national collation orders, there is also a standardized collation order for the European languages, called the European Ordering Rules (EOR).

Improve this answer
4

There is ISO 14651. This is an ISO Standard specifying an algorithm that can be used when comparing two strings. The standard also specifies a datafile specifying the comparison order, the Common Tailorable Template, CTT.

There is the European Ordering Rules. This is an implementation of the iso CTT. It defines an ordering for strings written in languages that are written with the Latin, Greek and Cyrillic alphabets.

There is the Unicode Collation Algorithm. The Unicode collation algorithm (UCA) is an algorithm defined in Unicode Technical Report #10, which defines a customizable method to compare two strings.

Improve this answer
2
  • 2
    would you mind explaining more on what these resources do and why do you recommend these as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange – gnat Oct 3 '14 at 10:39
  • 1
    @gnat I updated the answer. – Pieter B Oct 3 '14 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.