Zuletzt angesehen:

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
lesson:first [2023/08/24 10:40] – [Hardcore: Quicksort] mccab99lesson:first [2023/08/27 13:44] (aktuell) – Externe Bearbeitung 127.0.0.1
Zeile 213: Zeile 213:
 ++++Auflösung | ++++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. Quicksort ist etwas schwieriger syntaktisch aufzuschreiben, aber wir schauen mal.
Zeile 225: Zeile 229:
 3 4 __1__ __8__ 2 __5__ __9__ 7 **6**\\ 3 4 __1__ __8__ 2 __5__ __9__ 7 **6**\\
 3 4 1 //5// 2 //8// 9 7 **6**( 5 und 8 wurden getauscht)\\ 3 4 1 //5// 2 //8// 9 7 **6**( 5 und 8 wurden getauscht)\\
-3 4 1 5 2 //6// 9 7 __8__ ( 6 und 8 wurden getauscht, Vergleich war unnötig, die muss die kleinste Zahl sein)\\+[ 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 haben in diesem ersten Durchgang insgesamt 7x Zahlen miteinander verglichen. Die 6 liegt jetzt schon auf ihrer Endposition. 
Zeile 234: Zeile 238:
   * für das Pivot-Element **8** 1x vergleichen müssen   * für das Pivot-Element **8** 1x vergleichen müssen
  
-Wir kommen also mit 13 Vergleichen aus.  +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? ===== ===== Ja, und was ist jetzt mit Informatik? =====
Nach oben