Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/SelectionSort

SelectionSort

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

Java Code

void  SelectionSort(int[] F) {  
   int  marker = F.length -1;
   while (marker >= 0) {
     /*bestimme größtes Element links v. Marker*/
       int max = 0;  /* Indexposition*/
       for (int i = 1; i <= marker; i++){
           if (F[i] > F[max])
               max = i;
       swap(F, marker, max);
       marker--;   /*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

Theorem der Terminierung

Das Theorem der Terminierung besagt, dass der Algorithmus SelectionSort für jede Eingabe int[]F nach endlicher Zeit terminiert.

Beweis

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 of durchlaufen. Die innere for‐Schleife hat in jedem Durchgang marker‐viele (also endlich viele) Durchläufe.

Theorem der Korrektheit

Das Theorem der Korrektheit besagt, dass der Algorithmus SelectionSort das Problem des vergleichsbasierten Sortierens löst.

Beweis

Es gilt zunächst, dass die innere for‐Schleife stets den Index des Maximums des Teilarrays F[0...marker] berechnet und in max speichert. Weiterhin gilt, dass die Methode swap(F, marker, max) die Werte F[marker] und F[max] vertauscht.

Wir zeigen nun, dass die folgenden Aussagen Invariante der äußeren while-Schleife ist (d.h. sie sind am Ende eines jeden Schleifendurchgangs gültig):

) Das Teilarray F[marker+1...n] ist sortiert
) Alle Zahlen in F[0...marker] sind nicht größer als jede Zahl in F[marker+1...n]

Damit gilt (nach 1.) auch, dass nach Abbruch der while‐Schleife das Array F[0..n]=F (mit n=F.length‐1) sortiert ist.

Zeige dies durch Induktion nach i=n‐marker:

i=1: Im ersten Durchgang wird das Maximum as F[0..n] bestimmt und an die letzte Stelle F[n] vertauscht. Damit gilt sowohl 1.) als auch 2.)
i→i+1: Nehme an, dass nach dem i‐ten Durchgang der while‐Schleife gilt

) Das Teilarray F[(i‐n+1)...n] ist sortiert
) Alle Zahlen in F[0...(i‐n)] sind nicht größer als jede Zahl in F[(i‐n+1)...n]

Im (i+1) Durchgang wird zunächst das Maximum aus F[0...(i‐n)] bestimmt und anschließend mit dem Element an Position F[i‐n] getauscht. Da nach 2.) dieses Element nicht größer war als jede Zahl in F[(i‐n+1)...n], ist nun F[(i‐n)...n] sortiert (Invariante 1.). Da wir aus F[0...(i‐n)] ein Maximum genommen haben, kann nun auch kein Element in F[0...(i‐n‐1)] größer sein, als jede Zahl in F[(i‐n)...n] (Invariante 2.)

Theorem der Laufzeit

Das Theorem der Laufzeit besagt, dass der Algorithmus SelectionSort eine Laufzeit von $\Theta (n^{2})$ hat im besten, mittleren und schlechtesten Fall.

Beweis

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

$(n-1)+(n-2)+(n-3)+...+1$ $={\frac {n\cdot (n-1)}{2}}\approx {\frac {n^{2}}{2}}$

Die Anzahl der Vergleiche ist im besten, mittleren und schlechteste Fall identisch, da immer das komplette Array durchlaufen wird.

Literatur

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.