zusammenfalten · markieren

Delphi-Quellcode:

    
procedure Quick_Sort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then Quick_Sort(A, iLo, Hi);
  if Lo < iHi then Quick_Sort(A, Lo, iHi);
end;


begin
  Quick_Sort(A, Low(A), High(A));
end;

Ich soll die Zahlen sortieren:

3-7-8-1-[4]-2-6-9-5

Es wird geteilt, ich erhalte Mid=4 - Pivot-Element .
Lo=iLo=3
Hi=iHi=5

3 und 5 stehen richtig so bewegen sich die Zeiger.

Lo bekam die Zahl 7 ,die groesser als 4 ist.
Hi bekam die Zahl 2 ,die kleiner als 4 ist.

Die zahlen werden vertauscht:

3-(2)-8-1-[4]-(7)-6-9-5

Lo=8
Hi=4

Und hier liegt das Problem, ich weiss nicht wie es weiter geht:


(((
Die Zahlen 4 und 8 sollen getauscht werden:

3-2-[4]-1-(8)-7-6-9-5

Lo=1
Hi=1

So wuerde Lo und Hi den Wert 1 haben und die Sortieren wuerde stoppen. Die Zahl 1 soll aber auf die linke Seite.
)))


Ich muss irgendwo einen Fehler gemacht haben. Kann mir jemand sagen wo der Fehler liegt, ob ich alles richtig mache und mir ewentuell Tipps geben?

Low(A) und High(A) geben den unteren und oberen Index von Array A zurück - nicht die Werte an diesen Positionen. Damit haben iLo und iHi beim ersten Aufruf auch die Werte 0 und 8 und nicht 3 und 5.

Edit: Die Methode funktioniert übrigens.

Zitat von Uwe Raabe:

Low(A) und High(A) geben den unteren und oberen Index von Array A zurück - nicht die Werte an diesen Positionen. Damit haben iLo und iHi beim ersten Aufruf auch die Werte 0 und 8 und nicht 3 und 5.

Edit: Die Methode funktioniert übrigens.

iLo und iHi haben die Werte 0 und 8, aber Feld[Lo] und Feld[Hi] haben die Werte 3 und 5.

1. Start: L=0, Hi=8, A[Lo]=3, A[Hi]=5, Mid=4
2. repeat
3. nach den beiden while-Schleifen: Lo=1, Hi=5, A[Lo]=7, A[Hi]=2
4. if-Bedingung ist true, also tauschen und Lo/Hi weiterbewegen: Lo=2, Hi=4, A[Lo]=8, A[Hi]=4
5. until-Bedingung ist false, also weiter nach repeat
6. beide while-Schleifen werden nicht durchlaufen, da A[Lo]{8} < Mid {4} und A[Hi] {4} < Mid {4} fehlschlagen
7. if-Bedingung ist immer noch true, also tauschen und weiterbewegen wie oben: Lo=3, Hi=3, A[Lo]=1, A[Hi]=1
8. until schlägt immer noch nicht zu, also wieder weiter nach repeat
9. A[Lo] {1} ist kleiner als Mid {4} und die erste while-Schleife setzt Lo=4, die zweite while ändert nichts
10. Die if-Bedingung greift nun nicht, aber dafür das until (die beiden schließen sich ja gegenseitig aus)
11. Da Hi {3} > iLo {0} ist, wird QuickSort für [0, 3] aufgerufen
12. Gleiches gilt für Lo {4} < iHi {8}

Zitat von Uwe Raabe:

1. Start: L=0, Hi=8, A[Lo]=3, A[Hi]=5, Mid=4
2. repeat
3. nach den beiden while-Schleifen: Lo=1, Hi=5, A[Lo]=7, A[Hi]=2
4. if-Bedingung ist true, also tauschen und Lo/Hi weiterbewegen: Lo=2, Hi=4, A[Lo]=8, A[Hi]=4
5. until-Bedingung ist false, also weiter nach repeat
6. beide while-Schleifen werden nicht durchlaufen, da A[Lo]{8} < Mid {4} und A[Hi] {4} < Mid {4} fehlschlagen
7. if-Bedingung ist immer noch true, also tauschen und weiterbewegen wie oben: Lo=3, Hi=3, A[Lo]=1, A[Hi]=1
8. until schlägt immer noch nicht zu, also wieder weiter nach repeat
9. A[Lo] {1} ist kleiner als Mid {4} und die erste while-Schleife setzt Lo=4, die zweite while ändert nichts
10. Die if-Bedingung greift nun nicht, aber dafür das until (die beiden schließen sich ja gegenseitig aus)
11. Da Hi {3} > iLo {0} ist, wird QuickSort für [0, 3] aufgerufen
12. Gleiches gilt für Lo {4} < iHi {8}

Nochmal langsam !
Lo=3, Hi=3, A[Lo]=1, A[Hi]=1 also,
A[Lo]< Mid => Inc(Lo) , Lo=4, A[Lo]=8
A[Hi]> Mid => Hi=3, A[Hi]=1
Until greift zu, somit wird Quicksort rekursiv aufgerufen...

Die Zahlenfolge bleibt:
3-2-[4]-1-(8)-7-6-9-5
also immer noch nicht richtig...

Iwas verstehe ich nicht ?



Edit: Noch eine Frage? Woher weiss das Programm, dass Lo links und Hi rechts sein soll?

Zitat von rsplisu:

Until greift zu, somit wird Quicksort rekursiv aufgerufen...

Die Zahlenfolge bleibt:
3-2-[4]-1-(8)-7-6-9-5
also immer noch nicht richtig...

Iwas verstehe ich nicht ?

Das ist genau der Punkt. QuickSort wird nach dem repeat-until rekursiv aufgerufen. Einmal für A[0{iLo}..3{Hi]] = (3,2,4,1) und dann für A[4{Lo}..8{iHi}] = (8,7,6,9,5). Zu diesem Zeitpunkt sind aber alle Werte im unteren Array-Bereich kleiner als die Werte im oberen Array-Bereich. Jeder rekursive Aufruf sortiert also nur noch einen Teilbereich des gesamten Arrays. Der repeat-until Block im Quicksort sortiert nicht die Zahlen nach Reihenfolge, sondern sorgt nur dafür, daß die kleinen alle nach unten kommen und die großen nach oben. Dann wird jeder Teil für sich rekursiv weiter sortiert.