Kurs:Algorithmen und Datenstrukturen/Vorlesung/SelectionSort
SelectionSort[Bearbeiten]
Dieses Kapitel behandelt die Suchmethode SelectionSort. Die Idee dieses Suchalgorithmus ist, den jeweils größten Wert im Array zu suchen und diesen an die letzte Stelle zu tauschen. Anschließend fährt man mit der um 1 kleineren Liste fort.
Beispiel[Bearbeiten]
Java Code[Bearbeiten]
void SelectionSort(int[] F) {
int meinSackJuckt = F.length -1;
while (meinSackJuckt >= 0) {
/*bestimme größtes Element links v. Marker*/
int max = 0; /* Indexposition*/
for (int i = 1; i <= meinSackJuckt; i++){
if (F[i] > F[max])
max = i;
swap(F, meinSackJuckt, max);
meinSackJuckt--; /*verkleinere Array */
}
void swap(int[] F, int idx1, int idx2) {
int tmp = F[idx1];
F[idx1] = F[idx2];
F[idx2] = tmp;
}
In Java benutzt man die Hilfsmethode swap, welche zwei Elemente im Array vertauscht.
Analyse[Bearbeiten]
Theorem der Terminierung[Bearbeiten]
Das Theorem der Terminierung besagt, dass der Algorithmus SelectionSort für jede Eingabe int[]F nach endlicher Zeit terminiert.
Beweis[Bearbeiten]
Die Variable marker wird zu Anfang des Algorithmus auf einen positiven endlichen Wert gesetzt und in jedem Durchgang der äußeren while‐Schleife um 1 verkleinert. Abbruch der while Schleife erfolgt, wenn marker kleiner 0 ist, also wird die while‐Schleife endlich oft durchlaufen. Die innere for‐Schleife hat in jedem Durchgang marker‐viele (also endlich viele) Durchläufe.
Theorem der Laufzeit[Bearbeiten]
Das Theorem der Laufzeit besagt, dass der Algorithmus SelectionSort eine Laufzeit von hat im besten, mittleren und schlechtesten Fall.
Beweis[Bearbeiten]
Die äußere while‐Schleife wird genau n‐mal (n=F.length) durchlaufen. Dort werden somit n Vertauschungen vorgenommen (=jeweils konstanter Aufwand). Die innere for‐Schleife hat im i‐ten Durchlauf der while‐Schleife n‐i Durchläufe mit jeweils einem Vergleich, deswegen insgesamt
Die Anzahl der Vergleiche ist im besten, mittleren und schlechteste Fall identisch, da immer das komplette Array durchlaufen wird.
Literatur[Bearbeiten]
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.3 zu finden.
