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....