mein QuickSort funktioniert nicht richtig..

Luzzifus · Beiträge: 200 Win2K D6 Prof

Mein QuickSort funktioniert nicht so ganz richtig, ich hab einfach keine Ahnung was da nicht stimmt.

Zuerst mal der Algorithmus:

markieren

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:

markieren

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#)

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!

markieren

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]; //<---- Dieser Abschnitt fehlt in deiner Routine.
    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

Wenn ich das einbaue, hängt er sich IMMER auf, nicht nur bei längeren Listen. :cry:

Tilo · Verfasst: Sa 30.10.04 14:48

Liegt es vielleicht am Rechner?

Luzzifus · Beiträge: 200 Win2K D6 Prof

wie meinste das? :shock:

Luzzifus · Beiträge: 200 Win2K D6 Prof

naja ich hab jetzt bissi drüber nachgedacht nochmal und bin auf eine stelle gestoßen:

markieren

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:

markieren

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

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 · Beiträge: 200 Win2K D6 Prof

so mir war's jetzt zu dumm, ich hab mir ausm netz ne andere implementation geholt und nu geht das:

markieren

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 :wink:

).

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme