Kurs:Algorithmen und Datenstrukturen/Vorlesung/SelectionSort

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

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

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

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.