Quicksort - theorie

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

[Delphi-Laie]

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)

Oder es sich in meinem Sortierkino anschauen.

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

[rsplisu]

Noch eine Frage:
Wenn man nur 2 Felder hat,

[4]-5

wobei 4 die Mitte ist. Hi springt, dann auf auf die A(Hi)(4), dadurch werden die Felder Lo und Hi getauscht und es geschieht Dec(hi) und Inc(lo) also A(Hi)(4) und A(Lo)(5). Damit uberlaufen sich Lo und Hi und das Programm endet die Arbeit, weil es nur je ein Feld gibt.

Erklaer ich das richtig?


... mdl Abiturstesss.... :/

[Uwe Raabe]

Zitat von rsplisu:

Wenn man nur 2 Felder hat,

[4]-5

wobei 4 die Mitte ist. Hi springt, dann auf auf die A(Hi)(4), dadurch werden die Felder Lo und Hi getauscht und es geschieht Dec(hi) und Inc(lo) also A(Hi)(4) und A(Lo)(5). Damit uberlaufen sich Lo und Hi und das Programm endet die Arbeit, weil es nur je ein Feld gibt.

So in etwa. In dem Fall sind iLo=0 und iHi=1. Die erste while-Schleife läuft nicht, da A[Lo] = mid ist. Die zweite wird einmal durchlaufen. Danach sind Lo = 0 = Hi und die if-Bedingung schlägt zu, tauscht dabei aber nur A[0] mit A[0], was ja nichts ändert. Dann haben wir nach Inc(Lo) und Dec(Hi) Lo = 1 und Hi = -1. Das bringt die repeat-Schleife zum Abbruch und die rekursiven Aufrufe erfolgen auch nicht.