Sortieren und Palimpseste

Im Informatikunterricht hat sich wieder der Server wegen zu großer Hitze verabschiedet. Vielleicht bin doch ich schuld und wir haben dem Rechner zuviel zugemutet. Es ging um Komplexitätstheorie, Quicksort und Bubblesort im Vergleich.

Für Interessierte: Eine typische Aufgabe für Computer besteht darin, Mengen von Daten zu sortieren – eine Liste von Schülernamen, von Zahlen, von Büchern, von verschiedenen Einträgen in einer Datenbank, von Bits und Bytes jeder Art. Im Laufe der Zeit sind dazu verschiedene Sortieralgorithmen erdacht worden, so wie jeder Lehrer auch seine eigene Methode hat, Schulaufgaben zu sortieren. Wie bei allen Algorithmen gibt es dabei bessere und schlechtere.

Bubblesort hatten die Schüler schon selber in zwei Varianten untersucht. Diese Sortiermethode ist leicht zu verstehen und zu programmieren, aber sie ist relativ langsam: wenn man n Elemente sortiert, braucht man dafür grob geschätzt etwa n2 Rechenschritte. Wenn n sehr klein ist, macht das nicht viel aus, aber bei größeren n kommt da schon einiges an Rechenzeit zusammen.
Quicksort ist schneller. Wenn man mit Quicksort eine Liste von n Elementen sortiert, braucht man dazu grob geschätzt etwa n*log(n) Rechenschritte. Je größer n wird, desto deutlicher schneller ist das im Vergleich zu Bubblesort.

(Bei anderen Problemen steigt, abhängig von n, die erforderliche Rechenzeit noch viel, viel steiler an als bei Bubblesort. Hochinteressant, wenn man sich dafür interessiert.)

Quicksort habe ich den Schülern erst einmal nur vorgeführt, das Verstehen und Programmieren kommt dann später. Aber die Schüler sollten mal ausrechnen, was der Unterschied zwischen n*log(n), n2, 2n und n! für verschiedene Werte von n ist. Und ausprobieren konnten sie das in Python auch.

Und als dann zuviele Schüler Listen von 100.000 Elementen mit Bubblesort sortieren wollten, da hat der Server dann gesagt, dass es ihm zu heiß wird. Kann auch Zufall sein.

– In Deutsch gab’s einen Schülervortrag, der zu einem Teil aus dem WWW abgeschrieben war (eine dieser Referatsseiten). Sogar verhältnismäßig lieblos, im Skript waren selbst die Unterstreichungen im Text beibehalten worden. Ich glaube nicht mal, dass da viel böser Wille da war, nur Faulheit Zeitmangel und mangelndes Unrechtsbewusstsein. Dabei hatte schon das Originalreferat viel von Peter Nussers Buch über den Kriminalroman abgeschrieben, ohne die Quelle zu nennen.
Insgesamt geht es gerade um Umberto Eco, Der Name der Rose, da passt das ganz gut – am Montag kann ich den Schülern gleich mal erklären, was ein Palimpsest ist, und wie Texte immer auf anderen Texten beruhen.

– Dafür habe ich beim Korrigieren einer Schulaufgabe – Bert Brecht, Fragen eines lesenden Arbeiters und dazu Kurt Bartsch, Adolf Hitler ganz allein – eine Arbeit gelesen, die diese beiden Texte gar nicht ungeschickt mit Douglas Adams verglich: Mit dem Planeten, der die ganzen Telefondesinfizierer und so weiter wegschickte, nur um dann an einem Virus zugrunde zu gehen (von einem nicht desinfizierten Telefon, natürlich). In allen Texten geht es um die Rolle, die die kleinen Leute spielen. Hat mich gefreut.

2 Antworten auf „Sortieren und Palimpseste“

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.