Selection Sort
Einführung
Ein simpler Sortieralgorithmus ist der Selection Sort. Dieser Algorithmus sucht sich als erstes das kleinste Element in der Liste, merkt es sich und tauscht es gegen das Element am Anfang aus, sodass sich dann das kleinste Element ganz am Anfang befindet. Als Nächstes wird das zweitkleinste Element in der Liste gesucht und wird gegen das an zweiter Stelle platzierte Element der Liste ausgetauscht usw. Auf diese Weise haben immer die Elemente auf der linken Seite der aktuellen Position einen festen Platz und werden nicht mehr geändert.
Beispiel
Es soll eine Liste mit dem Inhalt [4|3|1|5|2] sortiert werden.
Im ersten Durchlauf wird die komplette Liste durchlaufen, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert der Stelle des kleinsten Wertes (hier Wert 1 im Index 2) getauscht.
Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun im Index 1. Im Index 0 befindet sich bereits das kleinste Element, daher ist eine Suche an der ersten Stelle nicht mehr erforderlich. Der Rest der Liste wird durchlaufen. Das kleinste Element befindet sich hier zufällig am Ende der Liste. Es wird die 2 als kleinstes Element ausgewählt und die Werte werden mit der neuen Startposition getauscht.
Die Suche wiederholt sich nach dieser Logik bis alle Elemente sortiert wurden. Der Suchbereich sinkt Schritt für Schritt. Folgende Animation visualisiert den Algorithmus.
http://de.wikipedia.org/wiki/Selection_Sort
Pseudo Code
Der Algorithmus sieht im Pseudocode so aus:
prozedur SelectionSort( A : Liste sortierbarer Elemente )
hoechsterIndex = Elementanzahl( A ) - 1
einfuegeIndex = 0
wiederhole
minPosition = einfuegeIndex
für jeden idx von (einfuegeIndex + 1) bis hoechsterIndex wiederhole
falls A[ idx ] < A[ minPosition ] dann
minPosition = idx
ende falls
ende für
vertausche A[ minPosition ] und A[ einfuegeIndex ]
einfuegeIndex = einfuegeIndex + 1
solange einfuegeIndex < hoechsterIndex
prozedur ende
Java Implementierung
public ArrayList<Mitarbeiter> sortierenNachNachnamen(){
ArrayList<Mitarbeiter> sortierteListe = mitarbeiterListe;
int stelle = 0;
while(stelle < sortierteListe.size()){
int kleinstesElement = stelle;
for(int index = stelle+1; index < sortierteListe.size(); index++){
if(sortierteListe.get(index).getNachname().compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0){
kleinstesElement = index;
}
}
Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
sortierteListe.set(kleinstesElement,sortierteListe.get(stelle)) ;
sortierteListe.set(stelle,puffer);
stelle++;
}
return sortierteListe;
}
Komplexität
Mit Hilfe der Laufzeitanalyse betrachten wir nun die Zeitkomplexität des Algorithmus SelectionSort.
Um eine Datenstruktur (z.B. eine Array) mit Einträgen mittels SelectionSort zu sortieren, muss n-1 mal das Minimum durch Vergleichen bestimmt werden. Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw. Mit der gaußschen Summenformel erhält man die Anzahl der notwendigen Vergleiche. SelectionSort liegt somit in der Komplexitätsklasse O(n^2).
.