Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

[Caspar]

Hey, ich bin relativ neu auf dem Forum, also seid ein wenig nachsichtig ;)

Ich habe ein kleines Sortierprogramm geschrieben und habe ein klein Stack-Overflow, wenn ich auf den Knopf drücke.
ich habe ein String Grid, wo auf der einen Seite die Zufälligen Zahlen stehen und auf der anderen Seite die Sortierten.

Hier mein Code:

Code:

procedure Quicksort(l,r: Integer);
  var
    i,j,Mitte,Merke: Integer;

  begin
    i:=0;
    j:=999;
   Mitte:=Zahl[(0+999) div 2];
    repeat
      while Zahl[i]<Mitte do Inc(i);

      while Mitte<Zahl[j] do Dec(j);

      if i<=j then
        begin
          Merke:=Zahl[i];
          Zahl[i]:=Zahl[j];
          Zahl[j]:=Merke;
          Inc(i);
          Dec(j);
        end;
    until i>j;
    if 0<j then Quicksort(0,j);

    if i<999 then Quicksort(i,999);

  end;


 procedure TForm1.Button5Click(Sender: TObject);
 var a:integer;
begin
   Quicksort(0,999) ;

   For a:=0 to 999 do
 begin
  StringGrid1.Cells[1,a] :=  inttostr(Zahl[a]);
 end;


end;

Als Globale Variable habe ich "Zahl" als Array von 0 bis 999.

Zahl : Array[0..999] of Integer;


Ich bin noch recht unerfahren in Delphi, also bitte es leicht erklären :o

[Delphi-Laie]

Das ist kein Quick-, sondern ein Circlesort. Woher hast Du den Algorithmus? Edit: Das mit dem Circlesort nehme ich evtl. zurück....

Und der Stack wird erschöpft, weil die Rekursion nicht abbricht, sondern gegen unendlich strebt.

[Caspar]

Ich habe das aus meinem Schulbuch, wo es auch als Quicksort beschrieben wurde :o

[Delphi-Laie]

Zitat:

Zitat von Caspar (Beitrag 1380658)

Ich habe das aus meinem Schulbuch, wo es auch als Quicksort beschrieben wurde :o

Ja, zog es auch schon vorsichtig zurück. Das Pivotelement läßt sich meinetwegen auch aus der Mitte entnehmen / gewinnen.

Die Prozedur ruft sich immer und immer wieder selbst auf, anstatt daß sich dieses Vorgehen irgendwann beendet. Deshalb ist der Stack irgendwann erschöpft.

j muß sich im Verlaufe der Aufrufe immer mehr 0, i immer mehr 999 annähern. Tut es das? Höchstwahrscheinlich nicht.

Edit: nimm mal statt

Delphi-Quellcode:

Mitte:=Zahl[(0+999) div 2];

besser

Delphi-Quellcode:

Mitte:= (i+j) div 2;

(und nicht "Zahl[(i+j)"!)

[Caspar]

Ne, das hat leider nicht funktioniert.
Es kommt immer noch die Fehlermeldung des Stackoverflow.

[nahpets]

Quicksort wird mit den Parametern l und r aufgerufen. Die werden innerhalb der Routine aber nie benutzt. Das kann so nicht stimmen, da sie den Bereich bestimmen, der sortiert werden soll.

Dashier ist mit an Sicherheit grenzender Wahrscheinlichkeit falsch:

Delphi-Quellcode:

i := 0;
j := 999;
Mitte := Zahl[(0+999) div 2];

i müsste eher = l sein und j = r.
Mitte muss die Mitte zwischen l und r sein.

eventuell etwa so?

Delphi-Quellcode:

i := l;
j := r;
Mitte := Zahl[(i + j) div 2];

[Caspar]

Ja, 0 ist im Prinzip l, da es auf dem String Grid ja kein Links und Rechts gibt ist Links dann oben, also 0.
Rechts / r ist dann unten, ergo 999.

[nahpets]

Nein, nur beim ersten Aufruf, danach wird jeweils neu entschieden, welcher Bereich sortiert werden soll. Das ist jeweils entweder die obere Hälfte des noch nicht sortierten Bereiches oder die untere Hälfte.

So wie Du das machst, wird bei jedem Aufruf immer alles sortiert und das rekursive, also mit jedem Aufruf immer alles und mit dem nächsten Aufruf wieder alles ... - daraus resultiert dann der Stackoverflow, weil die Rekursion nie beendet wird.

Ändere Deine Routine bitte mal entsprechend meines Vorschlages und prüfe, ob der Fehler weg ist, dann prüfe, ob die Sortierung korrekt ist, wenn nein, dann beschreibe uns bitte die aufgetretenen Fehler, damit wir weiterschauen können.

Das Ignorieren der Werte von l und r ist aber auf jeden Fall falsch.

[Delphi-Laie]

Delphi-Quellcode:

i:=l
j:=r

am Prozeduranfang oder gleich l und r in der Prozedur verwenden.

[Caspar]

Ok, ich habe jetzt wie @nahpets gesagt hat alle "0" und "999" durch l und r ersetzt. Also für 0 l und für 999 l und es funktioniert!

Vielen Dank an euch alle, das ihr mir einerseits geholfen habt und anderseits so schnell geantwortet habt :) :thumb:
Ich bin mir noch nicht ganz sicher warum es jetzt auf einmal klappt, aber ich glaube ich komme bald dahinter :P

Ich hoffe ich werde irgendwann auch mal so gut in Informatik, damit ich dann auch Anfängern, wie mir, helfen kann :)

Ich wünsche euch noch ein Angenehmen Abend!
Lg, Caspar