Quicksort - theorie

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