|
Beschreibung
. Die Elemente werden der Reihe nach in eine bereits sortierte Folge eingetragen.
. Dazu wird in der bereits sortierten Folge die richtige Stelle zum Einfügen von rechts her gesucht und gleichzeitig die bereits eingetragenen Elemente um eins nach rechts verschoben.
. Das neue Element wird dann an der auf diese Weise freigewordenen Position eingefügt.
Programmcode
procedure InsertionSort ( var f : TArray; HighIndex : integer ) : string;
var i, j, v : integer;
begin
for i := 1 to HighIndex // äußere Schleife
do begin
v := f[i];
j := i;
while (j>0) and (f[j-1] > v) // innere Schleife (zum Einfügen)
do begin
f[j] := f[j-1];
dec (j)
end;
f[j] := v
end;
end; // InsertionSort
Aufwandsabschätzung
mittlerer-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird ½ * ½ (n-1) durchlaufen. (Im Mittel erwarten wir, daß das neue Element in die Mitte des soriterten Bereichs gehört.)
Daraus folgt der Aufwand .
worst-case-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird ½ (n-1) durchlaufen.
Daraus folgt der Aufwand .
best-case-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird 1 mal durchlaufen, da jedes neue Element schon am richtigen Platz steht, d.h. das Array war schon aufsteigend sortiert.
Daraus folgt der Aufwand .
Sortierdauer
|
