Selectionsort
Sucht den kleinsten übrigen Wert und tauscht ihn an den nächsten Platz. Es tauscht sehr selten, vergleicht aber immer gleich oft.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- nein
- ja
Bester Fall: wie die Zeit mit der Listengröße n wächst, wenn die Eingabe für diesen Algorithmus am einfachsten ist.
Durchschnitt: das übliche Wachstum der Zeit mit n. Bei n² dauern doppelt so viele Werte etwa viermal so lang. n log n wächst viel langsamer.
Schlechtester Fall: das Wachstum bei der schwierigsten Eingabe. Wichtig, wenn das Tempo nie einbrechen darf.
Speicher: wie viel Zusatzspeicher neben der Liste nötig ist. 1 heißt ein paar Variablen, n heißt eine Kopie der Liste.
Stabil: Zwei gleiche Werte behalten ihre ursprüngliche Reihenfolge. Wichtig, wenn man Datensätze nach einem Feld sortiert.
Ohne Zusatzspeicher: sortiert direkt in der Liste, ohne zweite Liste.
- wird verglichen
- wird verschoben
- bisher kleinster Wert
- am endgültigen Platz
Probieren Sie es aus: Wählen Sie eine umgekehrte Liste. Die Zahl der Vergleiche ist genau dieselbe wie bei jeder anderen Liste.
So funktioniert es
Im unsortierten Teil wird der kleinste Wert gesucht. Er wird mit dem ersten unsortierten Wert getauscht, so steht ein Wert mehr an seinem endgültigen Platz. Dabei wird immer jeder übrige Wert geprüft, auch bei einer schon sortierten Liste.
Wann es sich eignet
Nützlich, wenn das Verschieben von Daten teuer ist, das Lesen aber billig. Denn es tauscht höchstens einmal pro Platz. In den meisten anderen Fällen ist Insertionsort die bessere einfache Wahl.