Sieger
Operationen
Fertig

  • Verglichen
  • Markiert (Minimum, Pivot oder Schlüssel)
  • Getauscht oder verschoben
  • Platziert
Platz Verfahren Vergleiche oder Lesezugriffe Vertauschungen oder Verschiebungen Operationen

Mehr über Sortierverfahren

Sortier-Wettrennen

Welches Sortierverfahren ist am schnellsten? Das hängt von der Liste ab. Das Sortier-Wettrennen lässt alle acht Sortierverfahren gleichzeitig auf derselben Liste laufen, jedes auf seiner eigenen Bahn, und zählt jeden Vergleich, jeden Lesezugriff, jede Vertauschung und jede Verschiebung als eine Operation. Die Bahnen rücken vor, während ihre Zählungen steigen. So sehen Sie die effizienten Verfahren ins Ziel kommen, während die langsamen noch tauschen, und wie sich die Reihenfolge ändert, wenn die Liste fast sortiert oder umgekehrt ist. Drücken Sie „Abspielen“, um alle acht Sortierverfahren auf derselben Liste um die Wette laufen zu lassen, oder gehen Sie mit „Schritt“ und „Zurück“ eine Operation nach der anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Jeder Vergleich, jeder Lesezugriff, jede Vertauschung und jede Verschiebung zählt als eine Operation. Jede Bahn rückt vor, sobald ihre eigene Zählung steigt, also ist das Verfahren mit den wenigsten Operationen zuerst fertig. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge: zufällig, fast sortiert, umgekehrt oder mit wenigen verschiedenen Werten. Oder geben Sie eigene Zahlen ein.
  2. Drücken Sie „Abspielen“ und beobachten Sie die acht Bahnen. „Schritt“ und „Zurück“ gehen eine Operation vor oder zurück; mit dem Schrittregler springen Sie an jede Stelle des Rennens.
  3. Vergleichen Sie die Ergebnistabelle, und probieren Sie dann eine fast sortierte und eine umgekehrte Liste, um zu sehen, wie sich die Rangfolge ändert.

So funktioniert das Rennen

Alle acht Verfahren bekommen dieselbe Liste. Jeder Vergleich zweier Werte, jede Ziffer und jeder Wert, den Radixsort und Countingsort lesen, und jede Vertauschung oder Verschiebung zählt als eine Operation. In jedem Moment des Rennens zeigt jede Bahn, wie weit ihr Verfahren mit so vielen Operationen gekommen ist. Ein Verfahren, das weniger Operationen braucht, ist früher am Ende. Die Ergebnistabelle zeigt für jedes Verfahren die Vergleiche, die Vertauschungen oder Verschiebungen und die Summe.

Was die Ergebnisse zeigen

Bei 40 zufälligen Werten braucht Countingsort etwa 120 Operationen, Radixsort etwa 240, Quicksort etwa 260 und Mergesort etwa 380. Es folgt Heapsort mit etwa 490, während Selectionsort und Insertionsort etwa 820 brauchen und Bubblesort über 1.100. Bei einer fast sortierten Liste gewinnt Insertionsort mit etwa 50, und Bubblesort wird Zweiter. Bei einer umgekehrten Liste brauchen Bubblesort und Insertionsort beide 1.560. Countingsort und Radixsort gewinnen so oft, weil diese Werte kleine ganze Zahlen sind; bei anderen Daten sind sie gar nicht einsetzbar.

Häufig gestellte Fragen

Welches Sortierverfahren ist am schnellsten?

Das hängt von den Daten ab. Bei kleinen ganzen Zahlen brauchen Countingsort und Radixsort die wenigsten Operationen. Bei allgemeinen Daten sind Quicksort und Mergesort auf zufälligen Listen am schnellsten, und Insertionsort ist auf fast sortierten Listen am schnellsten. Bubblesort und Selectionsort sind langsam, außer bei sehr kleinen Listen.

Was zählt als Operation?

Jeder Vergleich zweier Werte, jede Ziffer und jeder Wert, den Radixsort und Countingsort lesen, und jede Vertauschung oder Verschiebung eines Werts. Das ist ein einfaches Modell: Echte Laufzeiten hängen auch vom Speicherzugriff und von den Kosten jeder Operation ab.

Warum gewinnen Countingsort und Radixsort so oft?

Weil sie nie Werte vergleichen. Sie nutzen, dass die Werte kleine ganze Zahlen sind, daher wächst ihre Arbeit mit n plus dem Wertebereich, nicht mit n log n. Bei Daten, die nicht aus kleinen ganzen Zahlen bestehen, sind sie nicht anwendbar.

Warum gewinnt Insertionsort bei einer fast sortierten Liste?

Weil seine Arbeit der Zahl der Werte plus der Zahl der Paare in falscher Reihenfolge entspricht. Eine fast sortierte Liste hat sehr wenige solche Paare, also rückt jeder Wert nur ein oder zwei Plätze.

Werden meine Zahlen irgendwohin gesendet?

Nein. Das Rennen läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor