|
Beschreibe hier die neue Seite.--- |
|
Die Laufzeit von Quicksort ist bestenfalls O(n log(n)), im schlimmsten Fall O(n^2). Der StackBedarf von Quicksort ist im besten Fall O(log(n)) und im schlechtesten Fall O(n). Wir werden dies hier demonstrieren: als Vorwissen braucht man dazu lediglich die grundsätzliche Funktionsweise von QuickSort zu kennen. [[Überschrift]Sortieren mit QuickSort als Baum] Einführung in die Darstellung als Baum Man kann einen Sortiervorgang mit QuickSort hervorragend als Baum darstellen. Solch ein Baum zum Sortieren eines Arrays mit Zahlen von 0 bis 15 sieht dann zum Beispiel so aus: <pre> [0..15] / \ [0..7] [9..15] / / \ [0..6] [9..12] [14..15] / \ / \ \ [0..2] [4..6] [9] [11..12] [15] / / \ \ [0..1] [4] [6] [12] / [0] </pre> An diese Schreibweise muss man sich durchaus zuerst gewöhnen. In der ersten Zeile steht, dass wir ein Array mit Zahlen von 0 bis 15 sortieren wollen. Wir nehmen jetzt mal an, wir erwischen die Zahl 8 als Pivot(element). Dies bedeutet, dass nach der Partitionierung die Zahlen 0 bis 7 im Array alle links von der Zahl 8 stehen, während die Zahlen 9 bis 15 alle rechts von der Zahl 8 sind. Quicksort macht deshalb zwei rekursive Aufrufe der Prozedur Quicksort, einmal um das Teilarray mit Zahlen von 0 bis 7 zu sortieren, und einmal um das Teilarray mit den Zahlen von 9 bis 15 zu sortieren. Diese zwei Aufrufe sieht man in der nächsten Zeile. Beim Aufruf von Quicksort([9..15]) wird nun z.B. die 13 als Pivot gewählt (bzw. erwischt), so dass hier Quicksort sich nach der Partitionierung wiederum als Quicksort([9..12]) und Quicksort([14..15]) aufruft. Für das Pivot selbst wird Quicksort nie aufgerufen, und wir nehmen an, dass die Prozedur Quicksort für leere Teilbereiche ebenfalls nicht aufgerufen wird. Dies muss zwar nicht in jeder Implementation so sein, das ändert aber an der Analyse nichts. Vereinfachung der Darstellung Die obige Darstellung ist zwar schon sehr aufschlussreich, doch beinhaltet sie viele Details, welche uns nicht interessieren. Da wir uns lediglich für die Laufzeit und den Speicherbedarf interessieren, genügt es uns zu wissen, wieviele Zahlen sortiert werden sollen, nicht aber welche. Wenn wir nun die Knoten des obenstehenden Baums einfach mit der Anzahl der zu sortierenden Zahlen beschriften, sieht das so aus: <pre> 16 / \ 8 7 / / \ 7 4 2 / \ / \ \ 3 3 1 2 1 / / \ \ 2 1 1 1 / 1 </pre> Wir stellen fest, dass der Baum die Eigenschaft erfüllt, dass der Wert eines Knotens immer die Summe der Werte der Kinder plus eins entspricht. Zudem ist der Wert der Wurzel genau die Länge des zu sortierenden Arrays. Der Leser kann sich selbst davon überzeugen, dass Bäume die diesen Eigenschaften entsprechen, genau einer mögliche Ausführung von Quicksort entsprechen. Das heisst unter anderem, jeder Baum, der diesen Eigenschaften entspricht, kann aus einer Ausführung von Quicksort hervorgegangen sein. Zudem entspricht jeder Ausführung von Quicksort genau ein solcher Baum. Mit diesen Bäumen gerüstet, wird die Analyse von Quicksort nun wesentlich einfacher. [[Überschrift]Laufzeit] Um die Laufzeit zu analysieren, fragen wir uns, wie lange denn eine Ausführung von Quicksort benötigt, von welcher wir den Baum kennen. Nun, beim Sortieren fallen zunächst die Kosten zum Partitionieren an. Diese entsprechen genau der Anzahl der Zahlen, welche in unserem vereinfachten Baum stehen. Zudem fallen noch Kosten an, um die beiden Teilarrays zu sortieren. (Dies sind gerade die Kosten der beiden Teilbäume links und rechts, welche ja gerade das symbolisieren sollen.) Zusätzlich kommen noch Kosten für Verwaltungsaufgaben hinzu, wie das Anlegen von Einträgen auf dem Stack und sonstige kleinere Sachen. Dieses sind konstante Kosten, und wir können sie mit 1 veranschlagen. Wir legen nun folgende Notation fest für einen Knoten K des Baumes: w(K) ist der Wert von K welcher im vereinfachten Baum steht. l(K) und r(K) sind die linken und rechten Kinder des Knotens oder der spezielle Wert nil. (nil bedeutet, dass für diesen "Zweig" des Knotens kein Unterbaum (Kind) mehr existiert. Daher gilt: kosten(nil) = 0) Die Kosten, um einen Baum mit Wurzel R (für Root) zu sortieren, sind nun: kosten(R) = w(R) + kosten(l(R)) + kosten(r(R)) + 1. Also die Kosten, um zu partitionieren plus die Kosten, um den linken Teilbaum zu sortieren plus die Kosten, um den rechten Teilbaum zu sortieren plus 1 für den Verwaltungsaufwand. BesterFall? Die Laufzeit von QuickSort hängt wesentlich davon ab, wie das Pivotelement gewählt wird. Im Optimalfall wird das Pivotelement so gewählt, dass es nach dem Partitionieren in der Mitte des Arrays steht. In diesem Fall hat man nämlich die zukünftige Arbeit optimal aufgeteilt. Man muss dann nur noch zwei halb so lange Arrays wie zuvor sortieren, was intuitiv auch schon wesentlich einfacher erscheint. Unser Baum würde dann zum Beispiel für ein Array der Grösse 15 so aussehen: <pre> Kosten 15 64 / \ 7 7 24 / \ / \ 3 3 3 3 8 / \ / \ / \ / \ 1 1 1 1 1 1 1 1 2 </pre> Um nun die Kosten zu berechnen, kann man hier unsere obige Formel anwenden. Dies ergibt für die Kosten (jeweils eines betrachteten Knotens) die Werte, welche man in der Spalte Kosten oben sieht. Falls man das im gleichen Stil weiterverfolgt, ergibt sich folgendes Bild: n 1 3 7 15 31 63 Kosten 2 8 24 64 160 384 Und wenn man mal einfach so die Kosten durch n dividiert: n 1 3 7 15 31 63 Kosten/n 2 3 3 4 5 6 Und hier kann man dann schon vermuten dass die Kosten O(n log(n)) sind. Man kann das aber auch direkt zeigen: Die Summe der Kosten in einer "Knotenebene" beträgt jeweils konstant n+1, wie man leicht überprüfen kann, und es gibt ca. log(n) Ebenen (+/-1), wie man sich leicht überlegt. In Summe haben wir also ca. die Kosten (n+1) log(n), d.h. also O(n log(n)). SchlechtesterFall? Der Baum sieht dann folgendermaßen aus: <pre> n / n-1 . . . . . / 3 / 2 / 1 </pre> Hier sieht man, dass man bereits für die Partitionierung eine Laufzeit von 1+2+3+ ... + n benötigt, was O(n^2) ist, wie man sich leicht überlegt. Für die Verwaltung braucht man lediglich O(n), so dass die gesamten Kosten also O(n^2) sind. [[Überschrift]Speicherbedarf] QuickSort sortiert InPlace?: das heisst, es wird kein zusätzliches Array benötigt, um die Daten zu kopieren. Deshalb hängt der zum ursprünglichen Array zusätzlich benötigte Speicherbedarf lediglich von der StackTiefe? ab. Bei der Baum-Darstellung ist die maximale Stacktiefe genau die maximale Tiefe des Baumes, denn jedes Kind entspricht einem Aufruf von Quicksort. Für den besten Fall ist die Stacktiefe also logarithmisch, wie man oben sieht. Im schlechtesten Fall ist sie aber linear. |
| Sortieren mit QuickSort als Baum |
Einführung in die Darstellung als Baum
Man kann einen Sortiervorgang mit QuickSort hervorragend als Baum darstellen. Solch ein Baum zum Sortieren eines Arrays mit Zahlen von 0 bis 15 sieht dann zum Beispiel so aus:
[0..15]
/ \
[0..7] [9..15]
/ / \
[0..6] [9..12] [14..15]
/ \ / \ \
[0..2] [4..6] [9] [11..12] [15]
/ / \ \
[0..1] [4] [6] [12]
/
[0]
An diese Schreibweise muss man sich durchaus zuerst gewöhnen. In der ersten Zeile steht, dass wir ein Array mit Zahlen von 0 bis 15 sortieren wollen. Wir nehmen jetzt mal an, wir erwischen die Zahl 8 als Pivot(element). Dies bedeutet, dass nach der Partitionierung die Zahlen 0 bis 7 im Array alle links von der Zahl 8 stehen, während die Zahlen 9 bis 15 alle rechts von der Zahl 8 sind. Quicksort macht deshalb zwei rekursive Aufrufe der Prozedur Quicksort, einmal um das Teilarray mit Zahlen von 0 bis 7 zu sortieren, und einmal um das Teilarray mit den Zahlen von 9 bis 15 zu sortieren. Diese zwei Aufrufe sieht man in der nächsten Zeile.
Beim Aufruf von Quicksort([9..15]) wird nun z.B. die 13 als Pivot gewählt (bzw. erwischt), so dass hier Quicksort sich nach der Partitionierung wiederum als Quicksort([9..12]) und Quicksort([14..15]) aufruft. Für das Pivot selbst wird Quicksort nie aufgerufen, und wir nehmen an, dass die Prozedur Quicksort für leere Teilbereiche ebenfalls nicht aufgerufen wird. Dies muss zwar nicht in jeder Implementation so sein, das ändert aber an der Analyse nichts.
Vereinfachung der Darstellung
Die obige Darstellung ist zwar schon sehr aufschlussreich, doch beinhaltet sie viele Details, welche uns nicht interessieren. Da wir uns lediglich für die Laufzeit und den Speicherbedarf interessieren, genügt es uns zu wissen, wieviele Zahlen sortiert werden sollen, nicht aber welche. Wenn wir nun die Knoten des obenstehenden Baums einfach mit der Anzahl der zu sortierenden Zahlen beschriften, sieht das so aus:
16
/ \
8 7
/ / \
7 4 2
/ \ / \ \
3 3 1 2 1
/ / \ \
2 1 1 1
/
1
Wir stellen fest, dass der Baum die Eigenschaft erfüllt, dass der Wert eines Knotens immer die Summe der Werte der Kinder plus eins entspricht. Zudem ist der Wert der Wurzel genau die Länge des zu sortierenden Arrays. Der Leser kann sich selbst davon überzeugen, dass Bäume die diesen Eigenschaften entsprechen, genau einer mögliche Ausführung von Quicksort entsprechen. Das heisst unter anderem, jeder Baum, der diesen Eigenschaften entspricht, kann aus einer Ausführung von Quicksort hervorgegangen sein. Zudem entspricht jeder Ausführung von Quicksort genau ein solcher Baum.
Mit diesen Bäumen gerüstet, wird die Analyse von Quicksort nun wesentlich einfacher.
| Laufzeit |
Um die Laufzeit zu analysieren, fragen wir uns, wie lange denn eine Ausführung von Quicksort benötigt, von welcher wir den Baum kennen.
Nun, beim Sortieren fallen zunächst die Kosten zum Partitionieren an. Diese entsprechen genau der Anzahl der Zahlen, welche in unserem vereinfachten Baum stehen. Zudem fallen noch Kosten an, um die beiden Teilarrays zu sortieren. (Dies sind gerade die Kosten der beiden Teilbäume links und rechts, welche ja gerade das symbolisieren sollen.) Zusätzlich kommen noch Kosten für Verwaltungsaufgaben hinzu, wie das Anlegen von Einträgen auf dem Stack und sonstige kleinere Sachen. Dieses sind konstante Kosten, und wir können sie mit 1 veranschlagen.
Wir legen nun folgende Notation fest für einen Knoten K des Baumes: w(K) ist der Wert von K welcher im vereinfachten Baum steht. l(K) und r(K) sind die linken und rechten Kinder des Knotens oder der spezielle Wert nil. (nil bedeutet, dass für diesen "Zweig" des Knotens kein Unterbaum (Kind) mehr existiert. Daher gilt: kosten(nil) = 0)
Die Kosten, um einen Baum mit Wurzel R (für Root) zu sortieren, sind nun: kosten(R) = w(R) + kosten(l(R)) + kosten(r(R)) + 1. Also die Kosten, um zu partitionieren plus die Kosten, um den linken Teilbaum zu sortieren plus die Kosten, um den rechten Teilbaum zu sortieren plus 1 für den Verwaltungsaufwand.
BesterFall?
Die Laufzeit von QuickSort hängt wesentlich davon ab, wie das Pivotelement gewählt wird. Im Optimalfall wird das Pivotelement so gewählt, dass es nach dem Partitionieren in der Mitte des Arrays steht. In diesem Fall hat man nämlich die zukünftige Arbeit optimal aufgeteilt. Man muss dann nur noch zwei halb so lange Arrays wie zuvor sortieren, was intuitiv auch schon wesentlich einfacher erscheint.
Unser Baum würde dann zum Beispiel für ein Array der Grösse 15 so aussehen:
Kosten
15 64
/ \
7 7 24
/ \ / \
3 3 3 3 8
/ \ / \ / \ / \
1 1 1 1 1 1 1 1 2
Um nun die Kosten zu berechnen, kann man hier unsere obige Formel anwenden. Dies ergibt für die Kosten (jeweils eines betrachteten Knotens) die Werte, welche man in der Spalte Kosten oben sieht.
Falls man das im gleichen Stil weiterverfolgt, ergibt sich folgendes Bild:
n 1 3 7 15 31 63 Kosten 2 8 24 64 160 384Und wenn man mal einfach so die Kosten durch n dividiert:
n 1 3 7 15 31 63 Kosten/n 2 3 3 4 5 6Und hier kann man dann schon vermuten dass die Kosten O(n log(n)) sind. Man kann das aber auch direkt zeigen: Die Summe der Kosten in einer "Knotenebene" beträgt jeweils konstant n+1, wie man leicht überprüfen kann, und es gibt ca. log(n) Ebenen (+/-1), wie man sich leicht überlegt. In Summe haben wir also ca. die Kosten (n+1) log(n), d.h. also O(n log(n)).
SchlechtesterFall?
Der Baum sieht dann folgendermaßen aus:
n
/
n-1
.
.
.
.
.
/
3
/
2
/
1
Hier sieht man, dass man bereits für die Partitionierung eine Laufzeit von 1+2+3+ ... + n benötigt, was O(n^2) ist, wie man sich leicht überlegt. Für die Verwaltung braucht man lediglich O(n), so dass die gesamten Kosten also O(n^2) sind.
| Speicherbedarf |
QuickSort sortiert InPlace?: das heisst, es wird kein zusätzliches Array benötigt, um die Daten zu kopieren. Deshalb hängt der zum ursprünglichen Array zusätzlich benötigte Speicherbedarf lediglich von der StackTiefe? ab.
Bei der Baum-Darstellung ist die maximale Stacktiefe genau die maximale Tiefe des Baumes, denn jedes Kind entspricht einem Aufruf von Quicksort. Für den besten Fall ist die Stacktiefe also logarithmisch, wie man oben sieht. Im schlechtesten Fall ist sie aber linear.