ShellSort Problem - Array mit 2 Elementen

[TUX_der_Pinguin]

Ich habe aus dem Delphi Buch (Delphi 5 - Grundlagen und Profiwissen, Amazon) die Sortierung Shell-Sort gefunden und die bereits für mehre Projekte verwendet.

Jedoch bin ich jetzt auf ein Problem gestoßen, alle Arrays die sortiert werden fangen bei 0 an, soweit scheint es mit der
Sortierung zu klappen, jedoch habe ich einen Fall das ein Array nur 2 Elemente enthält und jetzt stellt sich raus
das das Array nicht sortiert wird.

Original Quellcode aus dem Buch:

Delphi-Quellcode:

procedure sort_shell(var a: array of Word);
var bis,i,j,k : LongInt;
  h           : Word;
begin
  bis := High(a);
  k   := bis shr 1; //div 2
  while k > 0 do begin
    for i := 0 to bis - k do begin
      j := i;
      while (j >= 0) And (a[j] > a[j + k]) do begin
        h        := a[j]; 
        a[j]     := a[j + k];
        a[j + k] := h;
        if j > k then Dec(j,k) else j := 0;
      end
    end;
    k := k shr 1; //div 2
  end

end;

Mein Array:

Zitat:

Files[0].SortStr := '20090422';
Files[1].SortStr := '20090423';

So meine Implementierung sieht wie folgt aus...

Delphi-Quellcode:

  //Dateien sortieren
  countTo := High(Files);
  k       := countTo div 2;

  while (k > 0) do begin
    for i := 0 To countTo - k do begin
      j := i;

      while (j >= 0) and (Files[j].SortStr <= Files[j+k].SortStr) do begin
        //Elemente austauschen
        exchg      := Files[j];
        Files[j]   := Files[j+k];
        Files[j+k] := exchg;
        if j > k then Dec(j,k) else j := 0;

      end;{while}

    end;{for}
    k := k div 2;
  end;{while}

Das Ergebnis ist das nichts sortiert wird, da bei "k := countTo div 2" k = 0 rauskommt wird die folgende while schleife nicht durchlaufen.

Ich habe mich damit beholfen das bei der initialisierung abgefangen wird ob das Array nur 2 Elemente groß ist oder nicht.

Delphi-Quellcode:

  if Length(Files) = 2 then
    k := 1
  else
    k := countTo div 2;

Dann wird das Array richtig sortiert:

Zitat:

Files[0].SortStr := '20090423';
Files[1].SortStr := '20090422';

Jetzt meine Frage ist das jetzt soweit alles korrekt, ich bin mir nicht sicher ob jetzt alles korrekt sortiert wird oder vielleicht
der letzte Eintrag "vergessen" wird zu sortieren, erste Tests bestätigen dies zwar nicht. Jedoch bin ich etwas verwirrt wieso
Shell-Sort ein Problem hat mit einem "zu kleinen" Array. Haben die Autoren im Buch etwas vergessen oder wo liegt das Problem.

[gammatester]

Scheint mir zumindest ein Bug im Originalquellcode zu sein. Der wird provoziert durch die neumodische Art, arrays meist bei Index 0 anfangen zu lassen. Das erste k soll wohl gleich der halben Anzahl der Elemente sein, also etwa k := (High(Files) - Low(Files) + 1) div 2; Nebenbei: die durch

Delphi-Quellcode:

k := (High(Files) - Low(Files) + 1) div 2;
...
k := k div 2;

erzeugte Schrittweitenfolge ist suboptimal.

Gammatester

[TUX_der_Pinguin]

Zitat von gammatester:

Scheint mir zumindest ein Bug im Originalquellcode zu sein. Der wird provoziert durch die neumodische Art, arrays meist bei Index 0 anfangen zu lassen. Das erste k soll wohl gleich der halben Anzahl der Elemente sein, also etwa k := (High(Files) - Low(Files) + 1) div 2; Nebenbei: die durch

Delphi-Quellcode:

k := (High(Files) - Low(Files) + 1) div 2;
...
k := k div 2;

erzeugte Schrittweitenfolge ist suboptimal.

Gammatester

Naja nur die halbe Anzahl also "Length(Files) div 2" bringt nichts, den dann tritt ein Fehler auf und das Programm bricht ab,
soweit ist die Routine schon korrekt das sie mit "High(Files) div 2" arbeitet. Vorraussetzung ist Index 0 im Array.

Und ob jetzt die Schrittweitenfolge suboptimal oder nicht ist, ist soweit ja Vernachlässigbar solange der Quellcode generell funktioniert.

[gammatester]

Zitat von TUX_der_Pinguin:

Naja nur die halbe Anzahl also "Length(Files) div 2" bringt nichts, den dann tritt ein Fehler auf und das Programm bricht ab, soweit ist die Routine schon korrekt das sie mit "High(Files) div 2" arbeitet. Vorraussetzung ist Index 0 im Array.

Das zeigt nur, daß noch Fehler im Code sind, hier einige Beobachtungen:

- Die Shell-Sort-For-Schleife muß mit jedem k funktionieren, was viele Implementation auch benutzen, die mit 'optimalem' Inkrementen arbeiten (ggf. wird sie halt gar nicht durchlaufen).

- Es wird auch dann getauscht, wenn die Werte gleich sind.

- if j > k then Dec(j,k) else j := 0; macht mich kribbelig. Was soll das? Wo kommt das her? Hier ist Potential für eine Endlosschleife, zB immer dann, wenn alle Arraywerte gleich sind. (Im 'Originalcode' kann das nicht passieren, weil da mit > gearbeitet wird).

Zitat von TUX_der_Pinguin:

Und ob jetzt die Schrittweitenfolge suboptimal oder nicht ist, ist soweit ja Vernachlässigbar solange der Quellcode generell funktioniert.

War ja auch nur unter 'nebenbei'.

Gammatester

[TUX_der_Pinguin]

Ups ich hatte eine Zeile im Original code noch vergessen, aber die ist identisch mit der aus meiner Implementierung.

if j > k then Dec(j,k) else j := 0;

[gammatester]

Zitat von TUX_der_Pinguin:

Ups ich hatte eine Zeile im Original code noch vergessen, aber die ist identisch mit der aus meiner Implementierung.

if j > k then Dec(j,k) else j := 0;

OK. Ist aber trotzdem unschön. Ein einfaches dec(j,k) reicht völlig aus, denn j<0 wird ja durch die While-Bedingung angefangen.

Gammatester

[TUX_der_Pinguin]

Okay das mag ja alles sein, nur ging es mir anfangs ja darum ob der Sortieralgorythmus nun funktioniert bzw. wie muß der
lauten damit Shell-Sort egal bei der Anzahl von Elementen funktioniert.

[gammatester]

Zitat von TUX_der_Pinguin:

Okay das mag ja alles sein, nur ging es mir anfangs ja darum ob der Sortieralgorythmus nun funktioniert bzw. wie muß der
lauten damit Shell-Sort egal bei der Anzahl von Elementen funktioniert.

Na ja: Auf jeden Fall das "<=" in "<" ändern, sonst gibt es unter bestimmten Umständen die Endlosschleife. Dann nimm meinen Vorschlag für den Startwert von k und verrate uns, welcher Fehler auftritt. (Wie schon gesagt, sollte das ganze für jede fallende Folge von k-Werten mit Endwert 1 funktionieren).

[TUX_der_Pinguin]

Ich habe jetzt 2 Versuche gestartet der erste schlägt mit einer Zugriffsverletztung fehl.

Delphi-Quellcode:

//Dateien sortieren 
  countTo := Length(Files);  //Änderung
  k       := countTo div 2; 

  while (k > 0) do begin 
    for i := 0 To countTo - k do begin 
      j := i; 

      while (j >= 0) and (Files[j].SortStr < Files[j+k].SortStr) do begin 
        //Elemente austauschen 
        exchg      := Files[j]; 
        Files[j]   := Files[j+k]; 
        Files[j+k] := exchg; 
        if j > k then Dec(j,k) else j := 0; 

      end;{while} 

    end;{for} 
    k := k div 2; 
  end;{while}

Die zweite Änderung bezieht sich auf deinen Vorschlag, dies scheint soweit zu klappen.

Delphi-Quellcode:

//Dateien sortieren 
  countTo := High(Files); 
  k       := Length(Files) div 2;  //Änderung, das gleiche wie High(Files) - Low(Files) + 1

  while (k > 0) do begin 
    for i := 0 To countTo - k do begin 
      j := i; 

      while (j >= 0) and (Files[j].SortStr < Files[j+k].SortStr) do begin 
        //Elemente austauschen 
        exchg      := Files[j]; 
        Files[j]   := Files[j+k]; 
        Files[j+k] := exchg; 
        if j > k then Dec(j,k) else j := 0; 

      end;{while} 

    end;{for} 
    k := k div 2; 
  end;{while}

[gammatester]

Der höchste Index, der vorkommt ist max(j+k) = max(i+k) = max(countTo-k+k) = countTo. Und das ist im ersten Fall = length(files) > high(files) und deshalb krachts.

Gammatester