Quicksort - theorie

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