Eine Sammlung von Michael Casagranda

Magic Book of Algorithms

Ein Notizbuch über Algorithmen: kurz erklärt, in lesbarem C# umgesetzt und mit einem Beispiel, das wirklich gelaufen ist.

Algorithmen: 19
Gruppen: 9
Sprache: C# / .NET 10

SRT

Sortieren

Daten in eine Reihenfolge bringen. Der Klassiker, an dem sich Laufzeitverhalten am besten begreifen lässt.

SRT-01

Bubble Sort

Benachbarte Werte tauschen, bis alles an seinem Platz steht.

O(n²) SRT-02

Merge Sort

Halbieren, bis nichts mehr zu tun ist, und sortiert wieder zusammenfügen.

O(n log n) SRT-03

Quick Sort

Ein Wert wird zum Trennpunkt, alles Kleinere wandert nach links.

O(n log n)

SRC

Suchen

Etwas Bestimmtes finden, ohne alles anzuschauen.

SRC-01

Binäre Suche

Jeder Schritt halbiert den Suchbereich, aus einer Million werden zwanzig Vergleiche.

O(log n)

PTH

Wegfindung

Den günstigsten Weg von hier nach dort finden, wenn nicht jeder Schritt gleich viel kostet.

PTH-01

Dijkstra

Der günstigste Weg, gefunden ohne jede Ahnung, wo das Ziel liegt.

O((K + N) log N) PTH-02

A*

Dijkstra mit einer Ahnung: derselbe Weg, ein Bruchteil der Arbeit.

O((K + N) log N)

MTH

Mathematik

Zahlenfolgen und Rechenverfahren, die in überraschend vielen Programmen auftauchen.

MTH-01

Fibonacci-Folge

Jede Zahl ist die Summe der beiden davor, und plötzlich steckt der goldene Schnitt darin.

O(n)

STA

Statistik

Was viele Zahlen zusammen verraten, auch wenn die einzelne Zahl nichts sagt.

STA-01

Benfords Gesetz

Echte Zahlen fangen viel öfter mit einer 1 an, als man denkt. Wer welche erfindet, weiß das nicht.

O(n)

RND

Zufall & Rauschen

Berechneter Zufall: reproduzierbar, schnell und die Grundlage für prozedural erzeugte Welten.

RND-01

PCG (Zufallszahlen)

Ein Zufallsgenerator aus wenigen Zeilen: schnell, gleichmäßig und jederzeit reproduzierbar.

O(1) RND-02

Perlin Noise

Aus rohem Zufall wird weiches Rauschen, aus dem sich Landschaften, Wolken und Texturen bauen lassen.

O(n · o) RND-03

Worley Noise

Punkte streuen, Abstände messen — und heraus kommen Zellen, Schuppen und rissiger Boden.

O(Pixel)

PRC

Prozedurale Erzeugung

Welten, Karten und Muster nach Regeln erzeugen, statt sie von Hand zu bauen.

PRC-01

Wave Function Collapse

Kacheln so lange festlegen, bis nur noch eine Möglichkeit übrig bleibt.

≈ O(Zellen · Kacheln²) PRC-02

Reaction-Diffusion

Zwei Stoffe, zwei Regeln, zwei Zahlen — und daraus Korallen, Streifen und Leopardenflecken.

O(Zellen · Schritte)

CMP

Kompression

Dieselbe Information mit weniger Platz speichern.

CMP-01

Lauflängenkodierung (RLE)

Statt zwölfmal W zu speichern, merkt man sich einfach: zwölfmal W.

O(n)

IMG

Bildverarbeitung

Aus Pixeln etwas anderes machen: filtern, umrechnen, neu zeichnen.

IMG-01

Weighted Voronoi Stippling

Ein Bild aus lauter Punkten: dicht, wo es dunkel ist, licht, wo es hell ist.

O(Pixel · Punkte · Runden) IMG-02

Dithering

Wenige Farben, die aus der Ferne wie viele aussehen.

O(Pixel) IMG-03

Kantenerkennung

Sobel, Prewitt, Laplace und Canny: vier Antworten auf die Frage, wo im Bild etwas anfängt.

O(Pixel · Kernel) IMG-04

Bloom

Helles strahlt über seine Ränder hinaus — ein Fehler der Optik, drei Zeilen nachgebaut.

O(Pixel · Radius) IMG-05

Marching Squares

Aus einem Feld von Zahlen wird eine Linie: sechzehn Fälle, mehr braucht es nicht.

O(Zellen)