Tutorial: Sortier-Algorithmen I+II

[Alexander Roth]

Zitat:

Zitat von Daniel

Delphi-Quellcode:

Procedure ShellSort;
var i, j, h, v : Integer;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > N);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To N Do
    Begin
      v:= Data[i];
      j:= i;

      While ((j > h) and (Data[j-h] > v)) Do
      Begin
        Data[j]:= Data[j-h];
        dec( j, h );
      End;
      Data[j]:= v;
    End;
  Until (h = 1);
End;

Unten das habe ich von Alexander Franz (http://www.alexander-franz.de):

Delphi-Quellcode:

function TMainFrm.shellSort(zahlen : IntArray): Int64;
var
  i, j, k, tmp: Integer;
  n : Int64;
const
  h : Array[0..15] of Integer = (1391376, 463792, 198768, 86961, 33936, 13776,
                                4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1);
begin
  for k:=0 to Length(h)-1 do
  begin
    for i:=h[k] to Length(zahlen) do
    begin
      j := i;
      tmp := zahlen[j];
      while ((j>h[k]) AND (tmp<zahlen[j-h[k]])) do
      begin
        zahlen[j] := zahlen[j-h[k]];
        Dec(j, h[k]);
        Inc(n);
      end;
      zahlen[j] := tmp;
    end;
  end;
  Result := n;
end;

Ich kopiere nur äußerst ungern einen Code und will ihn gern immer selbst verstehen:
Also Shellsort habe ich von der Logik her kapiert:
1. halbe Arraylänge auseinander Einträge vergleich und wenn nötig vertauschen
2. viertel Arraylänge auseinander Einträge vergleich und wenn nötig vertauschen
3.....
...

Also die 2 äußeren Schleifen sind mir klar. Aber was die innere da soll? Das ist doch einfach nur eine Bedingung, wenn die eine größer ist als die andere dann vertausche, ansonsten mache nix.
Und die Bedingung j>h[k]ist auch irgendwie komisch, man hat doch in der for schleife davor genau das festgelegt, dass diese Bedingung immer erfüllt ist.
Und es kann ja nix bingen Dec(j, h[k]); für den nächsten Durchlauf zu beschreiben, denn j wird ja wieder i zugewiesen. Es kann also nur für die innerste Schleife relevant sein. Doch was macht die da. Die macht doch die Bedingung (j>h[k]) lediglich unerfüllt. Damit läuft die innerste Schleife immer nur genau 1 mal durch. Damit kann man es auch in einer if Bedingung schreiben.

Wisst ihr eine Erklärung?

[Lee500]

Hiho,

Ich hab mich ma an den ShellSort algorythmus gewagt. Er sortiert jetzt wunderbar, bis auf den letzten Datensatz.

Delphi-Quellcode:

Procedure TForm1.ShellSort();
var i, j, h : Integer;
v: Trun;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > Length(Runs)-1);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To Length(Runs)-1 Do
    Begin
      v:= Runs[i-1];
      j:= i;

      While ((j > h) and (Runs[j-h-1].sumtime > v.sumtime)) Do
      Begin
        Runs[j-1]:= Runs[j-h-1];
        dec(j,h);
      End;
      Runs[j-1]:=v;
    End;
  Until (h = 1);
End;

TRun ist ein eigenes record mit ein paar variablen, wie z.B. das benutzte sumtime. Ich will also die array-Datensätze des arrays Runs nach sumtime sortieren. Er sortiert wie gesagt alles, nur den letzten Datensatz nicht. Es wäre wirklich toll wenn ihr meinen Denkfehler finden würdet.

Gruß Lee500

[Larsi]

Mach ein neues Thema auf. Hier darfst du nur Fragen und Anregungen und Kritik über Daniels Tut loswerden.

[Lee500]

Das ist doch eine Frage zum Tut. Im Tut steht ja der ShellSort-Algorytmus, der den letzten Datensatz nicht berücksichtigt. So gesehen ist es eine Frage zum Tut.

[marabu]

Hallo,

@Lee500: Du musst fremden Code immer an deine Bedürfnisse anpassen. Daniel verwendet ein Array Data[1..N], für dein Array hingegen gilt Low(Runs) = 0.

@Larsi: Was du da machst ist falsch. Wenn dir etwas auffällt, was nicht in Ordnung ist, dann benachrichtige einen Mod.

Freundliche Grüße

[Lee500]

Hi,

@marabu ich habe ja bereits überall Length(Runs)-1 und das ganze so angepasst wie im Post von Daniel mit der TListBox. Von daher müsste es so funktionieren. Wenn ich das nicht berücksichtigt hätte, wäre im übrigen der erste Datensatz der, der nicht mitsortiert würde.

Hab das Problem jetzt behoben:

Delphi-Quellcode:

Procedure TForm1.ShellSort();
var i, j, h : Integer;
v: Trun;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > Length(Runs));

  Repeat
    h:= (h div 3);
    For i:= (h+1) To Length(Runs) Do
    Begin
      v:= Runs[i-1];
      j:= i;

      While ((j > h) and (Runs[j-h-1].sumtime > v.sumtime)) Do
      Begin
        Runs[j-1]:= Runs[j-h-1];
        dec(j,h);
      End;
      Runs[j-1]:=v;
    End;
  Until (h = 1);
End;

So funktioniert es wunderbar.

Gruß Lee500

[zeustates]

hallo ich habe mich mal an den Mergesort gewagt.
nur leider tut er nicht. Eig sollte er nur bekomm ich in zeile 25 immer ein "sigsegev" bei einem begin. Ich werde nicht schlau daraus.

hier ist mal mein code als anhang

[Delphi-Laie]

Zitat:

Zitat von zeustates (Beitrag 1318429)

hallo ich habe mich mal an den Mergesort gewagt.
nur leider tut er nicht. Eig sollte er nur bekomm ich in zeile 25 immer ein "sigsegev" bei einem begin. Ich werde nicht schlau daraus.

hier ist mal mein code als anhang

Sigsev? Das kenne ich von Lazarus(-Compilaten). Benutzt Du Lazarus?

Mergesort benutze ich in rekursiver und "halb-rekursiver" Form in meinem Sortierkino, es läuft auch mit Lazarus-Compilaten.