shellsort

Shellsort

Funktionsweise
Der Sortieralgorithmus Shellsort (benannt nach D.L. Shell - 1959) basiert auf dem bereits besprochenen Insertionsort. Shellsort kümmert sich jedoch nicht von vornherein um alle Elemente des Feldes sondern setzt ein Raster an, so dass zunächst (z.B.) nur jedes 5. Element einbezogen wird. So werden die Elemente zahl[0,5,10,15,20] mittels Insertionsort vorsortiert. Danach rückt das Raster um eine Position nach rechts (zahl[1,6,11,16,21]), Insertionsort erledigt aufs Neue seine Arbeit, dann wieder eine Position nach rechts usw. Nach 5 derartigen Sortierzyklen ist das gesamte Feld grob vorsortiert.
Nun wird der Rasterabstand (z.B.) auf 3 reduziert (zahl[0,3,6,9,12,15,18,21,24]), wodurch sich die Vorsortierung weiter verfeinert. Nach 3 derartigen Zyklen liegt schon ein recht gut sortiertes Feld vor.
Da jetzt aber immer noch einige Elemente an der falschen Position stehen, muss das Raster auf jeden Fall im allerletzten Durchlauf den Wert 1 erhalten.
Die Rasterabstände können als Integer-Konstanten in einem Array bereitgestellt oder aber auch (in Abhängigkeit von der Feldgröße) dynamisch generiert werden. Nur eine geschickte Festlegung der Rasterabstände garantiert letztendlich auch eine hohe Sortiergeschwindigkeit.

I =

J =

Stoppuhr:

Vergleiche =

Vertauschungen =

Raster:

[5,3,1] [4,2,1] [5,1] [4,1] [3,1]


procedure shell(var zahl: feld);
const step: array[0..2] of byte = (5,3,1);
var i,j,k,pos,help: byte;
begin
  for k:=0 to 2 do
  begin
    for pos:=0 to step[k] do
    begin
      for i:=1 to ((size-pos) div step[k]) do
      begin
        if zahl[i*step[k]+pos]<zahl[(i-1)*step[k]+pos] then
        begin
          j:=i*step[k]+pos;
          help:=zahl[j];
          while (zahl[j-step[k]]>help) and (j>pos) do
          begin
            zahl[j]:=zahl[j-step[k]];
            j:=j-step[k];
          end;
          zahl[j]:=help;
        end;
      end;
    end;
  end;
end;

procedure TForm1.btnSortClick(Sender: TObject);
begin
  shell(zahl);
  printList(zahl);
end;