Quicksort - theorie

[rsplisu]

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?

[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.

[rsplisu]

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.

[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}

[rsplisu]

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?

[Uwe Raabe]

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.

[sx2008]

Um Quicksort zu verstehen muss man den Algorithmus visuell betrachten.
https://www.youtube.com/watch?v=ywWBy6J5gz8 (Ton leise stellen, sonst nervt es)

[Romiox]

Zitat von sx2008:

Um Quicksort zu verstehen muss man den Algorithmus visuell betrachten.
https://www.youtube.com/watch?v=ywWBy6J5gz8 (Ton leise stellen, sonst nervt es)

[OT]

.
.
.
.
.

[/OT]

[rsplisu]

Zitat von Uwe Raabe:

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.

Also wenn 4 das Pivot-Element ist muss es nach dem ersten Durchgang nicht an seiner richtigen stelle stehen..?'

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

[Uwe Raabe]

Zitat von rsplisu:

Also wenn 4 das Pivot-Element ist muss es nach dem ersten Durchgang nicht an seiner richtigen stelle stehen..?'

Das ist bei dieser Implementation von Quicksort so, muss aber nicht zwingend so sein. Es gibt auch Implementierungen, die das Pivot-Element gar nicht in die Rekursion mit einfließen lässt. Geht man wie in diesem Fall davon aus, daß kein Wert doppelt vorkommt, dann kann man das Pivot-Element auch zwischen den Listen anordnen.

Zitat von rsplisu:

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

Ich weiß nicht genau, was du damit meinst. Lo und Hi sind einfach nur Variablennamen, die verdeutlichen sollen, daß in Lo der niedrigere Index und in Hi der höhere Index des Arrays stehen soll.

Wenn es aber um die Sortierung des Arrays gehe, das wird durch die Vergleiche in den beiden while-Schleifen festgelegt. Wenn du die beiden Operatoren umdrehst, wird das Array absteigend sortiert.