Quicksort - theorie

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