Natürliche Sortierung von Zeichenketten

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

Zeichenweise
Ordnung:
Natürliche
Ordnung:
Bild1.jpg Bild1.jpg
Bild10.jpg Bild2.jpg
Bild2.jpg Bild5.jpg
Bild251.jpg Bild10.jpg
Bild26.jpg Bild26.jpg
Bild5.jpg Bild251.jpg

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

Scale of justice 2

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: .NET 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:

List<string> liste = new List<string>();
liste.Add("abc");
liste.Add("def");
// …
liste.Sort(NatCompare);

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.

Option Vergleich zu String.Compare Vergleich zu NATSORT_CMP_ CHAR Vergleich zu NATSORT_CMP_ STRING_NOCASE
Zeichenvergleichsmodi:
NATSORT_CMP_CHAR
Einfacher Zeichenvergleich nach Code-Tabelle
−33 %
NATSORT_CMP_CHAR_NOCASE
Zeichenvergleich ohne Beachtung von Groß-/Kleinschreibung
+150 % +280 %
NATSORT_CMP_STRING
Berücksichtigung lokaler Sonderzeichen
+550 % +875 %
NATSORT_CMP_STRING_NOCASE
Berücksichtigung lokaler Sonderzeichen, ohne Groß-/Kleinschreibung
+567 % +900 %
Zusätzliche Optionen:
+ NATSORT_WITH_SPECIAL
Überspringt bestimmte Sonderzeichen
+130 % +15 %
+ NATSORT_WITH_NEGATIVE
Unterstützt negative Zahlen (kam in meinen Testdaten nicht vor)
+8 % +3 %

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

2009Feb12
Negative Zahlen werden jetzt korrekt sortiert. Zuvor hing die Sortierung von der Länge der Zeichenketten ab. (Dank an Michael Hodel für den hilfreichen Hinweis.)

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 €