Ich hab mir jetzt mal einen eigenen Sortieralgorithmus für Integer Werte geschreiben... dieser ist nicht an bekannte Algorithmen angelehnt (glaub ich zumindest
)
zur Zeit brauch mein Algo für 10000 Integer Zahlen zwischen 0.042 ~ 0.055 Sekunden; kommt immer darauf an wie viele Zahlen mehrfach enthalten sind...
hier mein Code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
| var
unsortierte_liste,sortierte_liste:array of integer;
bool_liste:array of bool;
doppel_liste:array of array of integer;
procedure bool_sort;
var i,j,k,max,min,pos,d_pos,dl_laenge:integer;
doppelt:bool;
begin
min:=unsortierte_liste[0];
max:=min;
pos:=0;
d_pos:=0;
dl_laenge:=1;
doppelt:=false;
for i:=0 to length(unsortierte_liste)-1 do
begin
if unsortierte_liste[i]<min then min:=unsortierte_liste[i];
if unsortierte_liste[i]>max then max:=unsortierte_liste[i];
end;
setlength(bool_liste,max-min+1);
setlength(doppel_liste,1,2);
for i:=0 to length(unsortierte_liste)-1 do
begin
if bool_liste[unsortierte_liste[i]-min]=true then
begin
for j:=0 to dl_laenge-1 do
begin
if unsortierte_liste[i]=doppel_liste[j,0] then
begin
doppelt:=true;
d_pos:=j;
break;
end;
end;
if doppelt=true then
begin
inc(doppel_liste[d_pos,1]);
end
else
begin
doppel_liste[dl_laenge-1,0]:=unsortierte_liste[i];
doppel_liste[dl_laenge-1,1]:=1;
inc(dl_laenge);
setlength(doppel_liste,dl_laenge,2);
end;
doppelt:=false;
end;
bool_liste[unsortierte_liste[i]-min]:=true;
end;
setlength(sortierte_liste,length(unsortierte_liste));
for i:=0 to length(bool_liste)-1 do
begin
if bool_liste[i]=true then
begin
for j:=0 to length(doppel_liste)-1 do
begin
if i+min=doppel_liste[j,0] then
begin
for k:=0 to doppel_liste[j,1]-1 do
begin
sortierte_liste[pos]:=i+min;
inc(pos);
end;
break;
end;
end;
sortierte_liste[pos]:=i+min;
inc(pos);
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var j,zahl:integer;
start,ende,f:int64;
begin
zahl:=strtoint(edit1.text);
randomize;
setlength(unsortierte_liste,zahl);
for j:=0 to zahl-1 do
begin
unsortierte_liste[j]:=random(zahl*10);
end;
QueryPerformanceCounter(Start);
bool_sort;
QueryPerformanceCounter(ende);
QueryPerformanceFrequency(f);
showmessage(floattostr((ende-start)/f));
setlength(bool_liste,0);
setlength(doppel_liste,0,2);
setlength(sortierte_liste,0);
setlength(unsortierte_liste,0);
end; |
Funktionsprinzip:
1. die min. und max. Zahl wird ermittelt
2. daraus wird eine boolean Tabelle erstellt die (max-min+1) lang ist
3. der unsortierte Array wird Element für Element abgegrasst und dabei wird die integer Zahl einfach als Index für den boolean Array genommen, der dann auf True gesetzt wird (z.B I-zahl=100 -> boolen_array[100]=true)
4. es wird auf doppelte Zahlen geprüft, sollte es doppelte Zahlen geben wird diese Zahl in einem zusätzlichen Array mit Anzahl gespeichert
5. am Ende wird der boolean Array ausgewerte und die Zahlenwerte werden in den sortierten Array geschreiben
ich hoffe das war halbwegs klar beschreiben und ihr seit nicht allzu verwirrt...
ich weis das dieser Algorithmus nicht gerade RAM sparend ist..aber darum ging es mir weniger(da kann man sicher auch noch was drehen, zB für die sortierten Werte einfach den unsortierten Array überschreiben statt ein neuen Array zu nutzen...)
Hauptsächlich gings mir natürlich um Geschwindigkeit.
Was meint ihr dazu und wo kann man noch was am Speed drehen?
//EDIT: auch BucketSort genannt
