Quicksort: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Thomas (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 100: | Zeile 100: | ||
<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math> | <math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math> | ||
Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>. | Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>. | ||
== Best Case == | |||
[[Datei:Verzweigungsbaum Quicksort symetrisch.png|mini]] | |||
Der beste Fall von Quicksort liegt vor, wenn die Partitionen so gleichmäßig wie möglich aufgeteilt werden: Ihre Größen sind entweder gleich oder weichen nur um ein Element voneinander ab. | |||
[[Datei:SubArrays symetrisch Quicksort.png|mini]] | |||
Der erstere Fall tritt auf, wenn das Subarray eine ungerade Anzahl von Elementen hat und der Drehpunkt nach der Partitionierung genau in der Mitte liegt und jede Partition <math>(n-1) / 2 </math> hat. Der letztere Fall tritt auf, wenn das Subarray eine gerade Anzahl n von Elementen hat und eine Partition n / 2 hat, während die andere n-1 / 2 hat. In beiden Fällen hat jede Partition höchstens n / 2 Elemente. | |||
Wird die Anzahl der zu sortierenden Elemente n verdoppelt, muss nur eine neue Ebene mit Teilarrays erzeugt werden. Dieses Wachstum lässt sich mit <math>log(n) </math> beschreiben. | |||
{| class="wikitable" style="text-align:center" | |||
|- | |||
! Zu sortierende Elemente n | |||
| style="color:green" | 4 | |||
| style="color:green" | 8 | |||
| style="color:green" | 16 | |||
| style="color:green" | 32 | |||
|- | |||
! Zu sortierende Elemente n | |||
| <math>\color{green}{2^2}</math> | |||
| <math>\color{green}{2^3}</math> | |||
| <math>\color{green}{2^4}</math> | |||
| <math>\color{green}{2^5}</math> | |||
|- | |||
! Anzahl Ebene log(n) | |||
| style="color:red" | 2 | |||
| style="color:red" | 3 | |||
| style="color:red" | 4 | |||
| style="color:red" | 5 | |||
|} | |||
In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>. | |||