3-Wege-Quicksort für Strings (Algorithmus 5.3)

So geht’s: Beim Öffnen läuft der Testclient mit den 14 Strings aus Abbildung 5.18. Jeder Aufruf sort(a, lo, hi, d) bearbeitet den blau markierten Bereich, und das Zeichen an Position d ist rot. Ein rotes ▪ heißt, dass der String dort schon zu Ende ist. Rechts stehen v, das Zeichen von a[lo], und das gerade geprüfte Zeichen t. Neben a[] stehen die Zeiger lt, i und gt. Während der Partitionierung färbt sich der Bereich: blau ist kleiner als v, gelb gleich, lila größer, dazwischen liegt das noch Ungeprüfte. Danach folgen drei rekursive Aufrufe, Kleiner- und Größer-Teil wieder mit d, der Gleich-Teil mit d + 1. Grün sind Plätze, die endgültig stehen. Der Aufrufstapel zeigt, in welchem Teil der Eltern-Aufruf gerade steckt, das Protokoll listet jede Partitionierung eingerückt nach Rekursionstiefe. Oben zählt die App die Zeichenvergleiche. „Zufallsdaten“ erzeugt kurze Strings aus a, b und c mit vielen gemeinsamen Präfixen, „↺ Neu starten“ springt zurück zum Beispiel aus dem Buch.

Erklärung

3-Wege-Quicksort für Strings (Algorithmus 5.3), Klasse Quick3string. Eine Kreuzung aus Quicksort [11] und MSD [44]: Partitioniert wird wie bei Quicksort, aber immer nur nach einem Zeichen an Position d, wie bei MSD.

Idee:

• Partitionszeichen v ist das d-te Zeichen des ersten Strings a[lo].
• Das Teilarray wird in drei Teile zerlegt (3-Wege-Partitionierung nach Dijkstra): d-tes Zeichen kleiner als v, gleich v, größer als v.
• Rekursion:
  • kleiner und größer: wieder ab Position d (das Zeichen ist noch nicht sortiert),
  • gleich: ab Position d + 1 (dieses Zeichen ist bei allen gleich, also weiter zum nächsten).
• Gleich-Teil nur, wenn v ≥ 0. Bei v = −1 (Stringende) sind die Strings komplett gleich, nichts mehr zu tun.

Der Code:

• lt, i, gt sind drei Zeiger. Links von lt liegt alles Kleinere, zwischen lt und i alles Gleiche, rechts von gt alles Größere, dazwischen das noch Ungeprüfte.
• Zeichen kleiner → nach links tauschen, beide Zeiger vor. Größer → nach rechts tauschen, gt zurück. Gleich → nur i vor.
• charAt liefert wie bei MSD −1 am Stringende.

Abbildung 5.18 (she sells seashells by the sea shore …):

• Erste Partitionierung nach dem ersten Zeichen von „she“, also s: kleiner sind by, are; gleich sind alle s-Wörter; größer sind the, the.
• Der große s-Block wird ab dem zweiten Zeichen weiterbearbeitet (e, h, u …), die Ränder ab dem ersten.
• Graue Balken = leere Teilarrays. Wo das Stringende erreicht ist, gibt es keinen weiteren Aufruf, etwa bei she, sea, the.
• Bei seashells und sells sieht man, wie die gleichen Präfixe einfach Zeichen für Zeichen abgearbeitet werden, ohne die Gruppe zu zerlegen.

Kosten (Satz E im Buch): Für N zufällige Strings im Schnitt etwa 2 N ln N Zeichenvergleiche.

Warum besser als MSD [44]?

• Kein count-Array pro Aufruf, also kein Zusatzspeicher außer dem Rekursionsstapel.
• Immer nur drei Teile statt R + 1, also keine Flut leerer Teilarrays, egal wie groß das Alphabet ist.
• Lange gemeinsame Präfixe sind kein Problem: Sie landen im Gleich-Teil und werden mit d + 1 einfach durchgereicht.

Warum besser als normales Quicksort [11]?

• Normales Quicksort vergleicht ganze Strings mit compareTo(). Das läuft jedes Mal von vorn über die gemeinsamen Präfixe. Bei URLs wie „edu.princeton.cs…“ heißt das: immer wieder dieselben 14 Zeichen.
• 3-Wege-Quicksort für Strings schaut jedes Präfix-Zeichen nur einmal an und geht dann weiter.

Die Verbesserungen im Text:

• Kleine Teilarrays: Wechsel zu Insertionsort (Listing 5.5), der gleiche Anfangszeichen überspringt. Bringt etwas, aber weniger als bei MSD, weil hier ohnehin keine teuren count-Arrays anfallen.
• Begrenztes Alphabet: lohnt sich hier nicht. Der Zusatzcode säße in der inneren Schleife und würde mehr kosten als bringen.
• Randomisierung: Wie bei jedem Quicksort vorher mischen oder das Partitionselement zufällig wählen. Schützt vor dem schlimmsten Fall bei vorsortierter Eingabe.
• Schlussgedanke: Alle Vergleichsverfahren aus Kapitel 2 sind bei Strings eigentlich schon eine Art MSD, weil compareTo() die Zeichen von links nach rechts liest und beim ersten Unterschied aufhört.

Die drei Stringsortierverfahren:

Kapitel 5 bisher:

• Algorithmus 5.1: LSD-Sortierverfahren [43]
• Algorithmus 5.2: MSD-Sortierverfahren [44]
• Algorithmus 5.3: 3-Wege-Quicksort für Strings [45]