keinDummer
unic's_un_dd_nix_anders
Code:
[B]InsertionSort[/B]
Sortieren durch Einfugen.
Gegeben sei eine Folge a[1],...,a[N] von Schlüsselelementen.
Prinzip: Wir betrachten den i-ten Durchgang der Schleife i = 2,...,N. Dabei sei die
i − 1-elementige Teilfolge a[1],...,a[i − 1] bereits sortiert
Programm:
PROCEDURE InsertionSort (VAR a : ARRAY[0..N] OF KeyType) =
VAR j : CARDINAL;
v : KeyType;
BEGIN
a[0] := −∞; (* in Modula-3: a[0]:=FIRST(KeyType); *)
FOR i := 2 TO N DO
v := a[i];
j := i;
WHILE a[j-1]>v DO
a[j] := a[j-1];
DEC(j);
END;
a[j] := v;
END;
END InsertionSort;
Beachte: Um in der WHILE-Schleife eine zusatzliche Abfrage auf die linke Feldgrenze zu
vermeiden, wird ein sog. Sentinel-Element (=Warter; Anfangs- oder Endmarkierung)
a[0] := −∞ verwendet.
Bemerkung: Auf die Verwendung eines Sentinel-Elementes kann bei nicht-strikter
Auswertung (auch lazy evaluation) des Compilers verzichtet werden:
WHILE 1<j AND a[j-1]>v DO
Dabei wird zunachst nur der linke Teil 1<j der Abbruchbedingung ausgewertet.
Liefert die Auswertung den Wert FALSE, so wird die Schleife verlassen, ohne daß der
rechte Teilausdruck a[j-1]>v ausgewertet wird. (Sprechweise:
Der Operator „AND ist nicht-strikt“ bzw. „AND ist ein short-circuit operator“) Die Auswertung des rechten
Teilausdrucks erfolgt nur dann, wenn das linke Argument von AND zu TRUE ausgewertet
werden kann.
Bei strikterUbersetzung des Compilers kann die Abbruchbedingung der WHILE-Schleife
auch innerhalb einer LOOP-Anweisung formuliert werden:
LOOP
IF 1<j THEN
IF a[j-1]>v THEN
a[j] := a[j-1];
DEC(j);
ELSE EXIT; END;
ELSE EXIT; END;
END
Beispiel:
InsertionSort durchläuft die zu sortierende Folge von links nach rechts. Dabei ist die
Anfangsfolge des Feldes zwar in sich sortiert, die Elemente befinden sich jedoch noch
nicht notwendigerweise an ihrer endgultigen Position.
−∞ 3 [B]7[/B] 8 6 4 2
[B]*[/B]
−∞ 3 7 [B]8[/B] 6 4 2
[B]*[/B]
−∞ 3 7 ---> 8 ----> [B]6[/B] 4 2
<------- <----------------|
−∞ 3 6 ---> 7 -----> 8 ----> [B]4[/B] 2
<--------- <-------- <---------|
−∞ 3 -----> 4 -----> 6 -----> 7 -----> 8 ----->[B]2[/B]
<------- <------- <------- <------ <-----------|
−∞ 2 3 4 6 7 8
−∞
Sentinel-Element a[0] = −∞
Komplexitatsanalyse
Vergleiche: Das Einfügen des Elements a[i] in die bereits sortierte Anfangsfolge
a[1],...,a[i − 1] erfordert mindestens einen Vergleich, hochstens jedoch i Vergleiche.
Das folgende Programm führt eine in-situ-Permutation durch wiederholte verkettete
Ringtauschoperationen aus:
PROCEDURE InsituPermutation (VAR a : ARRAY[1..N] OF KeyType;
VAR p : ARRAY[1..N] OF CARDINAL) =
VAR t : KeyType;
j, k : CARDINAL;
BEGIN
FOR i := 1 TO N DO
IF p[i] <> i THEN
t := a[i];
k := i;
REPEAT
j := k; a[j] := a[p[j]];
k := p[j]; p[j] := j;
UNTIL k=i;
a[j] := t;
END;
END;
END InsituPermutation;
