Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
| lesson:first [2023/08/13 07:18] – [Eine formale Sortierstrategie] mccab99 | lesson:first [2023/08/27 13:44] (aktuell) – Externe Bearbeitung 127.0.0.1 | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| - | ===== Was ist Informatik eigentlich? | + | ===== Über Algorithmen |
| <WRAP center round info 95%> | <WRAP center round info 95%> | ||
| Zeile 96: | Zeile 96: | ||
| # i ist ein Zähler und erhöht sich bei jedem Durchlauf um 1 | # i ist ein Zähler und erhöht sich bei jedem Durchlauf um 1 | ||
| # die letzte Zahl lassen wir beim Vergleich aus | # die letzte Zahl lassen wir beim Vergleich aus | ||
| - | # wir gehen nur bis zur vorletzten (n-1) | + | # wir gehen nur bis zur vorletzten (n-1) |
| # das sind praktisch die " | # das sind praktisch die " | ||
| for j in range(0, n-i-1): | for j in range(0, n-i-1): | ||
| Zeile 199: | Zeile 199: | ||
| - Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf. | - Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf. | ||
| - Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn. | - Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn. | ||
| + | - [[loesung: | ||
| </ | </ | ||
| Zeile 210: | Zeile 211: | ||
| * Was sagt dein Gefühl über die Anzahl der Vergleiche, die für die Sortierung benötigt werden, im Unterschied zu Bubblesort? | * Was sagt dein Gefühl über die Anzahl der Vergleiche, die für die Sortierung benötigt werden, im Unterschied zu Bubblesort? | ||
| + | ++++Auflösung | | ||
| + | |||
| + | 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, | ||
| + | |||
| + | Ein Tausch von Zahlen ist dagegen vergleichweise einfach - es wird intern nur ein Zeiger umgestellt. [[loesung: | ||
| + | |||
| + | Quicksort ist etwas schwieriger syntaktisch aufzuschreiben, | ||
| + | * das aktuelle Pivotelement ist **fett** formatiert. | ||
| + | * eine unterstrichene Zahl ist ein Zahl, die mit dem Pivot-Element verglichen wurde | ||
| + | * die Anzahl der unterstrichenen Zahlen ist also die Gesamtzahl der Vergleiche im aktuellen Durchgang | ||
| + | |||
| + | **Durchgang 1 - 6 ist Pivotelement: | ||
| + | __3__ __7__ 1 8 2 5 9 __4__ **6**\\ | ||
| + | 3 //4// 1 8 2 5 9 //7// **6** ( 4 und 7 wurden getauscht)\\ | ||
| + | 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 ] //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? ===== | ===== Ja, und was ist jetzt mit Informatik? ===== | ||
| Für eine ganz präzise Formulierung ist es jetzt noch zu früh, aber du hast unglaublich wichtige Grundprinzipien eines // | Für eine ganz präzise Formulierung ist es jetzt noch zu früh, aber du hast unglaublich wichtige Grundprinzipien eines // | ||