Selectionsort

Selectionsort sortiert eine Liste so, wie viele Menschen Spielkarten auf der Hand sortieren: die kleinste suchen, nach vorne legen, dann die kleinste vom Rest suchen. Es macht viele Vergleiche, aber sehr wenige Vertauschungen, und seine Laufzeit hängt kaum von der Reihenfolge der Liste ab.

Balken unterschiedlicher Höhe werden sortiert, links der sortierte Teil, der kleinste verbleibende Balken hervorgehoben und ein Pfeil, der zeigt, wie er an seinen Platz getauscht wird
Balken unterschiedlicher Höhe werden sortiert, links der sortierte Teil, der kleinste verbleibende Balken hervorgehoben und ein Pfeil, der zeigt, wie er an seinen Platz getauscht wird

Die Idee

Teilen Sie die Liste in einen sortierten Teil links, anfangs leer, und einen unsortierten Teil rechts. Durchsuchen Sie den unsortierten Teil und merken Sie sich, wo sein kleinster Wert steht. Tauschen Sie diesen Wert mit dem ersten unsortierten Wert: Der sortierte Teil ist um eins gewachsen. Wiederholen Sie das, bis nur noch ein Wert übrig ist, und der muss der größte sein.

Ein Beispiel

Nehmen Sie 5, 1, 4, 2, 8. Der erste Durchlauf prüft alle fünf Werte, findet 1 als kleinsten und tauscht ihn mit 5: 1, 5, 4, 2, 8. Der zweite Durchlauf prüft 5, 4, 2, 8, findet 2 und tauscht ihn mit 5: 1, 2, 4, 5, 8. Der dritte Durchlauf findet 4 schon an seinem Platz, der vierte ebenso 5, also bewegt sich nichts. Das sind 4 + 3 + 2 + 1 = 10 Vergleiche und nur 2 Vertauschungen. Bubblesort braucht für dieselbe Liste 4 Vertauschungen.

Immer gleich viele Vergleiche

Um sicher zu sein, welcher Wert der kleinste ist, muss die Suche jeden verbleibenden Wert ansehen. Durchlauf 1 macht n − 1 Vergleiche, Durchlauf 2 macht n − 2 und so weiter bis 1, zusammen n(n − 1)/2. Diese Zahl hängt nicht von der Liste ab: Eine sortierte Liste kostet genau so viele Vergleiche wie eine umgekehrte. Selectionsort hat keinen vorzeitigen Abbruch, denn eine Suche, die den kleinsten Wert schon vorne findet, hat über den Rest nichts erfahren.

Wenige Vertauschungen

Jeder Durchlauf macht höchstens eine Vertauschung, daher macht Selectionsort nie mehr als n − 1 Vertauschungen, und es lässt die Vertauschung aus, wenn der kleinste Wert schon an seinem Platz steht. Bubblesort und Insertionsort machen so viele Vertauschungen, wie es Paare in falscher Reihenfolge gibt, also bis zu etwa n²/2. Wenn das Schreiben eines Werts viel teurer ist als das Lesen von zweien, etwa bei Speicher, der sich mit jedem Schreibvorgang abnutzt, ist die kleine Zahl an Vertauschungen ein Vorteil.

Nicht stabil

Ein Sortierverfahren ist stabil, wenn gleiche Werte ihre ursprüngliche Reihenfolge behalten. Selectionsort ist es nicht, weil eine Vertauschung über eine weite Strecke einen Wert an einem gleichen vorbeitragen kann. In 2, 2, 1 tauscht der erste Durchlauf die erste 2 mit der 1. Das ergibt 1, 2, 2, wobei die beiden Zweien nun in umgekehrter Reihenfolge stehen. Eine Variante, die die Werte dazwischen verschiebt statt zu tauschen, ist stabil, bewegt aber viel mehr Werte.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie „Abspielen“, oder drücken Sie „Schritt“, um einen Vergleich nach dem anderen durchzugehen. Der gerade geprüfte Wert ist hervorgehoben, der bisher kleinste Wert hat eine eigene Farbe, und jeder Durchlauf endet mit einer Vertauschung in den sortierten Teil links. Probieren Sie eine sortierte und eine umgekehrte Liste: Die Vergleiche sind gleich, nur die Vertauschungen unterscheiden sich.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Selectionsort?

O(n²) in jedem Fall: genau n(n − 1)/2 Vergleiche bei n Werten, egal in welcher Reihenfolge. Es macht höchstens n − 1 Vertauschungen und braucht nur O(1) zusätzlichen Speicher.

Was ist der Unterschied zwischen Selectionsort und Bubblesort?

Bubblesort tauscht unterwegs Nachbarn und kann früh aufhören, sobald ein Durchlauf nichts tauscht. Selectionsort merkt sich nur, wo der kleinste Wert steht, und macht am Ende jedes Durchlaufs eine Vertauschung. Selectionsort macht weniger Vertauschungen; Bubblesort ist bei fast sortierten Listen schneller.

Ist Selectionsort stabil?

Nein. Eine Vertauschung kann einen Wert an einem gleichen Wert vorbeibewegen, sodass gleiche Werte ihre Reihenfolge ändern können. Durch Verschieben statt Tauschen lässt es sich stabil machen, was mehr Bewegungen kostet.

Was hat Heapsort mit Selectionsort zu tun?

Heapsort ist ein Selectionsort mit einer schnelleren Suche nach dem nächsten Wert: Es hält den unsortierten Teil in einem Heap, sodass jede Auswahl etwa log n Schritte statt einer vollen Suche braucht. Das senkt den Gesamtaufwand auf O(n log n).

Bereit, es auszuprobieren?

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

Selectionsort ausprobieren