|
|
 |  | InsertionSort | | Ein recht ineffizienter Sortieralgorithmus ist der InsertionSort! |
|  |
|
 | | |
|
| |
| | |
| EinführungDefinition 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] |
 | |
| | |
| ImplementierungImplementierung mit SML | | | | |
| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | | (* 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 | | | | |
| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | | 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 | | | | |
| 1
2
3
4
5
6
7 | | % ?-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]). | |
| | | | |
 | |
| | |
| | |
| AllgemeinDiese Seite ist Bestandteil der Domäne www.stefan−baur.de und heißt InsertionSort. Die letzte Änderung erfuhr diese Seite am Sonntag, den 15. März 2009 von Stefan K. Baur. Zuletzt wurde sie von Ihnen am Mittwoch, den 8. September 2010 um 3:44 Uhr im Internet besucht. Sie gelangen zur vorliegenden Seite, wenn Sie ausgehend von der Startseite über dem Hauptmenü wie folgt navigieren: Die vorliegende Seite verfügt über folgenden Menüunterpunkt: | ShellSort
Ein verbesserter InsertionSort, aber immer noch recht ineffizient, ist der ShellSort! |
Wenn Sie die vorliegende Seite ausdrucken möchten, nutzen Sie dazu die Printversion. | |
| Literaturangaben[FUNPROG] Prof. Dr. Peter Pepper (TU Berlin): Funktionale Programmierung, Springer−Verlag, 1999, ISBN 3−540−64541−1. In OPAL, ML, HASKELL und GOFER mit 34 Abbildungen [INFO2002] Heinz−Peter Gumm, Manfred Sommer: Einführung in die Informatik, Oldenbourg Verlag, 5. Auflage, 2002, ISBN 3−486−25635−1.
Weitere Literatur, die zur Erstellung vorliegender Homepage beigetragen hat, finden Sie unter  Literaturverzeichnis. | |
| AutorenWerden Sie Autor vorliegender Homepage, informieren Sie sich unter Autoren. | |
| | |
| Look & FeelDas aktuelle Design trägt den Namen „Design 2007”.
Falls Ihnen jedoch das aktuelle Design nicht zusagen sollte, so stehen Ihnen noch andere, alternative Designs zur Verfügung: | |
| CopyrightVorliegender Webauftritt wurde in mühevoller Kleinarbeit von  Stefan K. Baur entwickelt.
Copyright (c) 2004-2010 Stefan K. Baur | |
| | |
|
