QUICKSORT

Teilung um ein Pivot-Element · die Spur eines echten Durchlaufs

Als Merktafel gemacht statt als Tabelle: oben das, weswegen man sie aufhängt und über den Raum hinweg liest, darunter die vollständige Übersicht in kleinerer Schrift.

Drei Größen in einem Archiv — vom Blatt für den Kühlschrank bis zum Plakat für die Wand.

Formate: A4 · A3 · A2
Was Sie erhalten: Druckfertige PDFs, eines je Größe, sämtliche Schriftzeichen in Pfade umgewandelt — nichts zu installieren, nichts verrutscht.
Thema: Code · Anfänger · Merkblatt · Arbeitszimmer

Die Spur und alle Zahlen auf diesem Blatt stammen aus einem Durchlauf des Algorithmus selbst auf dem gezeigten Array; Vergleiche werden während des Durchlaufs gezählt, nicht aus einer Formel entnommen.

DER SCHLECHTESTE FALL FÜR QUICKSORT IST EIN BEREITS SORTIERTES ARRAY

Die Teilung am letzten Element kostet auf 64 gemischten Zahlen 329 Vergleiche. Auf denselben 64, bereits sortiert, sind es 2016: Jede Teilung schält genau ein Element ab, und statt Hälften entsteht eine Treppe.

Der schlechteste Fall ist hier also kein seltener Zufall, sondern die gewöhnlichsten Daten überhaupt. Deshalb wählen Bibliotheken das Pivot entweder zufällig oder nehmen den Median aus drei Werten.

Der Name „Quicksort“ beschreibt den Durchschnittsfall, kein Versprechen. Ein Algorithmus, der sich auf sortierten Daten am schlechtesten verhält, ist genau wegen dieser Schwäche wissenswert.

Auf der Tafel

Die Spur und alle Zahlen auf diesem Blatt stammen aus einem Durchlauf des Algorithmus selbst auf dem gezeigten Array; Vergleiche werden während des Durchlaufs gezählt, nicht aus einer Formel entnommen.
Farbe trägt Bedeutung, aber die Bedeutung hängt nie allein an der Farbe — die Tafel liest sich auch in Schwarzweiß.
Nichts darüber, wie sie entstanden ist: die Tafel trägt nur, was die Leserin oder der Leser braucht.

Drucken

Drei Größen im Archiv: A4 — 210×297 mm, A3 — 297×420 mm, A2 — 420×594 mm.
Der gesamte Text ist in Pfade umgewandelt. Keine Schriften zu installieren, nichts verrutscht auf einem anderen Gerät.
Weißer Hintergrund und sparsame Füllflächen — sie druckt auf einem Heimdrucker, ohne die Patrone zu leeren.
Ränder von mindestens 10 mm: ein Heimdrucker druckt nicht randlos.
Keine Linie dünner als 0,3 mm, damit beim Druck nichts verschwindet.

Warum man den Zahlen trauen kann. Jede zählbare Zahl hier ist aus Daten berechnet, nicht abgetippt, und die Tafel muss 4 unabhängige Prüfungen bestehen, bevor sie gebaut werden darf — wie viele Elemente es gibt, in welcher Reihenfolge, und die Aussage im hervorgehobenen Kasten selbst. Scheitert eine, gibt es keine Datei.

QUICKSORT

DER SCHLECHTESTE FALL FÜR QUICKSORT IST EIN BEREITS SORTIERTES ARRAY

Auf der Tafel

Drucken

Ähnliche Tafeln

BIT, BYTE, KILOBYTE

HTTP-STATUSCODES

PYTHON vs GO

PYTHON vs JAVASCRIPT