- Verglichen
- Bisheriges Minimum
- Getauscht
- Platziert
Selectionsort
Selectionsort baut die sortierte Liste von vorne auf. Jeder Durchlauf durchsucht die noch unsortierten Werte, merkt sich den kleinsten und tauscht ihn an die erste unsortierte Stelle. Spielen Sie die Sortierung in beliebigem Tempo ab oder gehen Sie einen Vergleich nach dem anderen 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.
- Beobachten Sie, wie sich der bisher kleinste Wert während der Suche ändert und wie ihn am Ende jedes Durchlaufs eine Vertauschung an seinen Platz bringt.
So funktioniert Selectionsort
Sehen Sie sich jeden Wert der Liste an und merken Sie sich den kleinsten. Tauschen Sie ihn mit dem ersten Wert: Die erste Stelle ist jetzt endgültig. Machen Sie dann dasselbe mit dem Rest der Liste, eine Stelle weiter hinten beginnend. Nach n − 1 Durchläufen steht jeder Wert an seinem Platz; der letzte ergibt sich von selbst.
Viele Vergleiche, wenige Vertauschungen
Die Suche hört nie früher auf, denn erst nach dem Blick auf jeden verbleibenden Wert steht fest, welcher der kleinste ist. Daher macht Selectionsort bei n Werten genau n(n − 1)/2 Vergleiche, ob die Liste sortiert, umgekehrt oder zufällig ist. Dafür macht es höchstens n − 1 Vertauschungen, eine pro Durchlauf. Das macht es zu einer vernünftigen Wahl, wenn das Bewegen eines Werts viel mehr kostet als ein Vergleich.
Häufig gestellte Fragen
Wie funktioniert Selectionsort?
Es wählt immer wieder den kleinsten noch unsortierten Wert aus und tauscht ihn an die erste unsortierte Stelle. Nach Durchlauf k stehen an den ersten k Stellen die k kleinsten Werte in Reihenfolge.
Wie viele Vergleiche und Vertauschungen macht Selectionsort?
Immer n(n − 1)/2 Vergleiche bei n Werten: 45 bei 10 Werten, 780 bei 40. Die Zahl der Vertauschungen ist höchstens n − 1, eine pro Durchlauf, und kleiner, wenn der kleinste Wert schon an seinem Platz steht.
Warum dauert eine sortierte Liste so lange wie eine umgekehrte?
Weil jeder Durchlauf jeden verbleibenden Wert ansehen muss, um sicher den kleinsten zu finden. Anders als Bubblesort und Insertionsort kann Selectionsort an seinen Vergleichen nicht erkennen, dass die Liste schon sortiert ist.
Ist Selectionsort stabil?
Nicht in dieser üblichen Form. Eine Vertauschung kann einen Wert an einem gleichen vorbeitragen: In 2, 2, 1 wird die erste 2 mit der 1 getauscht und landet hinter der zweiten 2. Eine Variante, die Werte verschiebt statt tauscht, ist stabil, braucht aber mehr Bewegungen.
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