Probleme bei der Implementierung von Radixsort

[Isildur]

Ich schreibe gerade für die Schule eine Implementation von Radixsort. Zwar habe ich eine fertige Implementation gefunden allerdings liegt diese vom Wissenstand weit über meiner oder der meines Kurses.

Daher habe ich versucht das Verfahren mit relativ einfachen Techniken wiederzugeben, da es hierbei eh um die Demonstration nicht um die Geschwindkeit in einem Anwendungsprogramm geht.

Der zugegeben etwas wirre Code sieht derzeit so aus

Delphi-Quellcode:

procedure TSortieren.RadixSort;
var sorttil, i, j, k, l: integer;
var temp : array[0..255] of array of string; //array für alle ansichars
var len : integer;
var pos1, pos2 : integer;
begin
//da sorttil := 4; nur nach den ersten 4 Zeichen sortieren
for sorttil := 4 downto 1 do begin
  //Partionierungsphase
  for i := 1 to Anzahl-1 do begin
    if length(Feld[i])>=sorttil then begin
      pos1 := ord(Feld[i,sorttil]);
      len := length(temp[pos1]);
      pos2 := len-1;
      if len=0 then pos2 := 0;
      setlength(temp[pos1],len+1);
      temp[pos1, pos2] := Feld[i];
    end;
  end;
  //Sammelphase
  l:=1;
  j:= 0;
  k:=0;
  while j <= length(temp)-1 do begin
    while k <= length(temp[j])-1 do begin
      Feld[l] := temp[j,k];
      k:=k+1;
      l:=l+1;
    end;
    j:=j+1;
  end;
end;

Anzahl ist ein vorgegebener Wert der Anzahl der Elemente im Array Feld beinhaltet(das ist etwas wirr, da die an dieser Stelle vorgegebene Implementation von Seitens meines Lehrers nicht ganz sauber ist(es gibt ein Element Feld[0] aber dies ist leer...), aber dies dürfte eigentlich keine Auswirkungen auf die grundsätzliche Ordnung haben).
Ich habe am Ende while-Schleifen verwendet weil aus mir völlig unbegreiflichen Gründen eine for-Schleife nach dem Muster for j := 0 to length(temp)-1 do nicht bei 0 sondern bei length(temp)-1 anfing zu zählen und dann runter zählte. So gehts jetzt, ich habe kA wieso.

Für eine kurze anschauliche Beschreibung des Verfahrens siehe hier.


Nun das Problem ist, dass die Werte nachher völlig ungeordnet sind genauso wie vorher und ich derzeit keine Idee habe woran das liegen könnte(vll übersehe ich auch einfach nur mal wieder ein Detail). Hat jmd. eine Idee? Für weitere Informationen einfach fragen.

ps:Sry wegen der etwas ungenauen Problembeschreibung.

[peschai]

Zitat:

es gibt ein Element Feld[0] aber dies ist leer...), aber dies dürfte eigentlich keine Auswirkungen auf die grundsätzliche Ordnung haben).

...Eventuell doch... was passiert wenn du die obere Schleife von "0..Anzahl-1" laufenlässt ?
Es kann ja vom Lehrer gewollt sein, daß auch ein LeerElement sauber einsortiert wird ...

Wie ist den Feld definiert ?

[peschai]

Huch mir ist noch etwas aufgefallen...

Delphi-Quellcode:

  //Sammelphase 
  l:=1; 
  j:= 0; 
  k:=0; 
  while j <= length(temp)-1 do begin 
    while k <= length(temp[j])-1 do begin 
      Feld[l] := temp[j,k]; 
      k:=k+1; 
      l:=l+1; 
    end; 
    j:=j+1; 
  end;

Ich glaube hier stimmt etwas nicht. Dieser Block ist innerhalb deiner 4er-Sortil-Schleife, aber sortil hat hier keinerlei Auswirkung! l,j,k werden alle frisch initialisert...

-> kontrollier mal deine Anweisungsblöcke pro While, If, else... stimmen alle begin und end ?

[Kedariodakon]

Zitat von peschai:

Huch mir ist noch etwas aufgefallen...

Delphi-Quellcode:

  //Sammelphase 
  l:=1; 
  j:= 0; 
  k:=0; 
  while j <= length(temp)-1 do begin 
    while k <= length(temp[j])-1 do begin 
      Feld[l] := temp[j,k]; 
      k:=k+1; 
      l:=l+1; 
    end; 
    j:=j+1; 
  end;

Ich glaube hier stimmt etwas nicht. Dieser Block ist innerhalb deiner 4er-Sortil-Schleife, aber sortil hat hier keinerlei Auswirkung! l,j,k werden alle frisch initialisert...

Weil da Sortil auch gar keine Auswirkungen hat...
Das Sortierverfahren ist so ein Schubkastenverfahren, in der es 2 Phasen gibt einmal alles in die Kisten packen und einmal wieder alles verteilen...

beim verteilen brauch man nicht mehr schauen nach welcher stelle man sortiert hat, man geht einfach alle Kisten von vorn nach hinten durch und packt sie aus...


Die Frage die ich mir aber stelle, was ist Anzahl und Feld?

Bye Christian
Bye Christian

[Isildur]

Hier zur Klärung von Anzahl und Feld(vorgegeben, nicht von mir geschrieben)

Delphi-Quellcode:

const max = 2000;
type TSortieren = class
    private
      Feld : array [0..max] of String;
      Anzahl : Integer;
[...]
procedure TSortieren.DatenLaden(Dateiname : String);
 var i : Integer;
 begin
   kAnzeigefenster.DateiInMemo(Dateiname);
   Anzahl := kAnzeigefenster.getAnzahl;
   if Anzahl > max then anzahl := max;
   for i := 1 to Anzahl do
       Feld[i] := kAnzeigefenster.getZeile(i-1);
end;

Delphi-Quellcode:

function TfrmAnzeigen.getAnzahl: Integer;
begin
  getAnzahl := memAnzeige.Lines.Count;
end;

Feld ist von 0 an deklariert wird aber erst ab 1 benutzt(siehe for-Schleife), m.E. müsste es for i := o to Anzahl-1 heißen. Dass hier ein statischer Array mit jeder Menge leeren Elementen verwendet wird - nya ist halt so..

Edit:Problem scheint gelöst zu sein. Es gab mehrere Fehler, einer der wichtigsten und verstecktesten war der, dass temp[j] nicht auf die Länge 0 zurück gesetz wurde und setlength in der Partionierung daher mist gebaut hat. So scheint es augenblicklich zu klappen(ich glaube es noch nicht ganz aber bisher keine Fehler)

Delphi-Quellcode:

procedure TSortieren.RadixSort;
var sorttil, i, j, k, l: integer;
var temp : array[0..255] of array of string; //array für alle ansichars
var pos : integer;
var ansi : integer;
begin
for sorttil := 4 downto 1 do begin
  //Partionierungsphase
  for i:=0 to Anzahl-1 do begin
    if length(Feld[i]) >= sorttil then begin
      ansi := ord(Feld[i,sorttil]);
      pos := length(temp[ansi]);
      if length(temp[ansi])-1 < 0 then pos := 0;
      setlength(temp[ansi],length(temp[ansi])+1);
      temp[ansi,pos] := Feld[i];
      Feld[i]:=''
    end;
  end;
  //Sammelphase
  l := 0;
  j := 0;
  repeat
    for k := 0 to length(temp[j])-1 do begin
      if length(temp[j])>=k+1 then begin
        Feld[l] := temp[j,k];
        temp[j,k] := '';
        l := l+1;
      end;
    end;
    setlength(temp[j],0);
    j := j+1;
  until j >= 255;
end;

end;

[peschai]

@Kedariodakon:
Stimme dir zu ...
...lag aber auch nicht falsch, denn im ursprünglichen noch fehlerhafte code hätte ilsidur die Sammelphase nach der Sorttil schleife plazieren können, ohne daß sich etwas geändert hätte. Wenn so etwas möglich ist, dann stimmt da was nicht. Die jetzige Korrektur in der //Sammelphase mit dem schreibenden zugriff auf temp bestätigt dies, dann damit bekommt die //Sammelphase einen Sinn innerhalb der Schleife!