So funktioniert es
Sortieren heißt Elemente in Ordnung bringen — vom Kleinsten zum Größten, von A bis Z. Alle Algorithmen unten lösen dasselbe Problem; sie unterscheiden sich nur in der Strategie, und die Strategie beobachtest du. Wähle einen Algorithmus (oder den Rennmodus für alle sechs auf einmal), wähle eine Eingabe und drücke Play. Die Balken leuchten während die Engine arbeitet: Gelb markiert einen Vergleich, Rot eine Bewegung oder einen Tausch, Violett den Pivot undGrün fertige Positionen.
Die Steuerung erinnert an einen Videoplayer, weil die Engine einer ist: Play und Pause mit der Leertaste, Einzelschritte mit der Pfeil-nach-rechts-Taste, Neustart mit R, neue Liste mit N, mischen mit S und Geschwindigkeiten von 0,25× bis 8×. Ein Code-Panel hebt jede Pseudocode-Zeile hervor während sie läuft, sodass Animation und Programm synchron bleiben. Probiere dasselbe Rennen zweimal: einmal mit umgekehrter Liste, einmal fast sortiert, und sieh Insertion Sort vom Ende des Feldes an die Spitze springen.
Die sechs Algorithmen
Drei sind einfache quadratische Verfahren — leicht zu schreiben, schmerzhaft im Maßstab. Drei sind effiziente Verfahren, die mit Teilen-und-Herrschen oder einer cleveren Datenstruktur O(n log n) erreichen. Jedes Beispiel unten ist vollständiges, lauffähiges Python auf einer gewöhnlichen Liste.
Bubble Sort — der Nachbarschaftstausch
Laufe die Liste entlang, vergleiche Nachbarn und vertausche ungeordnete Paare. Mit jedem Durchlauf «blubbert» das größte unsortierte Element an seinen endgültigen Platz, der nächste Durchlauf kann also einen Schritt kürzer sein. Wenn ein kompletter Durchlauf nichts vertauscht, ist die Liste bereits sortiert und der Algorithmus stoppt früh — seine einzige rettende Eigenschaft, die bei bereits sortierter Eingabe O(n) ergibt.
def bubble_sort(a):
n = len(a)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return aSelection Sort — nimm das Kleinste, wiederhole
Teile die Liste in sortierte Front und unsortierten Rest. Suche in jedem Schritt den gesamten unsortierten Rest nach seinem Minimum ab und tausche es an seinen Platz. Er macht immer gleich viele Vergleiche — etwa n²/2 — egal wie sortiert die Eingabe schon ist; darum sind bester, mittlerer und schlechtester Fall alle O(n²). Seine Tugend: höchstens n Vertauschungen, einst nützlich als Tauschen noch teuer war.
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return aInsertion Sort — die Kartenspieler-Methode
So wie man Spielkarten sortiert: Nimm das nächste Element und schiebe es nach links an allem Größeren vorbei, bis es passt. Bei fast sortierten Daten bewegt sich fast nichts, also läuft er in O(n) — in dem Fall der Schnellste im Raum, und der Grund, warum echte hybride Sortierer ihn für winzige Teillisten nutzen. Bei umgekehrten Daten legt jedes Element die volle Strecke zurück: schlechtester Fall O(n²). Er ist stabil und braucht keinen Extraspeicher.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return aMerge Sort — teilen, herrschen, mischen
Halbiere die Liste, sortiere jede Hälfte gleich (die Rekursion endet bei Einzelelementen, die per Definition sortiert sind) und mische die Hälften, indem du immer das kleinere Frontelement nimmst. Die Teilung ist immer ausgeglichen, also kostet jede Ebene O(n) und es gibt log n Ebenen: O(n log n) garantiert, in jedem Fall. Der Preis ist O(n) Extraspeicher zum Mischen, und er ist stabil — gleiche Elemente kreuzen sich nie.
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]Quick Sort — teilen um einen Pivot
Wähle einen Pivot und partitioniere: Alles Kleinere geht nach links, alles Größere nach rechts. Sortiere jede Seite gleich. Wenn Pivots nahe der Mitte landen, ist die Rekursion log n Ebenen tief und das Ganze ist O(n log n) mit winzigen Konstanten und nur O(log n) Extraspeicher für die Rekursion — in der Praxis meist am schnellsten. Landen sie am Extrem, behält eine Seite fast alles und er fällt auf O(n²) zurück. Dieser Simulator wählt Pivots per Median-of-Three (erstes, mittleres und letztes Element), was den schlechten Fall bei echten Daten selten macht. Das Python-Beispiel unten nimmt der Kürze halber einfach das letzte Element als Pivot.
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p, i = a[hi], lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return aHeap Sort — eine getarnte Prioritätswarteschlange
Mache die Liste zu einem Max-Heap: einem binären Baum, gepackt ins Array, in dem jeder Eltern- größer als seine Kinder ist, sodass das Maximum an Position null steht. Nimm das Maximum wiederholt heraus, tausche es ans Ende, schrumpfe den Heap um eins und stelle die Eigenschaft durch Versickern wieder her. Garantiert O(n log n) mit O(1) Extraspeicher — aber das springende Zugriffsmuster missfällt den Prozessor-Caches, darum verliert er gegen Quick und Merge Sort auf der Stoppuhr, trotz Gleichstands auf dem Papier.
def heap_sort(a):
def sift(lo, n, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[lo + l] > a[lo + m]:
m = l
if r < n and a[lo + r] > a[lo + m]:
m = r
if m == i:
return
a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
i = m
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift(0, n, i)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift(0, end, 0)
return aDie Tabelle lesen
Big-O beschreibt Wachstum, keine Stoppuhr: Konstanten und Hardware werden absichtlich ignoriert, damit dieForm der Skalierung sichtbar wird. Die Tabelle unten ist die Standardreferenz (Cormen et al.,Introduction to Algorithms; NIST-Wörterbuch der Algorithmen und Datenstrukturen). „Stabil“ heißt: Gleiche Elemente behalten ihre ursprüngliche Reihenfolge.
| Algorithmus | Bester | Mittel | Schlechtester | Extraspeicher | Stabil |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Ja |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Nein |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Ja |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein |
Probier es im Simulator: Lass alle sechs erst auf umgekehrter, dann auf fast sortierter Liste laufen. Die Zielreihenfolge dreht sich um — Insertion Sort springt vom Ende des Feldes an die Spitze — und keine Formel lehrt das so wie Zusehen.
Drei häufige Irrtümer
„Quick Sort ist immer am schnellsten.“ Im Mittel gehört er zu den schnellsten, aber ein einfacher Quick Sort hat einen schlechtesten Fall von O(n²), etwa wenn das Pivot-Element immer an einem Ende der Liste landet. Merge Sort und Heap Sort bleiben bei jeder Eingabe bei O(n log n).
„Die einfachen quadratischen Verfahren sind nutzlos.“ Insertion Sort wird häufig für kleine Listen verwendet und ist bei fast sortierten Listen sehr gut. Sortierroutinen in der Praxis sind meist Hybride, die für kleine Teilstücke auf Insertion Sort umschalten.
„Ein stabiles Sortierverfahren ist eines, das nie versagt.“ Stabilität hat eine genaue Bedeutung: Elemente mit gleichem Schlüssel behalten die Reihenfolge, die sie vor dem Sortieren hatten. Merge Sort und Insertion Sort sind stabil; Quick Sort und Heap Sort sind es in ihrer üblichen Form nicht.
Besucherfragen
Welchen Sortieralgorithmus soll ich in echtem Code verwenden?
Fast immer die eingebaute Sortierung der Sprache: sorted() in Python, Array.sort() in JavaScript oder Arrays.sort() in Java für Objekte. Das sind praxiserprobte Hybride (Python und Java nutzen Timsort) mit O(n log n) Laufzeit, sie sind stabil und millionenfach getestet. Die sechs Algorithmen auf dieser Seite lehren die Ideen dahinter, sie ersetzen sie nicht.
Wenn Bubble Sort langsam ist, warum wird es noch gelehrt?
Weil es die einfachstmögliche Sortieridee ist: Nachbarn vergleichen, bei Unordnung vertauschen, wiederholen. Ihn im Rennmodus gegen Merge Sort leiden zu sehen, lehrt mehr über O(n²)-Wachstum als jede Formel. Der frühe Abbruch zeigt außerdem, dass derselbe Algorithmus bei bereits sortierter Eingabe O(n) und allgemein O(n²) sein kann.
Was bedeutet es, dass eine Sortierung stabil ist?
Eine stabile Sortierung behält gleiche Elemente in ihrer ursprünglichen relativen Reihenfolge. Das zählt beim Sortieren nach mehreren Schlüsseln: Sortiere eine Klasse erst nach Name, dann nach Note mit einem stabilen Algorithmus, und Schüler mit gleicher Note bleiben alphabetisch geordnet. Merge, Insertion und Bubble Sort sind stabil; Selection, Quick und Heap Sort sind es in üblicher Implementierung nicht.
Warum ist Quick Sort nicht immer am schnellsten, wenn es im Mittel O(n log n) ist?
Weil sein schlechtester Fall O(n²) ist: Bei unglücklichen Pivots trennt jede Partitionierung nur ein Element ab. Gute Implementierungen vermeiden das mit Median-of-Three-Pivotwahl (wie in diesem Simulator) oder Randomisierung. Merge Sort garantiert O(n log n), braucht aber O(n) Extraspeicher; Heap Sort garantiert O(n log n) in-place, springt aber durch den Speicher, was moderne Caches nicht mögen.
Führt der Simulator die Algorithmen wirklich aus oder ist es nur Animation?
Er führt sie wirklich aus. Jeder Algorithmus läuft mit seiner echten Logik und sendet Schritt-Ereignisse — Vergleich, Tausch, Überschreiben, Pivot, Mischen, Heapify — die das animierte Diagramm abspielt. Im Rennmodus laufen alle sechs mit derselben Eingabe nebeneinander, der Vergleich ist also fair. Der Wörtermodus sortiert Text ohne auf Akzente und Großschreibung zu achten.
Was zählt die Big-O-Notation eigentlich?
Wie die Zahl der Grundschritte mit der Eingabe wächst, konstante Faktoren ignoriert. O(n²) heißt: Doppelte Eingabe vervierfacht grob die Arbeit; O(n log n) heißt: Doppelte Eingabe verdoppelt sie wenig mehr als. Bei n = 1.000.000 ist das der Unterschied zwischen rund einer Billion Operationen und zwanzig Millionen — Minuten oder sogar Stunden gegen Sekundenbruchteile.
Quellen und weiterführende Literatur
- Introduction to Algorithms — MIT Press (Cormen et al.)
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
- Algorithms course — Khan Academy
Dieses Exponat zitieren
Eurekarium. (2026). Sortierlabor. https://eurekarium.com/de/computing/sorting-lab/
Zuletzt aktualisiert: