Selectionsort
Der Selectionsort Algorithmus ist ein Sortieralgorithmus, bei dem das kleinste Element in der Liste gefunden und am Anfang des unsortierten Listenbereichs platziert wird. Dieser Vorgang wiederholt sich, bis die gesamte Liste sortiert ist.
Beispiel
Für die Zeichenkette "ZEBRASSINDGELB" sieht das dann folgendermaßen aus:
Selectionsort "wählt" also aus den noch nicht betrachteten Elementen das kleinste aus und ordnet dieses an der korrekten Position ein - auf diese Weise ergibt sich die korrekte Sortierung
(A1)
- Wieviele Vergleiche und wie viele Vertauschungen finden in etwa statt, bis das Array mit Selectionsort sortiert ist?
- Gibt es eine „Invariante“, also eine Eigenschaft des Arrays, welche sich beispielsweise nach einer Vertauschungsoperation nicht mehr verändert?
(A2)
- Implementiere im Bluej-Projekt https://codeberg.org/qg-info-unterricht/algs4-sort-bluej Selectionsort.
- Erzeuge mit Hilfe der
draw-Methode eine Veranschaulichung des Sortiervorgangs wie im Bild oben.