rekursiv

Da die Hauptarbeit durch die partition-Funktion übernommen wird, muss nur noch ein Verfahren erstellt werden, welches dafür sorgt, die Aufteilung der Menge entsprechend durchzuführen. Durch eine rekursive Implementierung ist dies sehr einfach zu bewerkstelligen. Die nachfolgende Funktion soll eine Möglichkeit verdeutlichen.
Es wird überprüft, ob die zu behandelnde Menge mehr als ein Element enthält. Trifft dies nicht zu, so ist keine Teilung (Partitionierung) notwendig. Im anderen Fall, wird die Partitionierung auf der Teilmenge ausgeführt, und die Menge getrennt. Die so entstandenen Teilmengen werden mit dem QuickSort unabhängig voneinander für sich sortiert.
Man beachte, dass bei der Trennung der Menge das Pivotelement in keine der entstehenden Menge aufgenommen wird, da es schon auf seiner richtigen Position liegt.
Die folgend implementierte Funktion wird mit der Addresse des Arrays, dem Startindex und dem Index des letzten Elements (N-1) aufgerufen.

$\begin{listing}{1} void rekursive_quick_sort( int * a, int lo, int hi ) { if( h... ... ); rekursive_quick_sort( a, right+1, hi, compares, swaps ); } } \end{listing}$

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: iterativ (nicht rekursiv) Aufwärts: Implementierung Vorherige Seite: Implementierung Inhalt

2002-05-09