Startseite < Informatik < Algorithmen < Sortieren < BucketSort RadixSort / QuickSort MergeSort HeapSort / BubbleSort SelectionSort [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] InsertionSort < ShellSort > / SlowSort BogoSort > Komprimieren Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >
InsertionSort
Ein recht ineffizienter Sortieralgorithmus ist der InsertionSort!
Einführung Theorie: InsertionSort
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 des InsertionSort
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 SML ⇑
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 Delphi ⇑
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]).
⇑ Implementierung mit Prolog ⇑
Startseite   Sitemap   Downloads   Hilfe   Impressum   Pflichtenheft  
Quellenangabe
  • [FUNPROG] Funktionale Programmierung: Prof. Dr. Peter Pepper (TU Berlin), 1999 Springer-Verlag ISBN 3-540-64541-1 In OPAL, ML, HASKELL und GOFER mit 34 Abbildungen
  • [INFO2002] Einführung in die Informatik: Heinz-Peter Gumm, Manfred Sommer, 2002 Auflage5, Oldenbourg Verlag ISBN 3-486-25635-1
Startseite < Informatik < Algorithmen < Sortieren < BucketSort RadixSort / QuickSort MergeSort HeapSort / BubbleSort SelectionSort [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] InsertionSort < ShellSort > / SlowSort BogoSort > Komprimieren Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >