Simulic
Deutsch

Sortieren sichtbar gemacht: Bubblesort, Selectionsort, Insertionsort und Mergesort Schritt für Schritt

InformatikAlgorithmen und ProblemlösenAlter 13–14

Wird geladen …

Mit meiner Klasse nutzen ✨ Mit KI anpassen Problem melden

Eine Zahlenfolge wird als Balken dargestellt; wählen Sie Bubblesort, Selectionsort, Insertionsort oder Mergesort und drücken Sie „Schritt“ oder „Starten“. Jeder Schritt hebt das verglichene Paar, das vertauschte Paar und den bereits sortierten Teil hervor und zählt Vergleiche und Vertauschungen; die passende Pseudocode-Zeile wird ebenfalls markiert. Mergesort teilt die Balken Ebene für Ebene in Hälften und fügt sie wieder zusammen, und eine Tabelle und ein Diagramm vergleichen die Vergleichszahlen aller vier Algorithmen (n log n gegenüber n²). Die Lernenden können vor dem Start einen Balken ziehen, um seinen Wert zu ändern.

Lektion: Sortieralgorithmen (Bubblesort, Selectionsort, Insertionsort, Mergesort), verschachtelte Schleifen und Teile und herrsche

Was sie zeigt

Bubblesort, Selectionsort und Insertionsort ordnen eine Liste mit verschachtelten Schleifen, deshalb brauchen sie bei n Elementen im ungünstigsten Fall etwa n²/2 Vergleiche. Selectionsort macht höchstens n − 1 Vertauschungen, Bubblesort kann nach einem Durchlauf ohne Vertauschung aufhören, und Insertionsort ist bei fast sortierten Daten sehr schnell. Mergesort arbeitet nach dem Prinzip Teile und herrsche: Die Liste wird immer wieder halbiert, bis einzelne Elemente übrig sind, dann werden sortierte Hälften zusammengeführt. Jede seiner etwa log₂n Ebenen kostet höchstens n Vergleiche, also braucht es bei jeder Anordnung rund n·log₂n Vergleiche, für großes n weit weniger als n²/2.

So funktioniert es

Beginnen Sie mit etwa 8 Elementen und drücken Sie Schritt; die Lernenden sagen jeden hervorgehobenen Vergleich vorher und verfolgen die Pseudocode-Zeile. Drücken Sie Starten, notieren Sie Vergleiche und Vertauschungen, wechseln Sie dann den Algorithmus und wiederholen Sie das mit den Optionen Absteigend und Fast sortiert. Wählen Sie Mergesort, um zu sehen, wie sich die Balken Ebene für Ebene teilen und wieder zusammenfügen; Tabelle und Diagramm darunter schicken dieselbe Folge durch alle vier Algorithmen. Vor dem Start lässt sich auch ein Balken ziehen.

Einstellbare Parameter

  • Anzahl der Elemente 4–30
  • Algorithmus Bubblesort, Selectionsort, Insertionsort, Mergesort
  • Anfangsfolge Zufällig, Absteigend (ungünstigster Fall), Fast sortiert
  • Ablaufgeschwindigkeit 1–20 Schritte/s
  • Vergleich aller vier Algorithmen anzeigen

Fragen zum Erkunden

  1. Welches Element steht nach dem ersten Durchlauf von Bubblesort sicher an seiner endgültigen Stelle?
  2. Welcher Algorithmus braucht bei einer absteigenden Folge die wenigsten Vertauschungen, und warum?
  3. Warum ist Insertionsort bei einer fast sortierten Folge so schnell fertig?

Ähnliche Simulationen