 |
|
|
|
 InsertionSort |
|
|
|
Einführung
Implementierung
Highlight
|
|
| Ein recht ineffizienter Sortieralgorithmus ist der InsertionSort! |
|
|
|
|
| Einführung |
|
Definition
Der InsertionSort ist das duale Gegenstück zum  SelectionSort.
Es wird zwar auch in ein Element und den Rest zerlegt, aber jetzt wird die ganze Arbeit nicht in die Zerlegung, sondern in die Komposition gesteckt. Man nimmt das erste Element der Liste weg, sortiert rekursiv die Restliste und fügt dann das erste Element an der passenden Stelle ein.  [FUNPROG]
|
|
Komplexität
Der Aufwand ist hier quadratisch, weil das Einsortieren im Schnitt die halbe Liste abarbeiten muss, bis die richtige Stelle gefunden ist. [FUNPROG]
|
|
Beispiel: Sortieren von Spielkarten
Der Spieler nimmt eine Karte nach der anderen auf und sortiert sie in die bereits aufgenommenen Karten ein. Dieser Algorithmus wird InsertionSort genannt. [INFO2002]
|
|
Konkretes Zahlenbeispiel
Dabei sei nun [8,2,5,3,9,1,6,7,4] die zu sortierende Liste: [8,2,5,3,9,1,6,7,4][] [2,5,3,9,1,6,7,4][8] [5,3,9,1,6,7,4][2,8] [3,9,1,6,7,4][2,5,8] [9,1,6,7,4][2,3,5,8] [1,6,7,4][2,3,5,8,9] [6,7,4][1,2,3,5,8,9] [7,4][1,2,3,5,6,8,9] [4][1,2,3,5,6,7,8,9] [][1,2,3,4,5,6,7,8,9]
|
|
|
| Implementierung |
| Implementierung mit SML |
|
|
|
|
(* insertionsort: klar!
insert: Hilfsfunktion *)
fun insertionsort nil = nil
| insertionsort (e::el) =
let
fun insert a nil = [a]
| insert a (x::xl) =
if (a <= x)
then a :: (x :: xl)
else x :: (insert a xl)
in
insert e (insertionsort el)
end;
(* Anwendungsbeispiel *)
val output1 = insertionsort [3, 6, 2, 9, 1, 8, 7, 4, 5];
val output2 = insertionsort [7, 7, 7, 2, 7, 2, 2, 2];
val output3 = insertionsort [~3, 3, ~2, 2];
(* Ausgabe:
val output1 = [1,2,3,4,5,6,7,8,9] : int list
val output2 = [2,2,2,2,7,7,7,7] : int list
val output3 = [~3,~2,2,3] : int list *)
|
|
|
|
|
|
| Implementierung mit Delphi |
|
|
|
|
unit UInsertionsort;
interface
procedure InsertionSort(var A: array of Integer);
implementation
procedure InsertionSort(var A: array of Integer);
var
I, J: Integer;
Elem: Integer;
begin
for I := Low(A) + 1 to High(A) do
if (A[I] < A[I - 1]) then
begin
Elem := A[I];
J := I;
while ((J > Low(A)) and (A[J - 1] > Elem)) do
begin
A[J] := A[J - 1];
Dec(J);
end;
A[J] := Elem;
end;
end;
end.
|
|
|
|
|
|
| Implementierung mit Prolog |
|
|
|
|
% ?-insertionsort([8, 2, 5, 3, 9, 1, 6, 7, 4], SL).
insertionsort([], []).
insertionsort([X|L], SL) :- insertionsort(L, ZSL), insert_(X, ZSL, SL).
insert_(X, [Y|SL1], [Y|SL2]) :- X > Y, !, insert_(X, SL1, SL2).
insert_(X, SL, [X|SL]).
|
|
|
|
|
|
|
|
| Highlight |
|
Sie setzen matt!
Haben Sie beim Schach schon einmal mit dem  Stickmatt
…
|
| Weiß setzt matt in 1 |
|
|
| konstruiert |
|
… punkten können?
|
Mehr ...
|
|
|
|
|
|
|
Informatik 
Schach 
Privates 
Inhalt 
Startseite
[FUNPROG]
Literaturverzeichnis