Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- lesson:first [2023/08/24 10:33] – [Hardcore: Quicksort] mccab99
+++ lesson:first [2023/08/27 13:44] (aktuell) – Externe Bearbeitung 127.0.0.1
@@ Zeile 213: / Zeile 213: @@
 ++++Auflösung |
-Das Aufwändige für einen Rechner sind Vergleiche. Ein Tausch von Zahlen ist vergleichweise einfach - es wird intern nur ein Zeiger umgestellt. [[loesung:bubblesort|Bei Bubblesort hast du gesehen]], dass für die gegebene Zahlenreihe 40 Vergleiche notwendig sind, um den Algorithmus abzuschließen.
+Das Aufwändige für einen Rechner sind Vergleiche. Im Prinzip muss man für einen Vergleich eine Subtraktion durchführen und dann zwei Fälle unterscheiden:
+  - Ist das Ergebnis 0, dann sind die Zahlen gleich
+  - Ist das Ergebnis von 0 verschieden, dann sind die Zahlen nicht gleich
+Ein Tausch von Zahlen ist dagegen vergleichweise einfach - es wird intern nur ein Zeiger umgestellt. [[loesung:bubblesort|Bei Bubblesort hast du gesehen]], dass für die gegebene Zahlenreihe 40 Vergleiche notwendig sind, um den Algorithmus abzuschließen.
 Quicksort ist etwas schwieriger syntaktisch aufzuschreiben, aber wir schauen mal.
@@ Zeile 225: / Zeile 229: @@
 4 __1__ __8__ 2 __5__ __9__ 7 **6**\\
 4 1 //5// 2 //8// 9 7 **6**( 5 und 8 wurden getauscht)\\
-4 1 5 2 //6// 9 7 __8__ ( 6 und 8 wurden getauscht, Vergleich war unnötig)\\
+[ 3 4 1 5 2 ] //6// [ 9 7 //8// ] ( 6 und 8 wurden getauscht, Vergleich war unnötig, die 6 muss die kleinste Zahl sein)\\
+Wir haben in diesem ersten Durchgang insgesamt 7x Zahlen miteinander verglichen. Die 6 liegt jetzt schon auf ihrer Endposition.
+Wir werden weiterhin ...
+  * für das Pivot-Element **2** 3x vergleichen müssen
+  * für das Pivot-Element **4** 2x vergleichen müssen
+  * für das Pivot-Element **8** 1x vergleichen müssen
+Wir kommen also mit 13 Vergleichen aus. Quicksort ist um Größenordnungen effizienter als Bubblesort. Bei einer bereits sortierten Liste (Best-Case) bringt Quicksort keinen Nachteil gegenüber Bubblesort.
 ++++
 ===== Ja, und was ist jetzt mit Informatik? =====