Natürliche Sortierung von Zeichenketten

Sortiert Zeichenketten, die Zahlen enthalten, nicht zeichenweise (lexikalisch), sondern nach ihrem nummerischen Wert: „a1“ < „a2“ < „a10“ < „a11“ < „a20“

In Computern verwendete Sortieralgorithmen für Zeichenketten vergleichen die Zeichenketten üblicherweise Zeichen für Zeichen und entscheiden bei dem ersten Unterschied, ob die eine Zeichenkette vor oder nach der anderen einsortiert werden muss. Das funktioniert wunderbar mit Wörtern und Namen, aber nicht mit Zahlen unterschiedlicher Länge (siehe Tabelle rechts). Dafür muss die gesamte Zahl betrachtet und ihr nummerischer Wert verglichen werden. Zahlen werden zwar prinzipiell ebenfalls von links nach rechts ziffernweise verglichen, aber nur dann, wenn beide Zahlen die gleiche Anzahl an Ziffern haben. Bei kürzeren Zahlen muss man sich für den Vergleich also „führende Nullen denken“. So kommt bei der üblichen Sortierung zwar korrekterweise „ab“ vor „c“, aber eben auch „12“ vor „3“, was uns eigentlich falsch erscheint.

Vereinfacht ausgedrückt sortiert die natürliche Ordnung folgendermaßen:

a < a0 < a01 < a1 < a1a < a1b < a2 < a10 < a11 < a20 < a100 < b

Zeichenketten ohne Ziffern werden wie gewohnt sortiert. Weitere Eigenschaften meiner Implementierung sind:

• Negative Zahlen direkt am Anfang einer Zeichenkette werden nummerisch korrekt einsortiert.
• Explizit angegebene führende Nullen werden ignoriert. Um deterministische Ergebnisse zu erzeugen, wird ihnen aber eine Präferenz zugeordnet, die als Vergleichskriterium dient, wenn die Zeichenketten ansonsten gleich wären. Mehr führende Nullen werden (analog zur herkömmlichen zeichenweisen Sortierung) zuerst einsortiert. (Siehe Beispiel)
• Bestimmte Sonderzeichen werden genauso wie führende Nullen zunächst ignoriert. Das sind: Leerzeichen, einfache und doppelte Anführungszeichen (nur im ASCII-Zeichensatz, U+0027 bzw. U+0022). Die Liste dieser Zeichen kann in der Zeichenkette special verändert werden. Zahlen enden dennoch vor diesen Sonderzeichen: zwei durch ein Leerzeichen getrennte Zahlen werden also vor dem Vergleich nicht aneinandergeklebt.
• Das Ergebnis dieser Funktion ist deterministisch, d. h. Zeichenketten in beliebiger Sortierung werden in genau eine Sortierung überführt. Dafür werden während des Vergleichs Präferenzen gesammelt, die als Entscheidungskriterium dienen, wenn keine weiteren relevanten Unterschiede gefunden wurden. So kommen bei gleichen Wörtern z. B. Groß- vor Kleinbuchstaben und ignorierte Sonderzeichen werden schließlich doch beachtet. Würden führende Nullen z. B. ersatzlos ignoriert, führte das zu der „Ordnung“: … a0 < a01 = a1 < a1a …

Was diese Funktion nicht kann:

• Zahlen mit Nachkommastellen (unterschiedlicher Länge) werden nicht korrekt sortiert. Stattdessen wird der Nachkommaanteil wieder als Ganzzahl interpretiert und nummerisch verglichen. So käme z. B. „1,2“ vor „1,005“, weil 2 < 5 ist. Eine Unterstützung dieser Funktion würde die Erkennung des Tausendertrennzeichens erfordern, das je nach Sprache unterschiedlich ist. Vielleicht mach ich das aber noch.

Kompatibilität: Ab Version 2.0

Hinweise zur Verwendung

Das Sortieren von Daten lässt sich im Sortieralgorithmus auf das paarweise Vergleichen der Daten zurückführen. Ich biete hier also keinen Sortieralgorithmus (wie Bubble Sort oder Quicksort) an, sondern lediglich die Vergleichsfunktion. Die kann auch einzeln verwendet werden, woimmer zwei Zeichenketten sortiert werden sollen. Um ganze Listen zu sortieren, kann man z. B. folgenden Code verwenden:

Die Code-Datei enthält zu Beginn Präprozessor-Anweisungen („#define …“), mit denen der Umfang des tatsächlich verarbeiteten Codes konfigurierbar ist. So lassen sich u. a. die Unterstützung für lokale Sonderzeichen oder negative Zahlen komplett deaktivieren, diese Codeabschnitte werden dann gar nicht mehr mitkompiliert und verbrauchen weder Platz noch Laufzeit. Diese Anweisungen müssen jeweils direkt am Anfang einer Code-Datei stehen, also noch vor den using- und namespace-Angaben. Da es sich hier nur um Symboldefinitionen handelt, können diese alternativ auch in die Projektkonfiguration übernommen werden (Visual Studio: Projekteigenschaften; Erstellen; Symbole für bedingte Kompilierung).

Download

NaturalSort.cs8,0 KiBQuelltext der NatCompare-Funktion

Performance

Da in dieser Funktion erheblich mehr Aufwand getrieben wird, ist eine längere Laufzeit auf den gleichen Daten gegenüber einfachem zeichenweisen Vergleich zu erwarten. Um die Geschwindigkeit der Vergleichsfunktion zu testen, habe ich Zeitmessungen mit einer nicht repräsentativen Liste von ca. 21 100 Dateinamen aus meinem Windows-Verzeichnis durchgeführt, bei der die Methode List<string>.Sort(Comparison<string>) zum Einsatz kam.

Zusammenfassend lässt sich sagen, dass die Verwendung der Funktion zur natürlichen Sortierung mit aktivierter Unterstützung für lokale Zeichen und negative Zahlen sowie Groß-/Kleinschreibung und bestimmte Sonderzeichen ignorierend zu einem reinen Vergleichsaufwand von etwa dem 6,7-fachen der normalen Sortierung führt.

Änderungen

Referenzen

• Numeric String Sort in C# (The Code Project)
  Ich habe mich für meine Implementierung von diesem Artikel inspirieren lassen, den Code aber nicht als Vorlage verwendet. Ich habe mir in der Tat nichtmal die Mühe gemacht, ihn zu verstehen, und stattdessen direkt mit meinen eigenen Überlegungen begonnen. Meine Funktion ist jetzt besser konfigurierbar, unterstützt negative Zahlen und lokale Sonderzeichen von Haus aus, besteht aus nur einer Funktion und ist dabei etwa gleich schnell (nach meiner dargestellten Messung). Irgendwo in den Besucherkommentaren der Seite befindet sich auch eine Änderung, die lokale Sonderzeichen berücksichtigt. Diese Änderung habe ich im Benchmark verwendet.

Lizenz und Nutzungsbedingungen

Vervielfältigung und Weiterverbreitung dieser Datei, verändert oder unverändert, sind gestattet, vorausgesetzt die Urheberrechtsangabe und dieser Hinweis bleiben erhalten. Diese Datei wird wie vorliegend ohne jegliche Garantie oder Gewährleistung angeboten. (GNU All-Permissive-Lizenz)

Statistische Daten

• Erstellt am 2007-07-08, aktualisiert am 2009-02-12.
• Ca. 100 Codezeilen, geschätzte Ent­wick­lungs­kos­ten: 100 - 400 €