Quicksort - theorie

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