Bug beim Stringsortieren (Shell Sort)

[xZise]

Ich habe zwei Listen, die ich nach einer (Data : array of string) sortieren will.

Die Listen habe ich aus der Registry gelesen, und nicht alle Einträge werden verwendet.

Dazu habe ich mir dann ShellSort genommen, und das so umfunktioniert, dass es strings sortieren kann.

Soweit ist es auch gut, nur habe ich nach den 1. Eintrag (eine Zahl als erster Buchstabe), ein "leerer" Einträg, und danach erscheint der Rest (beginnend mit "A").

Nun wollte ich fragen wo der Bug liegt.

Es ist auf jedenfall kein "leerer Eintrag"

Sortieralgorithmus:

Delphi-Quellcode:

procedure TfrmRegistry.ShellSort;
var
  i, j, h, N : Integer;
  v : string;
begin
  N := Length(Data);
  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 (AnsiCompareText(Data[j-h], v) > 0) do begin
        Data[j] := Data[j-h];
        dec( j, h );
      end;
      Data[j] := v;
    end;
  until (h = 1);
end;

Die Funktion, welche das Programm mit Daten füttert:

Delphi-Quellcode:

function TfrmRegistry.Execute(path: string): Boolean;
var
  i, j, fails : Integer;
  keyList : TStringList;
begin
  with TRegistry.Create(KEY_READ) do
    try
      RootKey := HKEY_LOCAL_MACHINE;

      if KeyExists(path) then
        FKey := path
      else
        FKey := '';

      //HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\

      if KeyExists('SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\') then begin
        OpenKey('SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\', false);

        keyList := TStringList.Create;
        try
          GetKeyNames(keyList);

          CloseKey;

          bUse.Enabled := false;


          SetLength(keys, keyList.Count);
          SetLength(Data, keyList.Count);

          lbList.Items.BeginUpdate;
          lbList.Items.Clear;
          fails := 0;
          for i := 0 to keyList.Count - 1 do begin
            OpenKey('SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\' + keyList[i], false);
            if ValueExists('DisplayName') then begin
              Data[i - fails] := ReadString('DisplayName');
              keys[i - fails] := keyList[i];
            end else
              inc(fails);
            CloseKey;
          end;

          SetLength(Data, Length(Data) - fails);

          ShellSort;
          for i := 0 to High(Data) do begin
            lbList.Items.Add(Data[i]);
          end;

          lbList.Items.EndUpdate;

          SetLength(keys, lbList.Count);
        finally
          keyList.Free;
        end;

        Result := false;

        inherited ShowModal;

        Result := not aborted;
      end else begin
        MessageBox(Handle, PChar('Schlüssel existiert nicht!' + #13#10 + 'Dialog wird nicht geöffnet.'), PChar('Fehler'), MB_OK and MB_ICONWARNING);
        Result := false;
      end;
    finally
      Free;
    end;
end;

PS: Ich weiß ;) Die andere Liste sortiere noch nicht :D Aber das wird dann einfach ;)

[Reinhard Kern]

Zitat:

Zitat von xZise

Ich habe zwei Listen, die ich nach einer (Data : array of string) sortieren will.

Die Listen habe ich aus der Registry gelesen, und nicht alle Einträge werden verwendet.

Dazu habe ich mir dann ShellSort genommen, und das so umfunktioniert, dass es strings sortieren kann.

Soweit ist es auch gut, nur habe ich nach den 1. Eintrag (eine Zahl als erster Buchstabe), ein "leerer" Einträg, und danach erscheint der Rest (beginnend mit "A").

Nun wollte ich fragen wo der Bug liegt.

....
PS: Ich weiß ;) Die andere Liste sortiere noch nicht :D Aber das wird dann einfach ;)

Hallo,

Vermutung, ohne das alles durchzulesen: dein array geht von 0..n, Shellsort sortiert von 1..n.

Gruss Reinhard

[xZise]

Zitat:

Zitat von Reinhard Kern

Vermutung, ohne das alles durchzulesen: dein array geht von 0..n, Shellsort sortiert von 1..n.

Also das könnte es sein. Aber wie kann ich dann von "0" an sorieren lassen?
Müsste ich das ganze Array "eins höher" stufen?

[edit]Also ich sortiere jetzt so, dass "N := High(Data)" ist.
Und es funktioniert![/edit]

[Reinhard Kern]

Zitat:

Zitat von xZise

Zitat:

Zitat von Reinhard Kern

Vermutung, ohne das alles durchzulesen: dein array geht von 0..n, Shellsort sortiert von 1..n.

Also das könnte es sein. Aber wie kann ich dann von "0" an sorieren lassen?
Müsste ich das ganze Array "eins höher" stufen?

[edit]Also ich sortiere jetzt so, dass "N := High(Data)" ist.
Und es funktioniert![/edit]

Na prima, dann hast du zwar von 0 an sortiert, aber 1 zuweit.

Gruss Reinhard

[xZise]

Also ich habe einfach überprüft, wie viele Items vorher in dem Array waren, und wie viele nachher in der Liste ("lbList") waren. Wenn dann keine Doppelgänger/Leerzeilen drin sind, dann müsste er ja korrekt sortiert haben.