Home » Tipps & Tricks » Algorithmen » Sortieren » ShellSort

ShellSort

Untenstehende Prozedur sortiert ein Integer-Array mit dem ShellSort-Verfahren:

procedure ShellSort(var arr: array of Integer);
var
  gr,b,i,c: Integer;
  d: Integer;
begin
  if High(arr)=1 then
  begin
    if arr[0]  0 do
  begin
    for i := 0 to gr - b do
    begin
      c := i;
      while(c >= 0) and (arr[c] > arr[c + b]) do
      begin
        d := arr[c];
        arr[c] := arr[c + b];
        arr[c + b] := d;
        if c > b then
          dec(c, b)
        else
          c := 0;
      end;
    end;
    b := b shr 1;
  end
end;

Aufgerufen werden kann die Prozedur beispielsweise so:

procedure TForm1.Button1Click(Sender: TObject);
var
  a: array[0..100] of Integer;
  i: Integer;
begin
  for i := low(a) to high(a) do
    a[i] := Random(High(Integer));
  ShellSort(a);
end;

Dieser Tipp demonstriert den ShellSort-Algorithmus anhand eines Integer-Arrays. Es ist selbstverständlich ohne Weiteres möglich die Routine soweit anzupassen, dass auch Listen oder andere Array-Typen sortiert werden.

ShellSort ist ein vergleichsweise kompliziertes, aber auch recht schnelles Sortierverfahren, wobei allerdings kein optimales Laufzeitverhalten erreicht wird. Weitere Informationen zu diesem Verfahren finden sich etwa in der Wikipedia.