Frau Rau wies mich freundlicherweise auf Bubblesort im Volkstanz bei den Scienceblogs hin.
Wenn man dem Video zu Youtube folgt, findet man noch viele weitere getanzte Suchalgorithmen. Hier der Quicksort, nichtganz so intuitiv wie Bubblesort:
Ich denke mir natürlich sofort dabei, dass ich das Schülern zeigen muss. Wieviel man davon profitiert, wenn man die Algorithmen noch nicht kennt, weiß ich nicht. Bubblesort geht auf jeden Fall, Quicksort muss ich erst ausprobieren lassen.
Schlagwörter:
Nicht-Informatiker hier, der keine Sortier-Algorithmen kennt, aber Mathe kann: Bubblesort habe ich verstanden, scheint mir aber eeewig zu dauern. Quicksort durchschaue ich noch nicht so ganz…
Richtig, Bubblesort ist einfach zu verstehen, dauert dafür lange. Quicksort ist schneller, aber schwieriger.
Am Anfang stehen die Tänzer so:
3018725496
Man nimmt sich irgendeinen heraus (hier zum Beispiel immer den ersten von links), der kriegt einen Hut auf. Das ist in diesem Fall die 3. Der Knackpunkt nach dem ersten Durchgang ist der: alle links von der 3 sind kleiner als diese, alle rechts davon größer. Sonst ist noch nichts groß sortiert.
Das geschieht, indem man den Hutträger immer mit dem zweiten, wandernden Hutträger vergleicht. Wenn der auf der richtigen Seite vom ersten Hutträger steht, ändert sich nichts, ansonsten tauschen die beiden Hutträger Platz. Wenn sich die beiden Hüte treffen, ist die erste Runde vorbei.
Dann stehen sie so:
2013785496
Die 3 ist schon richtig, nur rechts davon und links davon muss noch sortiert werden. Und das geschieht jeweils auf die gleiche Methode wie vorhin. In der linken Hälfte wandert die 2 an ihren richtigen Platz, und nur links und rechts davon muss (eventuell) noch sortiert werden. In der rechten Hälfte wandert die 7 an ihren richtigen Platz, und nur links und rechts davon muss (eventuell) noch sortiert werden. Eventuell: bis nur noch 1 Element oder weniger da ist, dann ist da nichts mehr zu sortieren.
Die Geschwindigkeit der Algorithmen errechnet man in Abhängigkeit von der Problemgröße. Hier ist die Problemgröße einfach, nämlich äquivalent zur Anzahl der zu sortierenden Elemente, sofern die zufällig verteilt sind. Sagen wir, es sind n Elemente, dann braucht Bubblesort n*n/2 Schritte – mit der dem Informatiker eigenen Großzügigkeit rundet man das grob auf eine Größenordnung von O(n2) Schritten. Quicksort braucht dagegen meistens nur O(n*log(n)) Schritte. Wenn man Pech hat, kann es aber auch länger dauern.
Ich habe das im Unterricht gezeigt. Die Schüler kannten die Algorithmen bereits und fanden sie eigentlich nur lächerlich: „Und sowas macht man an einer Uni?“
Ich persönlich fand die Idee jetzt nicht soooo schlecht. Aber man sollte es vielleicht selbst mit den Schüler spielen/tanzen. Vielleicht ohne Musik oder mit einer anderen Musik. Den eigentlich ist es doch ganz schön, wenn man mal so etwas theoretisches wie Sortieralgorithmen am „eigenen Leib“ erfahren kann. Ich mache das auch mit rekursiven Datenstrukturen so.
Ansonsten erkläre ich halt die Sortieralgorithmen mit Kartenspielen: Ich kann die Karten nacheinander hochnehmen (InsertionSort). Oder alle auf einmal und dann Sortieren (BubbleSort, aber meistens eher SelectionSort)
Ingo
Das klingt nach Schülern, die zu cool für Albernheiten sind. Soll’s ja geben. (Demonstrieren dann bestimmt auch keine Stapel.) Aber ja, das müssten die Schüler wohl selber machen. Einen Trickfilm zu Quicksort erstellen, oder eben tanzen. Oder Schattenspiel, mit rumstehenden Leuten und kleinen schwarzgekleideten Ninjas, die sie sortieren und platzieren.
Ich hab null Ahnung von Informatik und auch nicht viel von Mathematik, trotzdem finde ich allein schon die Idee einfach genial! Toll, danke fürs Zeigen! :)
Schreibe einen Kommentar