LinearSort - Revisited...

[glkgereon]

Hi,

Es ist schon lange her, da hatte ich einmal den Plan ein Sortierverfahren zu entwickeln welches in Linearer Komplexität funktioniert. Dies hatte ich lange aus den Augen verloren...und nun noch einmal aufgenommen.

Und Voilà, es funktioniert tatsächlich.

Theoretisch ist es zwar nicht ganz allgemein, da die Daten in gewisser weise zusammengestaucht werden müssen, praktisch ist es jedoch für jegliche Anwendung die ich mir vorstellen kann verwendbar.

Vielleicht lassen wir mal etwas Code sprechen:

Delphi-Quellcode:

type
  TType = class(TObject)
    Text: String;
    ID: Cardinal;
  end;
  TTypeArray = array of TType;

TType ist der Typ der sortiert werden soll. hierbei ist es einfach ein String welchem eine ID zugewiesen wird.
Ist nicht nötig, macht aber mein Beispiel einfacher.
Dieser Typ kann vom Programmierer frei gewählt werden...schließlich sind es die Daten die er sortieren will....

Delphi-Quellcode:

  TSortType = class(TObject)
  private
    Datas: TTypeArray;
  public
    procedure Add(Data: TType);
    procedure Get(var Data: TType);
    function Count: Cardinal;
  end;
  TSortArray = array of TSortType;

Das ist eine kleine Interne Klasse....

Delphi-Quellcode:

procedure TSortType.Add(Data: TType);
begin
  SetLength(Datas,Length(Datas)+1);
  Datas[Length(Datas)-1]:=Data;
end;

procedure TSortType.Get(var Data: TType);
begin
  Data:=Datas[Length(Datas)-1];
  SetLength(Datas,Length(Datas)-1);
end;

function TSortType.Count: Cardinal;
begin
  Result:=Length(Datas);
end;

Teile der Internen Verwaltung...

Delphi-Quellcode:

function GetID(P: TType): Cardinal;
begin
  Result:=P.ID;
end;

Diese funktion muss ebenfalls der Programmierer Implementieren. hier liegt der Knackpunkt der "Allgemeinheit" da hier nicht verglichen werden kann sondern jedem DatenObjekt eine ID zugewiesen werden muss. Probleme gibt es hier wenn man Strings sortieren will, da Strings eben in einen Integer indiziert werden wo zwangsläufig Informationen verloren gehen :-/

Delphi-Quellcode:

function GetMaxID: Cardinal;
begin
  Result:=100; //bzw MAXINT;
end;

Und hier kann der Programmierer ebenfalls selber etwas angeben. Die Angabe dient zur Verringerung des Speicherplatzverbrauches...ist der MaximalWert nicht eingrenzwar MAXINT nehmen....aber dann wirds im Ram wüst...

Und nun das Herzstück

Delphi-Quellcode:

procedure Sort(var Data: TTypeArray);
var S: TSortArray;
    i, ID: Integer;
begin
  SetLength(S,GetMaxID);
  for i:=0 to Length(S)-1 do S[i]:=nil;
  for i:=0 to Length(Data)-1 do
    begin
    ID:=GetID(Data[i]);
    if S[ID]=nil then
      begin
      S[ID]:=TSortType.Create;
      S[ID].Add(Data[i]);
      end;
    end;
  ID:=0;
  for i:=0 to Length(S)-1 do
    if S[i]<>nil then
      begin
      while S[i].Count>0 do
        begin
        S[i].Get(Data[ID]);
        Inc(ID);
        end;
      S[i].Free;
      end;
  SetLength(S,0);
end;

eigentlich gibt es kaum etwas zu erklären...

Das Haupt-Manko an dem System ist mir völlig klar. Und bevor ihr fragt, hier liegt es:

Möchte man Daten sortieren, deren ID-Bereich man nicht klar eingrenzen kann, sondern ihn zB berechnet so muss als MaxID der gesamte Integer-Bereich genommen werden. Dem folgt dann ein enormer Ram-Verbrauch weil für jede Zahl ein Pointer à 4 Byte reserviert wird...

jedoch ist er für die sortierung von Zahlen bzw bereits indizierten inhalten perfekt geeignet, da
- er Linear ist ;)
- die Bereiche vom Programmierer gut eingegrenzt werden können
- die ID einfach gebildet werden kann....wie im Beispiel.


Ein Beispiel Programm gibt es natürlich auch...einfach ein Programm mit nem Button und 2 ListBoxen aufs Form und das rein:

Delphi-Quellcode:

procedure Dat2List(D: TTypeArray; Lst: TListBox);
var i:Integer;
begin //Ausgabe in Listbox
  Lst.Clear;
  for i:=0 to Length(D)-1 do
    Lst.Items.Add(IntToStr(D[i].ID)+' '+D[i].Text);
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i:Integer;
    Data: TTypeArray;
begin
  SetLength(Data,10);
  for i:=0 to 9 do
    begin //Init mit Random-Daten
    Data[i]:=TType.Create;
    Data[i].ID:=Random(100);
    Data[i].Text:=IntToStr(Random(1000));
    end;
  Dat2List(Data,ListBox1);
  Sort(Data); //Sortieren
  Dat2List(Data,ListBox2);
  for i:=0 to 9 do Data[i].Free;
  SetLength(Data,0); //Clear
end;

Mich würde nun einfach mal interessieren was ihr davon haltet.
Rein vom Prinzip her das es geht, von der Praxis her ob es überhaupt nutzbar ist und natürlich Performancemäßig, wie schnell er im Vergleich zu herkömmlichen Sortierverfahren ist....