Zuerst sei eine Funktion namens ``partition'' vorgestellt, die dafür verantwortlich ist, die grobe Vorsortierung durchzufüren.
Diese Routine liefert als Rückgabewert die Postition in der Menge zurück, an der das Pivotelement eingereiht wurde.
Die hier gezeigte Implementierung der Funktion nimmt das linke Element als Pivotwert. Danach werden kleinere Element von links
und größere Elemente von rechts gesucht und diese vertauscht. Anschließend wird das Pivotelement zwischen diese gesetzt.
Somit wird sichergestellt, daß links vom Pivotwert Elemente, die kleiner sind, links von diesem stehen, und Elemente, die
größer als das Pivotelement sind, rechts von diesem gesetzt werden.
Da das Pivotelement am Anfang ganz links in der
Menge steht, dient als Abbruchkriterium für das Suchen nicht die Stelle des Pivotwertes, sondern die Situation, in welcher
sich left und right überkreuzen.
Da der neue Index des Pivotelements bei der Sortierung noch gebraucht
wird, wird er an den Aufrufer zuückgeliert.
![\begin{listing}{1}
int partition( int * data, int lo, int hi )
{
int left, righ...
...ta[lo] = data[right];
data[right] = pivot;
\par return (right);
}
\end{listing}](img32.png)
Unterabschnitte
Nächste Seite
Aufwärts
Vorherige Seite
Inhalt
Nächste Seite: rekursiv
Aufwärts: QuickSort
Vorherige Seite: Laufzeitkomplexität
Inhalt
2002-05-09
