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.
