Autor |
Beitrag |
Luzzifus
Beiträge: 200
Win2K
D6 Prof
|
Verfasst: Fr 29.10.04 13:57
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
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: 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!
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
Beiträge: 200
Win2K
D6 Prof
|
Verfasst: Fr 29.10.04 14:15
Wenn ich das einbaue, hängt er sich IMMER auf, nicht nur bei längeren Listen.
|
|
Tilo
Beiträge: 1098
Erhaltene Danke: 13
Win7 geg. WInXP oder sogar Win98
Rad2007
|
Verfasst: Sa 30.10.04 14:48
Liegt es vielleicht am Rechner?
|
|
Luzzifus
Beiträge: 200
Win2K
D6 Prof
|
Verfasst: Sa 30.10.04 21:46
wie meinste das?
|
|
Luzzifus
Beiträge: 200
Win2K
D6 Prof
|
Verfasst: 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 ). 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
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Luzzifus
Beiträge: 200
Win2K
D6 Prof
|
Verfasst: 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?
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
Beiträge: 200
Win2K
D6 Prof
|
Verfasst: 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 ( ), jetzt funktioniert's und ihr braucht euch nicht weiter den kopf zu zerbrechen (falls ihr das getan habt ).
|
|
|