Home » Tipps & Tricks » Algorithmen » Sortieren » InsertionSort

InsertionSort

Insertionsort ist ein einfacher Sortieralgorithmus. Der Algorithmus benutzt dabei eine ähnliche Strategie, wie ein menschlicher Kartenspieler, der seine Karten sortiert.

procedure InsertionSort(var A: array of Integer);
var
  i: Integer;
  j: Integer;
  tmp: Integer;
begin
  for i:= 1 to high(A) do
  begin
    j:= i;
    tmp := A[i];
    while (j > 0) and (A[j-1] > tmp) do
    begin
      // Verschieben:
      A[j]:= A[j-1];
      Dec(j);
    end;
    A[j]:= tmp;
  end;
end;

Dieser Tipp demonstriert den InsertionSort-Algorithmus anhand der Sortierung eines Integer-Arrays. Es ist selbstverständlich ohne Weiteres möglich, die Routine soweit anzupassen, dass Arrays beliebigen Typs sortiert werden.

InsertionSort ist im Allgemeinen ein eher einfaches und langsames Verfahren, allerdings hat es den großen Vorteil, dass es bei „fast sortierten“ Listen sehr schnell ist. Weitere Informationen finden sich z.B. in der Wikipedia.