Entwickler-Ecke
Algorithmen, Optimierung und Assembler - mein QuickSort funktioniert nicht richtig..
Luzzifus - Fr 29.10.04 13:57
Titel: mein QuickSort funktioniert nicht richtig..
Mein QuickSort funktioniert nicht so ganz richtig, ich hab einfach keine Ahnung was da nicht stimmt.
Zuerst mal der Algorithmus:
Delphi-Quelltext
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:
| procedure QuickSort(left, right: Integer; var ax: Array of TUnicodeDB);
function tile(l,r: Integer): Integer;
var
pe : WideString;
S : TUnicodeDB;
begin
pe:=ax[(l+r) div 2].rom;
while l<r do begin
while (WideCompareStr(ax[l].rom,pe)<0) and (l<r) do inc(l);
while (WideCompareStr(ax[r].rom,pe)>0) and (l<r) do dec(r);
S:=ax[l];
ax[l]:=ax[r];
ax[r]:=S;
end;
tile:=l;
end;
var
posx : Integer;
begin
if right>left then
begin
posx:=tile(left,right);
QuickSort(left, posx, ax);
quicksort(posx+1, right, ax);
end;
end; |
das wird aufgerufen z.b. mit:
Delphi-Quelltext
1:
| QuickSort(0, length(aCutDB)-1, aCutDB); |
Wenn das Array relativ klein ist, funktioniert es, aber wenn ich größere Teile des Arrays sortieren lasse, hängt er sich immer auf (als ob er irgendwo festhängt). Dabei kann ich nicht sagen, ob's an der Array-Länge liegt oder an bestimmten Elementen.
Bin für jede Hilfe dankbar.. :D
Moderiert von 
Christian S.: Topic aus CLX / Delphi Language (Object-Pascal) verschoben am Sa 30.10.2004 um 14:52
Udontknow - Fr 29.10.04 14:08
Hallo!
Ich habe mal ganz tief in meinen Sourcen gebuddelt, und das ausgegraben.
Also, ich weiss auch nicht mehr genau, wieso ich das jetzt so gemacht hatte, aber es funktioniert... So ist das mit diesen Routinen: Einmal aufgebaut, hurra, ewig genutzt, und nach Jahren weiss man nicht mehr, wie man sie konstruiert hatte! :)
Delphi-Quelltext
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:
| procedure TExtObjectList.QuickSort(const l, r: Integer;
const CompareMethod: TCompareMethod);
var x, i, j : integer;
tmp:TExtObject;
begin
if r > l then
begin
x := l;
i := l;
j := r;
tmp:=NIL;
while i<j do
begin
While (i<r) and not (CompareMethod(Items[i],Items[x])=ATallerB) do
i := i+1;
While (j>l) and (CompareMethod(Items[j],Items[x])=ATallerB) do
j := j-1;
tmp := Self[j];
Self[j] := Self[i];
Self[i] := tmp;
end;
self[i] := self[j]; self[j] := self[l];
self[l] := tmp;
quicksort(l, j-1, CompareMethod);
quicksort(j+1, r, CompareMethod);
end;
end; |
Cu,
Udontknow
Luzzifus - Fr 29.10.04 14:15
Wenn ich das einbaue, hängt er sich IMMER auf, nicht nur bei längeren Listen. :cry:
Tilo - Sa 30.10.04 14:48
Liegt es vielleicht am Rechner?
Luzzifus - Sa 30.10.04 21:46
wie meinste das? :shock:
Luzzifus - Sa 30.10.04 22:19
naja ich hab jetzt bissi drüber nachgedacht nochmal und bin auf eine stelle gestoßen:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
| while l<r do begin
while (WideCompareStr(ax[l].rom,pe)<0) and (l<r) do inc(l);
while (WideCompareStr(ax[r].rom,pe)>0) and (l<r) do dec(r);
S:=ax[l];
ax[l]:=ax[r];
ax[r]:=S;
end; |
dort hängt er sich auf weil es konstellationen gibt, in denen er immer hin- und herwechselt ohne die grenzen l und r zu verändern (wenn beide gefundenen elemente genauso groß sind wie das pivotelement). desweiteren muss die stelle des pe zurückgegeben werden und nicht l oder r (ein hoch auf websites die algorithmen falsch erklären :evil:). ich hab ausserdem noch die funktion tile bezüglich worst case optimiert (zufällige wahl des pivotelement), die sieht nun so aus:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
| function tile(l,r: Integer): Integer;
var
pe : WideString;
S : TUnicodeDB;
xpe : Integer;
begin
xpe:=RandomRange(l,r);
pe:=ax[xpe].rom;
while l<r do begin
while (WideCompareStr(ax[l].rom,pe)<0) and (l<r) do inc(l);
while (WideCompareStr(ax[r].rom,pe)>0) and (l<r) do dec(r);
S:=ax[l];
ax[l]:=ax[r];
ax[r]:=S;
inc(l);
dec(r);
end;
tile:=xpe;
end; |
jetzt sortiert er zwar ohne sich dabei aufzuhängen, sortiert aber nicht fertig, d.h. ich muss das sortieren etwa dreimal auslösen bis er alles komplett richtig sortiert hat. jetzt dachte ich das liegt an der WideCompareStr-Funktion, aber auch wenn ich meine eigene vergleichs-funktion schreibe, passiert das.
langsam verzweifel ich hier wirklich :cry:
BenBE - Sa 30.10.04 23:11
Muss bei dem Tausch nicht noch eine Abfrage rein?
Weiterhin muss am Ende der Liste ne Rekursion folgen.
Auch solltet ihr mal die Abbruchbedingung der Liste prüfen.
Probier mal aus, was passiert, wenn ihr dort die Gleichheit noch mit erlaubt.
Luzzifus - So 31.10.04 01:02
| Zitat: |
| Muss bei dem Tausch nicht noch eine Abfrage rein? |
welche denn? mir fällt nix ein was an der stelle ausgeschlossen bzw. eingegrenzt werden müsste.
| Zitat: |
| Weiterhin muss am Ende der Liste ne Rekursion folgen. |
was meinst du denn damit? :shock:
| Zitat: |
Auch solltet ihr mal die Abbruchbedingung der Liste prüfen.
Probier mal aus, was passiert, wenn ihr dort die Gleichheit noch mit erlaubt. |
wenn ich gleichheit erlaube wird alles nur noch schlimmer (egal an welcher stelle).
das mit dem pe zurückgeben hab ich wieder aufgegeben (war schwachsinn) und hab durch debuggen rausgefunden, dass posx (also die trennungsstelle) irgendwann -1 wird. logisch da ja vor dem setzen des rückgabewertes l und r jeweils nochmal weitergesetzt werden. wenn ich nun aber r+1 statt r zurückgebe, hängt er sich ab und zu in der letzten rekursionsstufe auf (nur noch zweielementige listen zu sortieren), und zwar immer dann wenn er gleiche elemente miteinander vergleicht. wenn ich dem entsprechend entgegenwirke, hab ich wieder den fall dass die liste zum schluss nicht vollständig sortiert ist.
Luzzifus - So 31.10.04 10:40
so mir war's jetzt zu dumm, ich hab mir ausm netz ne andere implementation geholt und nu geht das:
Delphi-Quelltext
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:
| procedure QuickSort(left, right: Integer; var ax: Array of TUnicodeDB);
var
pe : WideString;
S : TUnicodeDB;
l,r : Integer;
begin
if left<right then
begin
l:=left;
r:=right;
pe:=ax[round((l+r)/2)].rom;
while (l<r) do begin
while (WideCompareStr(ax[l].rom,pe)<0) do inc(l);
while (WideCompareStr(ax[r].rom,pe)>0) do dec(r);
if l<=r then
begin
S:=ax[l];
ax[l]:=ax[r];
ax[r]:=S;
inc(l);
dec(r);
end;
end;
if left<r then QuickSort(left, r, ax);
if right>l then quicksort(l, right, ax);
end;
end; |
also danke an alle die mit mir verzweifelt waren ( :D ), jetzt funktioniert's und ihr braucht euch nicht weiter den kopf zu zerbrechen (falls ihr das getan habt :wink: ).
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!