Laufzeitkomplexität

Das Komplexitätsverhalten des Algorithmus hängt im Wesentlichen von der Wahl des Pivotwertes ab. Im Idealfall wäre der Pivotwert der Mittelwert der Menge. Um den Mittelwert zu berechnen, wird aber eine Komplexität von N benötigt, da die Menge einmal durchlaufen werden müßte. Dies würde aber die Komplexität enorm verschlechtern. Deswegen ist es im Allgemeinen eine gute Lösung, nur eine Näherung oder gar nur eine Annahme als Pivotwert zu verwenden. Häufig wird in einfachen Implementierungen das erste, letzte, oder das mittlere ($index = N/2$) Element der Menge als Pivotwert verwendet. Letzendlich ist dies nicht von Bedeutung, da es hier mehr oder weniger dem Zufall überlassen ist, wie gut sich dieser Wert für einen effizienten Ablauf des Algorithmus eignet. Das Verwenden eines wahlfreien Elements als Pivotwert ist nur insofern effizient, da es eine Komplexität von $O(1)$ benötigt dieses zu lokalisieren. Auf der anderen Seite verliert der Algorithmus die Kontrolle über die Abschätzung eines guten Pivotwertes. Dies kann zur Wahl eines sehr schlechten Pivotelementes führen. Im worst case wäre ein solcher Wert der Größte bzw. der Kleinste in der zu sortierenden Menge. Wie schon erwähnt wäre der beste Pivotwert der Mittelwert der Menge, sprich:

\begin{displaymath}\frac{1}{N}\times\sum_{i=0}^{N-1}a[i]\end{displaymath}

Zu beachten, dass in der hier vorgestellten Implementierung der Pivotwert tatsächlich in der Menge vorhanden sein muss, was in anderen Implementierungen nicht zwingend notwendig ist.

Unabhänging von der Wahl des Pivotwertes wird die Menge ungefähr $log_2N$ mal geteilt. Vereinfacht dargestellt müssen in jeder Teilmenge M Operationen durchgeführt werden, wobei M die Anzahl der Elemente in der Teilmenge selbst bezeichnet. Insgesamt ergibt sich somit eine Laufzeitkomplexität von $O(N \times log_2N)$ für den QuickSort.

Ein weiterhin sehr interessanter Punkt bei der Laufzeitbetrachtung ist die Analyse des Speicherplatzverbrauchs des Algorithmus. Wie später noch zu sehen wird, gibt es deutliche Unterschiede. Eine rekursive Implementiung kann im worst case Speicherplatz der Größe N verbrauchen. Im krassen Gegensatz steht dazu die iterative Implementierung, die gewährleistet, nicht über eine Größe von $log_2N$ zu kommen.

Die folgenden Tabellen mit ihren Daten wurden mit den hier gezeigten Implementierungen erstellt. Alle Tests wurden auf der gleichen Datenmenge erstellt, und gewinnen somit kokrete Aussagekraft im Vergleich der Implementierungen. In allen Tabellen befinden sich Werte für eine rekursive wie auch für eine iterative Variante (siehe Implementierung). Bei beiden Lösungen ist die Anzahl der Vergleichs- und Tauschoperationen gleich. Nur die letzten Spalten sind jeweils Implementierungsbezogen. Die letzte Spalte gibt die maximale Stackgröße beim Ablauf der iterativen Funktion. Dagegen ist in der vorletzten Spalte die maximale Rekursionstiefe der rekursiven Funktion sichtbar. Obwohl diese verschiedenen Werte nicht direkt miteinander vergleichbar sind, geben sie eine ungefähre Auskunft darüber, wieviel Speicherplatz die jeweiligen Implementierungen in Anspruch nehmen. Man beachte, daß bei jedem Rekursionsaufruf die lokalen Variablen gespeichert werden müssen, um späpter restauriert werden zu können. Wenn die Rekursion eine bestimmte Tiefe erreicht, so kann man davon ausgehen, daß der Stack eine Größe der Rekrusionstiefe mal die Größe eines Funktionsframes erreicht. Dies geschieht bei der iterativen Vorgehensweise nicht direkt, da kein Aufruf ihrer selbst erfolgt. Die Iterative Lösung behandelt das Speichern von benötiger Information selbst, durch die explizite Verwendung eines eigenen Stacks, und erzielt somit einen wesentlich geringeren Speicherverbrauch.

Tabelle 1 entstand durch die Sortierung einer Menge mit zufällig generierten Werten. Dies sollte einen average case inszenieren. Zu beachten ist, daß die Vergleichszahlen stark von den konkreten Werten abhängen und somit von der obigen Formel abweichen.


Elemente Vergleiche Tauschoperationen Rekursionstiefe Stackgröße
5 20 4 4 4
10 49 9 6 4
100 793 155 11 10
1000 15984 2340 27 12
10000 614647 25157 131 12


In der folgenden Tabelle ist, wie zuvor, eine Auflistung der entsprechenden Werte zu sehen. Die veränderte Eigenschaft ist hier die Anordnung der Datenelemente in der zu sortierenden Datenemenge. Der Test spiegelt das Verhalten des Quicksort auf einer bereits vorsortierten Menge, hier aufsteigend vorsortiert. Man beachte, daß der Algorithmus auf solchen Datenmengen unakzeptabel schlechte Laufzeiten entwickelt. Bei der rekursiven Lösung ist zudem noch zu sehen, wie die Rekusionstiefe linear mit der Anzahl der Elemente wächst, was sehr viel Speicherplatz in Anspruch nimmt. Dagegen ist die iterative Lösung mit einem konstant großen Stack speicherplatzsparend.


Elemente Vergleiche Tauschoperationen Rerusionstiefe Stackgröße
5 22 4 4 4
10 72 9 9 4
100 5247 99 99 4
1000 502497 999 999 4
10000 50024997 9999 9999 4


Bei der nächsten Tabelle waren die Daten bereits absteigend vorsortiert. Es ist zu sehen, daß sich die Werte kaum zu dem vorherigen Fall unterscheiden.


Elemente Vergleiche Tauschoperationen Rerusionstiefe Stackgröße
5 20 4 4 4
10 67 9 9 4
100 5197 99 99 4
1000 501997 999 999 4
10000 50019997 9999 9999 4


Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Implementierung Aufwärts: QuickSort Vorherige Seite: Beispiel   Inhalt

2002-05-09