iterativ (nicht rekursiv)

Eine etwas anspruchsvollere, aber wesentlich effizientere Version des QuickSort ist die iterative Variante. Um die Effizienz dieser Implementirung im Vergleich zur Rekursion zu unterstreichen, sei an dieser Stelle auf den Abschnitt Laufzeitkomplexität verwiesen. Da bei der rekursiven Variante, das Problem des Speicherplatzes entsteht, versucht die iterative Lösung den Speicherverbrauch zu minimieren. Beim Ablauf des Algorithmus muss gegebenenfalls auf Werte (Indizes) aus vorherigen Iterationen zurückgriffen werden, weswegen die im Folgenden vorgestellte Funktion explizit einen Stack verwendet. Der Clue hier ist, sich nur die notwendigste Information abzuspeichern und somit das Wachsen des Stacks zu reduzieren. Dies wird dadurch erreicht, daß die Teilmengen nicht in einer beliebegen Ordnung abgearbeitet, sondern auf ihre Größe verglichen werden. Nur die grössere Menge wird auf dem Stack abgelegt, wobei die Klenere sofort weiterbearbeitet wird. (Abgelegt wird tatsächlich nur die Information durch welche Indizes die Menge begrenzt ist).
Im folgenden Listing bezeichen die Funktionen push, pop, stack_init und stack_is_emtpy Operationen auf dem explizit verwendeten Stack.

$\begin{listing}{1} void iterarive_quick_sort( int * data, int N ) { int left, r... ...= pop(); left = pop(); } } while( stack_is_emtpy() != TRUE ); } \end{listing}$

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: Optimierung Aufwärts: Implementierung Vorherige Seite: rekursiv Inhalt

2002-05-09