- Wird eingefügt
- Verglichen
- Getauscht
- Sortierter Teil
Insertionsort
Insertionsort funktioniert so, wie viele Menschen Spielkarten auf der Hand sortieren. Vorn in der Liste wächst ein sortierter Teil: Der nächste Wert wird an jedem größeren Wert vorbei zurückgeschoben, bis er passt. Spielen Sie die Sortierung in beliebigem Tempo ab oder gehen Sie sie Vergleich für Vergleich durch, und verfolgen Sie die Zähler für Vergleiche, Vertauschungen und Durchläufe. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die Kacheln zählen Vergleiche, Vertauschungen und Durchläufe. 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
- 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.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
- Probieren Sie eine fast sortierte und eine umgekehrte Liste aus und vergleichen Sie, wie viele Vergleiche jede braucht.
So funktioniert Insertionsort
Der erste Wert allein ist ein sortierter Teil. Nehmen Sie den zweiten Wert und vergleichen Sie ihn mit dem davor; ist dieser größer, tauschen Sie beide. Vergleichen und tauschen Sie weiter, bis der Wert davor nicht größer ist oder der Wert vorn angekommen ist. Jetzt stehen die ersten beiden Werte in der richtigen Reihenfolge. Machen Sie dasselbe mit dem dritten Wert, dem vierten und so weiter bis zum Ende der Liste.
Schnell bei fast sortierten Listen
Jeder Durchlauf stoppt beim ersten Wert, der nicht größer ist. Ein Wert, der schon nahe an seinem Platz steht, kostet also nur ein oder zwei Vergleiche. Eine sortierte Liste braucht n − 1 Vergleiche und keine Vertauschung; eine umgekehrte Liste, der schlimmste Fall, braucht von beidem n(n − 1)/2. Die Zahl der Vertauschungen ist immer gleich der Zahl der Inversionen in der Startliste, also der Paare in falscher Reihenfolge. Deshalb wird Insertionsort oft für kurze oder fast sortierte Listen verwendet und in schnelleren Verfahren, um kleine Stücke fertig zu sortieren.
Häufig gestellte Fragen
Wie funktioniert Insertionsort?
Insertionsort baut vorn in der Liste einen sortierten Teil auf. Jeder Durchlauf nimmt den nächsten Wert und schiebt ihn an jedem größeren Wert davor vorbei zurück, bis er passt. Nach Durchlauf k stehen die ersten k + 1 Werte in der richtigen Reihenfolge, doch ein späterer Wert kann noch zwischen sie eingefügt werden.
Wie viele Vergleiche und Vertauschungen macht Insertionsort?
Die Zahl der Vertauschungen ist immer gleich der Zahl der Inversionen in der Startliste: keine bei einer sortierten Liste, n(n − 1)/2 bei einer umgekehrten. Die Vergleiche sind die Vertauschungen plus höchstens einer pro Durchlauf, also zwischen n − 1 und n(n − 1)/2.
Warum ist Insertionsort bei fast sortierten Listen schnell?
Weil ein Durchlauf stoppt, sobald er auf einen Wert trifft, der nicht größer ist. Steht jeder Wert nahe an seinem endgültigen Platz, ist jeder Durchlauf kurz, und die Laufzeit der ganzen Sortierung liegt nahe bei n.
Ist Insertionsort stabil?
Ja. Ein Wert wandert nur an echt größeren Werten vorbei. Gleiche Werte überholen sich also nie und behalten ihre ursprüngliche Reihenfolge.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Sortierung 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