Quicksort: Unterschied zwischen den Versionen

(4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)

Zeile 90:

}

</syntaxhighlight>

== Laufzeitanalyse ==

=== Worst-Case ===

[[Datei:Baum N-Ebenen.png|mini]]

Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.

In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1 Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).

Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:

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>.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

[[Kategorie:FI_I_TP2]]

@@ Zeile 90: / Zeile 90: @@
     }
 </syntaxhighlight>
+== Laufzeitanalyse ==
+=== Worst-Case ===
+[[Datei:Baum N-Ebenen.png|mini]]
+Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.
+In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1  Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).
+Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
+<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>.
+== 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>.
+[[Kategorie:Programmierung]]
+[[Kategorie:AHR_I_Informatik_LK]]
+[[Kategorie:FI_I_TP2]]