Selection sort (sortiern durch auswahl)

Beschreibung . Aus den vorhandenen Daten wird der kleinste Datensatz herausgesucht und mit dem ersten Datensatz vertauscht.
. Dieses Verfahren wird nun für die übriggebliebenen, noch unsortierten Daten ebenfalls angewandt.


Programmcode
procedure SelectionSort ( var f : TArray; HighIndex : integer ) : string;

var i, j, min : integer;
begin
for i := 0 to HighIndex-1 // äußere Schleife
do begin

min := i;
for j := i+1 to HighIndex do if f[j] < f[min] then min := j; // innere Schleife

Swap (f[i], f[min]);
end;

end; // SelectionSort


Aufwandsabschätzung
mittlerer-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird im Durchschnitt (n-1)/2 mal durchlaufen.

Daraus folgt der Aufwand .
worst-case-Aufwand:
Der maximale Aufwand beträgt ebenfalls O(n2).

Sortierverfahren mit quadratischen Aufwand sind schlecht und eignen sich nur für kleine Datenmengen. Ihre Rechtfertigung liegt einzig und allein in der einfachen Implementierung. Wie wir später sehen werden, gibt es wesentlich effizientere Sortierverfahren mit einem Aufwand von O(nln(n)). Sortierdauer