Quicksort findx Methode Fernuni Hagen 1661

Hallo zusammen!

Bei den Altklausurenaufgaben zu Quicksort wird immer wieder nach dem Pivotelement gefragt, das nach der Methode findx ausgewählt werden muss. Allerdings steht im Buch, dass findx das Pivotelement zufällig auswählt. Den Musterlösungen nach, kann das aber nicht ganz richtig sein.

Daher meine Frage: Auf welche Weise legt die findx Methode im Quicksort aus dem Kurstext des Kurses 1661 das Pivotelement fest?

Vielen Dank!
 
Ich habe es grad schon begriffen. Der Zeiger von findx geht von links nach rechts durch das Array und vergleicht immer zwei Schlüssel i und j. Dabei Wählt der den jeweils größeren als Pivotelement. Wenn die beiden Elemente gleich sind geht der Zeiger weiter nach rechts und wiederholt den Vorgang, bis eines der Elemente größer ist.

Also findx = max(i,j) wenn i>j oder j<i und findx = max(i+1,j+1) wenn i=j.
 
Top