17

I want to sort strings (text) in a software project of mine. I'm planning to do this in the lexically best way. My set of possible characters consist of the full alphabet (a–z and A–Z) and of the typical Latin 1 Umlauts, like Ä, ö, ß, and also characters from other Latin 1 languages like à, á, â, ã. (It’s technically impossible to order the data by expanding characters like Ä to Ae.)

How would one sort those characters so that also humans could look them up fast?

  • Would one look for Ä after A (I guess). And for é after e?
  • In which order would à, á, â, ã, and ä be sorted in between a and b?
  • Is there some kind of ISO standard defining such things? How would those characters be arranged?
Improve this question
4
  • 12
    In most programming languages a collation function is available which compares strings according to a locale. In C, this function is strcoll(). Java has a Collator class.
    – RHa
    Commented Jun 16, 2019 at 19:12
  • The right way to do this is to use strxfrm() to convert your user-visible strings into encoded strings that can be compared using strcmp(). If you're sorting user records, say, and each has a "name" field, you'd have to then create a "nameSortable" field and use strxfrm to populate it. That resulting field may or may not look much like the ASCII you put in but is guaranteed to sort in the right order for the current locale. And since you do the transformation once, it should then sort quickly.
    – Swiss Frank
    Commented Jun 17, 2019 at 13:45
  • A easier but typically lower-performance method is to use strcoll() to compare. This may be slower because in effect it's internally creating buffers, calling strxfrm to get comperable strings, comparing them, and throwing away the results of the conversion, only leaving the result. strxform() requires you to manage the caches, but pays you back by allowing far faster compares.
    – Swiss Frank
    Commented Jun 17, 2019 at 13:45
  • 4
    Humans? Unfortunately, it depends which humans. Swedish humans looking for these characters will look in a different place from German humans. There are many standards for collating sequences, some country-specific, some industry-specific. Whatever you do, don't go inventing another one.
    – Michael Kay
    Commented Jun 17, 2019 at 16:02

3 Answers 3

Reset to default
27

Short answer:

Take a look at MySQL and different character-collations. Choose one and follow its rules. Or as @RHa and @cbeleites suggest find a library that provides locale-dependent sorting.

Long answer:

There are 3 different solutions for your problem (actually there are 4, but believe me, you don't want to realize the 4th ;) )

  1. Rewrite every Umlaut to its base (German dictionary rules - DIN 5007-1 var. 1)

    Every Umlaut and Diacritic results in the same char. e.g.

    áàâäã = a

    ß = ss

    and so on.

    Sort them.

  2. Rewrite every Umlaut by adding an e, diacritics are removed (German phone book rules - DIN 5007-1 var. 2)

    ä = ae

    áàâã = a

    ü = ue

    ß = ss

    Sort them.

    1. Umlaute are new chars added to the alphabet (Swedish/Finnish collation rules)

      Every Umlaut and å are treated like new chars, which are added after the z of the alphabet. Other chars with diacretics are converted to their base.

      So sort like

      aáàâãbcd [...] xyzåäü

    2. Umlaute are new chars added to the alphabet (Austrian phone book order - kudos to @rexkogitans from the comments)

      It's as 3.1., but Umlaute and chars with Diacretics are appended to their base characters.

      aäáà [...] bcdeèé [...] uü ...

      But watch out, wiki says this is true for the Austrian White Pages, but the Austrian Yellow Pages are sorted like DIN 5007-1 var. 1.

In addition. According to EN 13710 the order of diacritics is

  1. Acute accent (á)
  2. Grave accent (à)
  3. Breve (ă)
  4. Circumflex (â)
  5. Hacek (háček) (š)
  6. Ring (å)
  7. Trema (ä)
  8. Double acute accent (ő)
  9. Tilde (ã)
  10. Dot (ż)
  11. Cedilla (ş)
  12. Ogonek (ą)
  13. Macron (ā)
  14. With stroke through (ø)
  15. Modified letter(s) (æ)

For further information take a look at

One very last comment:

There are a lot of countries and there are a lot of different languages and a lot of different characters. Some are frequently used in one country, but unknown in another.

Therefore there are a lot of different standards how to compare strings alphabetically. Even though there are international standards, you have to choose which one to follow.

How? Well, there's a saying: When in Rome, do as the Romans do.

Take a look at your target group and their expectations. Then choose the collation most of them will accept.

  • Spanish people? Well, ñ is an independent character sorted in between n and o.

  • Germans? Take a look above.

  • Russians and western europeans? Oh boy, you are in trouble sorting all these cyrillic and latin characters ;)

  • Or choose the one you are most comfortable with.

Also ... one of my professors once said: "The first thing I do before coding is searching the internet if there is already a solution." And as @RHa and @cbeleites said in the comments there are solutions (C, Java, PHP, etc.), so unless you insist ... use one of them and you only have to worry about choosing the right locale (and looking up which sorting rules they follow).

Last and least: The 4th sorting method

As I mentioned ealier there is a 4th (horrible) solution. German Wikipedia describes it as

Gleichordnung von Grundbuchstaben, Doppelbuchstaben und Umlaut, wenn Doppelbuchstabe wie Umlaut gesprochen wird. Mull wird wie Muell oder Müll sortiert. Duell dagegen zwischen Duden und Dugast.

To explain it in English I would like to quote @FabioTurati from the comments

It says that an approach is treating plain letters, double letters and Umlauts the same way, but only when the double letters are pronounced as an Umlaut. For example, "Mull", "Muell" and "Müll" are treated the same way (note that Mull and Müll are different words!), and the "ue" in Muell here is a way to avoid typing "ü". In other cases, the letters "ue" are pronounced separately: a "u" followed by an "e", for example in "Duell", which is why Duell is placed between Duden and Dugast.

Why is this a problem?

Consider it from the other point of view: if you find a word containing "ue", how do you treat it? For Muell you should pretend the "e" is not there, and treat it as "Mull". For "Duell", doing it would lead to "Dull", which would be sorted after "Dugast", which would be wrong. So, to know how to sort words you need to have some more info (that is, how they are pronounced), which a sorting algorithm normally doesn't have. That's why this approach is troublesome!

Improve this answer
12
  • 1
    Another sorting rule: Treat ä, ö, ü as additional characters, but not appended after z, but instead after a, o, u respectively: a, ä, b, c, ..., m, n, o, ö, p, ... This is called Austrian Order.
    – rexkogitans
    Commented Jun 17, 2019 at 6:11
  • 12
    So... what's the fourth?
    – sgf
    Commented Jun 17, 2019 at 7:47
  • 2
    @sgf from wikipedia: "Gleichordnung von Grundbuchstaben, Doppelbuchstaben und Umlaut, wenn Doppelbuchstabe wie Umlaut gesprochen wird. Mull wird wie Muell oder Müll sortiert. Duell dagegen zwischen Duden und Dugast." which is horrifying to code and gets nasty with names like "Schröder / Schroeder", etc
    – mtwde
    Commented Jun 17, 2019 at 9:50
  • 2
    Your description of the Swedish collation order is incorrect. You are right that å, ä and ö are treated as full-worthy letters and sorted after z, but all other diacritics are ignored. E.g. á is sorted as a and not after a. Until some 10 years ago, v and w were also considered equal when sorting, but w is now usually considered a 'proper' letter in itself and sorted after v. AFAIK, the same collation rules are used in Finnish.
    – jarnbjo
    Commented Jun 17, 2019 at 13:06
  • 1
    @mtwde My German isn't good enough to understand that Wikipedia excerpt. Could you translate it, please?
    – Nzall
    Commented Jun 18, 2019 at 7:08
6

If it's not names you are dealing with, it would be best to ignore all diacritics when sorting (and count ß as ss).

The only reason to deviate from this simple system lies in the unfortunate fact that German names show unpredictable variation between ä, ö, ü and ae, oe, ue. This has lead to phone books and library catalogues sorting e.g. Räder as Raeder, Örtel as Oertel, Hüber as Hueber.

Wikipedia has a good write-up.

Improve this answer
0

I can answer you only regarding the German characters. "Ä" is considered equivalent to "Ae", "Ö" to "Oe", "Ü" to "Ue" and "ß" to "ss". This is how those characters are sorted in a phonebook.

Improve this answer
4
  • Thank you for your answer. Sadly I cannot implement this behaviour. I'm sorry. I removed the phone book reference.
    – Matthias
    Commented Jun 16, 2019 at 16:06
  • 1
    This does mean that it is sorted like this not that it is written like this.
    – Kami Kaze
    Commented Jun 17, 2019 at 6:43
  • This is how German users would expect it.
    – Simon Richter
    Commented Jun 17, 2019 at 8:56
  • 3
    @SimonRichter: There are (at least) two different widely-used collation orders in Germany, and even more if you also consider other German-speaking countries such as Austria and Switzerland. So, whether or not "German users would expect it" this way depends very much on context and on whether those German users are actually from Germany or German-speaking from Austria, for example.
    – Jörg W Mittag
    Commented Jun 17, 2019 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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