Kurs:Algorithmen und Datenstrukturen/Kapitel 2/SelectionSort

Selection Sort

Herleitung

Wir haben bei BubbleSort beobachtet, dass der Algorithmus in jedem Durchlauf das größte Element ans Ende der Liste schiebt. Anstatt es direkt dorthin zu kopieren, wurde das Element um eine Stelle nach der anderen geschoben.

Bei Selection Sort vermeidet man diese Ineffizienz. Es wird dort zwischen 2 Bereichen unterschieden: dem sortierten und dem unsortierten. Man geht bei der Sortierung folgendermaßen vor.

Am Anfang gibt es nur den unsortierten Bereich. Man sucht aus der gegebenen Liste das kleinste Element heraus und fügt es am Anfang der Liste ein. Dieses Element bildet den sortierten Bereich. Im nächsten Durchgang sucht man wieder im unsortierten Bereich nach dem kleinsten Element und fügt es am Ende des sortierten Bereiches an. Nicht vergessen, dass erste Element war das kleinste aus dem gesamten unsortierten Bereich und somit ist das zweit kleinste größer bzw. gleich dem ersten Element aus dem sortierten Bereich.

Man geht pro Durchgang nun folgendermaßen vor:

kleinstes Element aus dem unsortierten Bereich heraussuchen
das Element dann an das Ende des sortierten Bereiches stellen

Am Ende liegt dann wieder eine sortierte Liste vor.

Implementierung in ObjectPascal

Nachfolgend wird Selection Sort in Object Pascal implementiert. Hier wird als Liste ein Array genommen.

 1. PROCEDURE SelectSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
 2.     VAR
 3.         i, j, min, temp : INTEGER;
 4.     BEGIN

            (* Arraylänge überprüfen *)
 5.         IF n > LEN(a) THEN
 6.             Out.String("Fehler: n ist größer als die Arraylaenge!"); Out.Ln;
 7.             RETURN;
 8.         END;

            (* Für jede Position... *)
 9.         FOR i := 0 TO n-2 DO

                (* Suche das Minimum *)
10.             min := i;
11.             FOR j := i+1 TO n-1 DO
12.                 IF a[j] < a[min] THEN min := j END
13.             END;

                (* Vertausche falls nötig *)
14.             IF min # i THEN
15.                 temp := a[i]; a[i] := a[min]; a[min] := temp;
16.             END

17.         END
18.     END SelectSort;

Anmerkung: Die Schleife über i (Zeilen 9 bis 17) durchläuft die Reihe nach alle Stellen des Arrays bis auf die letzte (TO n-2). Es wird angenommen, dass das kleinste Element ab der iten Stelle schon das Element an der Stelle i ist (Zeile 10). Danach werden alle Elemente ab dem iten mit dem vermeintlichen kleinsten Element verglichen (Schleife Zeilen 11 bis 13). Wir ein kleineres Element gefunden, so wird min neu gesetzt (Zeile 12). Ist das kleinste Element nun nicht mehr das an der iten Stelle, so wird es mit diesen Vertauscht (Zeile 15).

Für ein Array der Länge 6 sieht der Vorgang in Bildern wie folgt aus:

Der Name dieses Algorithmus (Selection Sort) kommt daher, dass wir iterativ das kleinste Element selektieren und an die richtige Stelle vertauschen. Der Algorithmus ist auch bekannt unter den Namen MinSort (oder auch MaxSort, je nach Richtung des Sortierens) oder auch einfach SelectSort.

Für detailliertere Informationen: Selection Sort bei Wikipedia

Average-Case Analyse

Beim ersten Durchgang werden $n-1$ Vergleiche durchgeführt und, falls das Minimum nicht schon an erster Stelle steht, eine Vertauschung. Im nächsten Durchgang sind es dann nur noch $n-2$ Vergleiche und, falls das Minimum nicht schon an zweiter Stelle steht, eine Vertauschung.

Allgemein kann man sagen, dass im $k$ -ten Durchgang $n-k$ Vergleiche und eine Vertauschung mit der Wahrscheinlichkeit ${\frac {n-k}{n-k+1}}$ (nämlich der Wahrscheinlichkeit, dass das Minimum der Elemente $a_{k}\dots a_{n}$ schon an der Stelle $a_{k}$ steht) vorgenommen werden.

Für die Anzahl Vergleiche ergibt sich somit im schlimmsten und im besten Fall:

\sum _{k=1}^{n-1}(n-k)\quad =\quad {\frac {n(n-1)}{2}}\quad \in \quad {\mathcal {O}}(n^{2})

Die Summe geht nur bis $n-1$ da, wie bei BubbleSort, das letzte Element nur an der richtigen Stelle stehen kann und somit schon sortiert ist.

Die Anzahl Vertauschungen pro Durchgang ist im schlimmsten Fall $1$ und im Durchschnitt ${\frac {n-k}{n-k+1}}$ . Bei $n-1$ Durchgängen ergibt dies

\sum _{k=1}^{n-1}{\frac {n-k}{n-k+1}}\quad \in \quad {\mathcal {O}}(n)

Um eine genauere Abschätzung für große Werte n zu erhalten, vereinfachen wir den obigen Ausdruck zu:

$\sum _{k=1}^{n-1}{\frac {n-k}{n-k+1}}$	$\quad =\quad$	$(n-1)-\sum _{k=1}^{n-1}{\frac {1}{n-k+1}}$
	$\quad =\quad$	$(n-1)-\sum _{j=n}^{2}{\frac {1}{j}}$
	$\quad =\quad$	$(n-1)-\left(\sum _{j=1}^{n}{\frac {1}{j}}-1\right)$
	$\quad =\quad$	$n-\sum _{j=1}^{n}{\frac {1}{j}}$
	$\quad \approx \quad$	$\quad n-\ln(n)\quad$ ,

wobei die letzte Approximation für große $n$ gilt.

Bemerkung: Da $ln(10^{8})=18$ ist, kann diese Verbesserung entfallen.

Obwohl die Anzahl der Vergleiche konstant hoch ist, ist die Anzahl von Vertauschungen sehr gering, womit sich dieses Verfahren immer dann für das Sortieren einer großen Anzahl von Elementen eignet, wenn die Vertauschung um ein Vielfaches teurer ist als der Vergleich.