Kurs:Algorithmen und Datenstrukturen (hsrw)/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  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.

Theorem der Terminierung

Bearbeiten

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

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

Bearbeiten

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

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):

  1. ) Das Teilarray F[marker+1...n] ist sortiert
  2. ) 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
  1. ) Das Teilarray F[(i‐n+1)...n] ist sortiert
  2. ) 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

Bearbeiten

Das Theorem der Laufzeit besagt, dass der Algorithmus SelectionSort eine Laufzeit von   hat im besten, mittleren und schlechtesten Fall.

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.