Startseite › Entwickler-Tools › Sortieralgorithmen visualisieren

Sortieralgorithmen visualisieren

Sieh zu, wie sieben klassische Sortieralgorithmen ein Array Balken für Balken umordnen. Folge der hervorgehobenen Pseudocode-Zeile, zähle Vergleiche, Vertauschungen und Schreibzugriffe, verlangsame bis zu Einzelschritten oder lass alle sieben auf denselben Daten gegeneinander antreten, um die O-Notation in Aktion zu sehen.

Zuletzt aktualisiert:

Vergleiche0
Vertauschungen0
Schreibzugriffe0
Schritte0
StatusBereit
Eigene Zahlen verwenden

Bis zu 250 nicht negative ganze Zahlen (0 bis 9999), getrennt durch Kommas oder Leerzeichen.

Anzeige
Anzeige

Anleitung: Sortieralgorithmen visualisieren

  1. Wähle einen Algorithmus und die Art der Startdaten (zufällig, fast sortiert, umgekehrt oder wenige verschiedene Werte).
  2. Stell Array-Größe und Geschwindigkeit mit den Schiebereglern ein. Bei kleinen Arrays steht jeder Wert über seinem Balken.
  3. Klicke auf „Start“ für die Animation, auf Schritt (oder die Pfeiltaste nach rechts), um eine Operation weiterzugehen, oder auf Sofort beenden, um die Endwerte zu sehen.
  4. Lies mit im Pseudocode-Bereich: Die aktuelle Zeile ist hervorgehoben, und der Satz darunter erklärt die Operation.
  5. Klicke auf „Alle Algorithmen um die Wette“, um jeden Algorithmus auf demselben Array laufen zu lassen und zu vergleichen, wie viele Schritte jeder braucht.

Spickzettel zur Komplexität von Sortieralgorithmen

AlgorithmusBester FallMittlerer FallSchlechtester FallZusätzlicher SpeicherStabilGeeignet für
BubblesortO(n)O(n²)O(n²)O(1)JaLehre; Erkennen eines bereits sortierten Arrays
InsertionsortO(n)O(n²)O(n²)O(1)JaKleine oder fast sortierte Arrays, Online-Eingaben
SelectionsortO(n²)O(n²)O(n²)O(1)NeinMinimale Vertauschungen (höchstens n − 1)
MergesortO(n log n)O(n log n)O(n log n)O(n)JaGarantierte Geschwindigkeit, verkettete Listen, externes Sortieren
QuicksortO(n log n)O(n log n)O(n²)O(log n)NeinSchnelles universelles Sortieren im Arbeitsspeicher
HeapsortO(n log n)O(n log n)O(n log n)O(1)NeinGarantie für den schlechtesten Fall ohne zusätzlichen Speicher
Radixsort (LSD)O(d·(n+b))O(d·(n+b))O(d·(n+b))O(n+b)JaGanzzahlen oder Schlüssel fester Länge

n ist die Anzahl der Elemente, d die Anzahl der Stellen des größten Schlüssels und b die Basis (hier 10). Jedes Verfahren, das nur Elemente vergleicht, braucht im schlechtesten Fall mindestens etwa log₂(n!) ≈ n·log₂(n) − 1.44n Vergleiche. Deshalb ist O(n log n) das Beste, was ein vergleichsbasiertes Sortierverfahren erreichen kann.

Experimente, die sich lohnen

  • Fast sortierte Daten: Lass Insertionsort und Bubblesort laufen, dann Quicksort. Die einfachen Algorithmen sind in knapp n Schritten fertig, während Quicksort nach Lomuto auf seinen schlechtesten Fall abbremst.
  • Wenige verschiedene Werte: Radixsort braucht unabhängig von der Reihenfolge gleich viele Durchläufe, während Quicksort mit diesem Partitionierungsschema bei doppelten Schlüsseln viele überflüssige Vergleiche macht.
  • Zähle die Vertauschungen: Selectionsort macht höchstens n − 1 Vertauschungen, aber immer n(n − 1)/2 Vergleiche; Bubblesort kann bis zu n(n − 1)/2 Vertauschungen machen.
  • Verdopple die Größe: Von 50 auf 100 Elemente vervierfachen sich die Vergleiche bei O(n²)-Algorithmen ungefähr, bei Mergesort und Heapsort verdoppeln sie sich nur etwas mehr als.

Häufige Fragen

Welcher Sortieralgorithmus ist der schnellste?

Bei allgemeinen Daten schlagen O(n log n)-Algorithmen wie Quicksort, Mergesort und Heapsort die O(n²)-Verfahren wie Bubblesort, Insertionsort und Selectionsort, sobald Arrays mehr als ein paar Dutzend Elemente haben. Quicksort ist in der Praxis meist am schnellsten, dank cachefreundlicher Partitionierung an Ort und Stelle, doch sein schlechtester Fall ist O(n²). Insertionsort gewinnt bei winzigen oder fast sortierten Arrays, weshalb Bibliotheksverfahren wie Timsort und Introsort für kleine Teile darauf umschalten.

Warum wird Quicksort hier bei sortierten oder umgekehrten Daten langsam?

Dieser Visualisierer verwendet die Lehrbuch-Partitionierung nach Lomuto mit dem letzten Element als Pivot. Bei bereits sortierten oder umgekehrten Daten ist dieses Pivot immer der kleinste oder größte Wert, sodass jede Partitionierung nur ein Element abtrennt und der Durchlauf etwa n²/2 Vergleiche braucht. Echte Bibliotheken vermeiden das mit zufälligen oder Median-aus-drei-Pivots.

Was ist ein stabiles Sortierverfahren?

Ein stabiles Sortierverfahren behält die ursprüngliche Reihenfolge von Elementen mit gleichem Schlüssel bei. Bubblesort, Insertionsort, Mergesort und Radixsort sind stabil; Selectionsort, Quicksort und Heapsort nicht. Stabilität ist wichtig, wenn du nacheinander nach mehreren Feldern sortierst, etwa erst nach Name und dann nach Abteilung.

Wie kommt Radixsort mit null Vergleichen aus?

Radixsort vergleicht nie zwei Werte. Es verteilt die Zahlen Stelle für Stelle auf zehn Buckets, beginnend bei der Einerstelle, mit einem stabilen Zähldurchlauf. Seine Laufzeit beträgt O(d·(n + b)) für d Stellen und Basis b, daher kann es bei Ganzzahlen fester Länge vergleichsbasierte Verfahren schlagen, deren Untergrenze bei etwa n·log₂(n) Vergleichen liegt.

Was zählt als Schritt?

Ein Schritt ist eine elementare Operation: zwei Elemente vergleichen, zwei Elemente vertauschen, einen Wert ins Array schreiben oder (bei Radixsort) eine Ziffer lesen. Eine Vertauschung zählt als zwei Schreibzugriffe. Schritte steuert der Geschwindigkeitsregler und vergleicht das Wettrennen, sie spiegeln also die geleistete Arbeit wider und nicht die tatsächliche Zeit auf deinem Computer.

Was bedeuten die Farben?

Bernsteinfarbene Balken werden verglichen oder gelesen, rote werden vertauscht oder geschrieben, Lila markiert das Pivot bzw. den aktuellen Schlüssel oder das Minimum, und dunkelgrüne Balken haben ihre endgültige Position erreicht. Bei Mergesort zeigt der schattierte Bereich den Teil des Arrays, der gerade zusammengeführt wird.

Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?

Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.

Ähnliche Tools

Alle Code-Playgrounds & Tester ansehen →