EINFÜGESORTIERUNG

wie man Karten in der Hand ordnet · 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.

AUF FAST SORTIERTEN DATEN SCHLÄGT SIE ALLES

Einfügesortierung gilt als langsam — und das stimmt nur für Unordnung. Auf 64 umgedrehten Zahlen macht sie 2016 Vergleiche, auf 64 bereits sortierten nur 63 — einen pro Element.

Deshalb meiden echte Bibliothekssortierungen sie nicht, sondern schließen mit ihr ab: Timsort, in Python und in Java, sucht zuerst nach bereits geordneten Abschnitten, fügt diese zusammen und übernimmt die kurzen Reststücke genau mit Einfügesortierung.

Die Frage „welcher Algorithmus ist schneller“ ist deshalb nur halb gestellt. Die andere Hälfte lautet: auf welchen Daten. Ein sortiertes Array ist keine Seltenheit, sondern der Normalfall.

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.

EINFÜGESORTIERUNG

AUF FAST SORTIERTEN DATEN SCHLÄGT SIE ALLES

Auf der Tafel

Drucken

Ähnliche Tafeln

BIT, BYTE, KILOBYTE

HTTP-STATUSCODES

PYTHON vs GO

PYTHON vs JAVASCRIPT