Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:37] – [Average Case und Worst Case bei Quicksort] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 19:00] – [Best Case/Average Case] sbel
@@ Zeile 100: / Zeile 100: @@
 Wie oben bereits angedeutet, ist es besonders ungünstig, wenn die Partitionireung bei Quicksort immer so ausfällt, dass das größte zu sortierende "Unterarray" lediglich ein Element weniger hat, als das Array im Rekursionsschritt zuvor. Besonders leicht kann man sich das klar machen, wenn man ein Array betrachtet, das bereits sortiert ist und stets das erste Array-Element als Pivotelement wählt:
-{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray04.drawio.png|}}
+{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray04.drawio.png  |}}
+==== Worst Case ====
+Wenn man den Sortiervorgang nachvollzieht, wenn man jeweils das erste Element des Arrays mit den größeren Elementen als Pivotelement wählt, sieht das so aus:
+{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray05.drawio.png |}}
+Auf jeder Ebene des des Call Stacks muss man alle Elemente betrachten um zu partitionieren - unabhängig vom gewählten Pivotelement. Das bedeutet, die Bearbeitung jeder Ebene des Call Stacks benötigt den Aufwand O(n).
+Im **Worst Case** haben wir also n Ebenen, die jeweils mit dem Aufwand O(n) bearbeitet werden müssen - im schlechtesten Fall hat Quicksort also die Laufzeit O(n*n) also O(n<sup>2</sup>).
+==== Best Case/Average Case ====
+Wir wählen bei unserem sortierten Beispielarray jetzt immer das mittlere Element als Privotelement und schauen, was dann passiert:
+{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray06.drawio.png |}}
+Die Größe des Call Stacks ist hier nur 4 -- oder allgemein (analog zur binären Suche) von der Ordnung ''log n''. Auch hier gilt natürlich, dass wir auf jeder Ebene des des Call Stacks  alle Elemente betrachten muss um zu partitionieren - unabhängig vom gewählten Pivotelement, also auch hier: Die Bearbeitung jeder Ebene des Call Stacks benötigt den Aufwand O(n).
+Da es aber nur log n Ebenen gibt, ist der Aufwand von Quicksort im Best Case O(n * log n) also O(n log n)