Das Standardwerk zu Algorithmen und Datenstrukturen in Java: Sortieren, Suchen, Graphen und Zeichenketten, jeweils mit vollständigem Code, Laufzeitanalyse und vielen Abbildungen.
Svens Buch – und die Grundlage der Rubrik Algorithmen: Dort laufen die Algorithmen aus diesem Buch Schritt für Schritt ab, mit eigenem Java-Code im Stil der Listings.
Robert Sedgewick, Kevin Wayne, Algorithms (4. Auflage 2011)
Der Max-Fluss-Algorithmus nach Ford-Fulkerson mit kürzestem augmentierendem Pfad aus Sedgewick/Wayne, Algorithmus 6.3 (Listing 6.11 bis 6.13) – Breitensuche im Restnetzwerk, Engpass, Augmentieren und am Ende der minimale Schnitt, am Beispiel tinyFN.txt aus den Abbildungen 6.21 und 6.22.
Das Suffixarray aus Sedgewick/Wayne, Algorithmus 6.2 (Listing 6.9 mit lcp() aus Listing 6.6) – alle Suffixe sortieren, den längsten sich wiederholenden Teilstring über benachbarte Suffixe finden (Listing 6.7) und mit rank() und Binärsuche Schlüsselwörter im Kontext suchen (Listing 6.8), am Beispiel aus Abbildung 6.14.
Der B-Baum aus Sedgewick/Wayne, Algorithmus 6.1 (Listing 6.5) – Seiten mit bis zu M Schlüsseln, Suche mit einer Seite pro Ebene, Einfügen unten mit Teilung voller Seiten auf dem Rückweg, am Beispiel der B-Bäume der Ordnung 6 aus den Abbildungen 6.7 bis 6.9.
Die LZW-Komprimierung aus Sedgewick/Wayne, Algorithmus 5.11 (Listing 5.41 und 5.42) – mit longestPrefixOf() im TST die längste bekannte Folge finden, ihr 12-Bit-Codewort schreiben und die Folge plus nächstes Zeichen neu eintragen; expand() baut die Tabelle beim Lesen wieder auf, samt der kniffligen Situation bei ABABABA.
Die Huffman-Komprimierung aus Sedgewick/Wayne, Algorithmus 5.10 (Listing 5.33 bis 5.40) – Häufigkeiten zählen, mit einer Min-Vorrangwarteschlange den Trie bauen, Codewörter ablesen, Trie und Text als Bitfolge schreiben und mit expand() wieder lesen, am Beispiel ABRACADABRA! wie in Abbildung 5.65.
Die musterbasierte Suche mit regulären Ausdrücken aus Sedgewick/Wayne, Algorithmus 5.9 (Listing 5.24 und 5.25) – den nichtdeterministischen Automaten mit einem Stapel aufbauen und dann alle möglichen Zustände gleichzeitig durch den Text schicken, am Beispiel ((A*B|AC)D) wie in Abbildung 5.51.
Die Rabin-Karp-Fingerprint-Suche aus Sedgewick/Wayne, Algorithmus 5.8 (Listing 5.21 und 5.22) – Hash des Musters nach dem Horner-Schema, dann ein rollender Hash über den Text, am Zahlenbeispiel 26535 in 3141592653589793 wie in Abbildung 5.47.
Die Teilstringsuche nach Boyer-Moore mit Vorkommensheuristik aus Sedgewick/Wayne, Algorithmus 5.7 (Listing 5.20) – das Muster von rechts nach links vergleichen und bei einer Abweichung weit springen, am Beispiel NEEDLE aus dem Buch.
Die Knuth-Morris-Pratt-Teilstringsuche aus Sedgewick/Wayne, Algorithmus 5.6 (Listing 5.18) – erst den Automaten aus dem Muster bauen, dann den Text Zeichen für Zeichen hindurchschicken, ohne je zurückzulesen, am Testlauf AACAA aus dem Buch.
Der ternäre Suchtrie aus Sedgewick/Wayne, Algorithmus 5.5 (Listing 5.13) – pro Knoten ein Zeichen und drei Verweise statt R, put und get Zeichen für Zeichen, am TST aus Abbildung 5.29.
Die Trie-Symboltabelle aus Sedgewick/Wayne, Algorithmus 5.4 (Listing 5.8 bis 5.10) – ein R-Wege-Trie mit put und get, dazu Schlüssel sammeln nach Präfix und nach Muster mit Platzhaltern, an „she sells sea shells by the sea shore“ wie in Abbildung 5.23.
Der 3-Wege-Quicksort für Strings aus Sedgewick/Wayne, Algorithmus 5.3 (Listing 5.6) – Partitionierung in kleiner, gleich und größer nach einem einzigen Zeichen, der Gleich-Teil geht mit dem nächsten Zeichen weiter, an „she sells seashells …“ wie in Abbildung 5.18.
Das MSD-Sortierverfahren aus Sedgewick/Wayne, Algorithmus 5.2 (Listing 5.4 und 5.5) – Strings beliebiger Länge vom ersten Zeichen aus sortiert, Gruppe für Gruppe rekursiv, mit Insertionsort für kleine Teilarrays, an „she sells seashells …“ wie in Abbildung 5.12 und 5.13.
Das LSD-Sortierverfahren aus Sedgewick/Wayne, Algorithmus 5.1 (Listing 5.3) – gleich lange Strings von der letzten Zeichenposition zur ersten sortiert, jeder Durchgang ein schlüsselindiziertes Zählen, an den 13 Kennzeichen aus dem Buch.
Der warteschlangenbasierte Bellman-Ford-Algorithmus aus Sedgewick/Wayne, Algorithmus 4.11 (Listing 4.36 bis 4.38) – kürzeste Pfade auch mit negativen Gewichten, negative Zyklen werden erkannt, an tinyEWDn und tinyEWDnc wie in Abbildung 4.91 und 4.92.
AcyclicSP aus Sedgewick/Wayne, Algorithmus 4.10 (Listing 4.34) – kürzeste Pfade in einem kantengewichteten DAG, Knoten für Knoten in topologischer Reihenfolge relaxiert, auch mit negativen Gewichten, am Digraphen tinyEWDAG wie in Abbildung 4.77.
Der Dijkstra-Algorithmus aus Sedgewick/Wayne, Algorithmus 4.9 (Listing 4.32) – kürzeste Pfade ab einem Startknoten in einem gerichteten, kantengewichteten Graphen, Knoten für Knoten aus einer indizierten Vorrangwarteschlange, am Digraphen tinyEWD wie in Abbildung 4.74.
Der MST-Algorithmus von Kruskal aus Sedgewick/Wayne, Algorithmus 4.8 (Listing 4.25) – alle Kanten nach Gewicht aus einer Vorrangwarteschlange, Union-Find verwirft jede, die einen Zyklus schlösse, am Graphen tinyEWG.
Der MST-Algorithmus von Prim in der Eager-Version aus Sedgewick/Wayne, Algorithmus 4.7 (Listing 4.24) – der Baum wächst ab Knoten 0, eine indizierte Vorrangwarteschlange hält je Knoten die beste Verbindung, am Graphen tinyEWG mit dem Ablauf aus Abbildung 4.61.
Der Kosaraju-Algorithmus aus Sedgewick/Wayne, Algorithmus 4.6 (Listing 4.17) – erst die umgekehrte Postorder des umgedrehten Digraphen, dann Tiefensuchen in genau dieser Reihenfolge, am Digraphen tinyDG.
Das topologische Sortieren aus Sedgewick/Wayne, Algorithmus 4.5 (Listing 4.16) – erst die Zyklussuche mit onStack[], dann die umgekehrte Postorder einer Tiefensuche, an den Vorrangbedingungen der Studienfächer aus jobs.txt.
Die Erreichbarkeit in gerichteten Graphen aus Sedgewick/Wayne, Algorithmus 4.4 (Listing 4.13) – Tiefensuche entlang der Pfeile, ab einem oder mehreren Startknoten, am Digraphen tinyDG mit dem Ablauf aus Abbildung 4.32 und den drei Testläufen des Buchs.
Die Zusammenhangskomponenten aus Sedgewick/Wayne, Algorithmus 4.3 (Listing 4.8) – die for-Schleife des Konstruktors, je Komponente eine Tiefensuche, id[] und count Schritt für Schritt, dazu connected(v, w), am Graphen tinyG aus dem Buch.
Die Breitensuche aus Sedgewick/Wayne, Algorithmus 4.2 (Listing 4.6) – Knoten für Knoten aus der Warteschlange, Abstände als Ebenen im Baum aus edgeTo[], kürzeste Pfade mit pathTo(v) und der direkte Vergleich mit der Tiefensuche am selben Graphen.
Die Tiefensuche aus Sedgewick/Wayne, Algorithmus 4.1 (Listing 4.5) – dfs Aufruf für Aufruf mit Aufrufstapel, marked[] und edgeTo[], der Baum aus edgeTo[] und pathTo(v) mit dem Stapel, am Graphen aus Abbildung 4.16.
Die Hashtabelle mit linearer Sondierung aus Sedgewick/Wayne, Algorithmus 3.6 (Listing 3.20) – jede Sondierung einzeln, Cluster, Löschen mit Neu-Einfügen des Clusters und Verdoppeln der Tabelle, mit dem Testclient aus Abbildung 3.59.
Die Hashtabelle mit separater Verkettung aus Sedgewick/Wayne, Algorithmus 3.5 (Listing 3.19) – hash() Schritt für Schritt, dann die Suche in einer einzigen der M Listen, mit dem Testclient aus Abbildung 3.56 und wahlweise den echten Hashwerten von Java.
Der linksgerichtete Rot-Schwarz-Baum aus Sedgewick/Wayne, Algorithmus 3.4 (Listing 3.16) – put Schritt für Schritt mit rotateLeft, rotateRight und flipColors auf dem Rückweg, daneben derselbe Baum als 2-3-Baum, mit beiden Einfügefolgen aus Abbildung 3.46.
Die Symboltabelle als binärer Suchbaum aus Sedgewick/Wayne, Algorithmus 3.3 (Listings 3.9–3.13, 3.15) – jeder rekursive Aufruf einzeln mit Aufrufstapel: Suchen, Einfügen, min, max, floor, ceiling, select, rank, deleteMin, Löschen nach Hibbard und die Bereichssuche aus Abbildung 3.21.
Die Symboltabelle als geordnetes Array aus Sedgewick/Wayne, Algorithmus 3.2 (Listings 3.5, 3.7, 3.8) – rank mit lo, hi und mid Schritt für Schritt wie in Abbildung 3.6, das Verschieben beim Einfügen und die geordneten Operationen min, max, select, ceiling, floor und keys.
Die Symboltabelle als ungeordnete verkettete Liste aus Sedgewick/Wayne, Algorithmus 3.1 (Listing 3.4) – put und get Schritt für Schritt, jeder Vergleich einzeln, mit dem Testclient SEARCHEXAMPLE wie in Abbildung 3.3.
Die Union-Find-Variante aus der Praxis nach Sedgewick/Wayne, Algorithmus 1.5 (Fortsetzung, Listing 1.57) – der kleinere Baum kommt unter den größeren, Abbildung 1.61 mit Referenz- und Worst-Case-Eingabe Schritt für Schritt und Satz H zum Nachprüfen.
Dynamische Zusammenhangskomponenten aus Sedgewick/Wayne, Algorithmus 1.5 (Listing 1.54) – Quick-Find, Quick-Union und gewichtetes Quick-Union zum Umschalten, find und union Schritt für Schritt mit Bäumen, id[] und Arrayzugriffen, dazu der Testclient mit tinyUF.txt.
Die Multimenge als Kette aus Sedgewick/Wayne, Algorithmus 1.4 (Listing 1.42) – hineinlegen mit add und durchlaufen mit dem Iterator, Schritt für Schritt bis zu Mittelwert und Standardabweichung, mit Java-Code und Protokoll.
Die Warteschlange als Kette mit zwei Zeigern aus Sedgewick/Wayne, Algorithmus 1.3 (Listing 1.41) – enqueue hinten, dequeue vorn, die beiden Sonderfälle bei leerer Schlange Schritt für Schritt, mit Java-Code und Protokoll.
Der Stapel als Kette von Knoten aus Sedgewick/Wayne, Algorithmus 1.2 (Listing 1.39) – push und pop Zeile für Zeile an der Kette, mit Java-Code, Iterator und Protokoll.
Der Stapel mit mitwachsendem Array aus Sedgewick/Wayne, Algorithmus 1.1 (Listing 1.37) – push, pop und das Umziehen in ein doppelt oder halb so großes Array Schritt für Schritt, mit Java-Code und Protokoll.
Sortieren mit dem Heap aus Sedgewick/Wayne, Algorithmus 2.7 (Listing 2.21) – Heap bauen und Sortdown Schritt für Schritt, im Baum und im Array, mit Java-Code und Ablaufprotokoll.
Die Max-Vorrangwarteschlange als Heap aus Sedgewick/Wayne, Algorithmus 2.6 (Listing 2.19) – selbst einfügen und entnehmen, swim und sink Schritt für Schritt im Baum und im Array.
Sortieren durch Zerlegen aus Sedgewick/Wayne, Algorithmus 2.5 (Listing 2.12) – Schritt für Schritt durch partition und Rekursion, mit Java-Code, Rekursionsbaum und Ablaufprotokoll.
Sortieren durch Mischen aus Sedgewick/Wayne, Algorithmus 2.4 (Listing 2.10) – Schritt für Schritt durch Rekursion und merge, mit Java-Code, Hilfsarray und Ablaufprotokoll.
Insertionsort mit Sprüngen aus Sedgewick/Wayne, Algorithmus 2.3 (Listing 2.8) – Schritt für Schritt durch die Abstände 13, 4 und 1, mit Java-Code und Ablaufprotokoll.
Sortieren durch Einfügen aus Sedgewick/Wayne, Algorithmus 2.2 (Listing 2.5) – Schritt für Schritt, mit Java-Code, Ablaufprotokoll und Inversionen.
Sortieren durch Auswählen aus Sedgewick/Wayne, Algorithmus 2.1 (Listing 2.4) – Schritt für Schritt, mit Java-Code und Ablaufprotokoll.
Die rekursive binäre Suche aus Sedgewick/Wayne, Listing 1.1 – zum Zuschauen, mit Aufrufstapel und Java-Code.
