{"id":1015,"date":"2007-06-22T21:57:19","date_gmt":"2007-06-22T19:57:19","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/2007\/06\/sortieren-und-palimpseste.htm"},"modified":"2023-05-10T09:32:12","modified_gmt":"2023-05-10T07:32:12","slug":"sortieren-und-palimpseste","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2007\/06\/sortieren-und-palimpseste.htm","title":{"rendered":"Sortieren und Palimpseste"},"content":{"rendered":"
(2 Kommentare.<\/a>)<\/small> <\/div>\n

Im Informatikunterricht hat sich wieder der Server wegen zu gro\u00dfer Hitze verabschiedet. Vielleicht bin doch ich schuld und wir haben dem Rechner zuviel zugemutet. Es ging um Komplexit\u00e4tstheorie, Quicksort und Bubblesort im Vergleich.<\/p>\n\n\n\n

F\u00fcr Interessierte: Eine typische Aufgabe f\u00fcr Computer besteht darin, Mengen von Daten zu sortieren – eine Liste von Sch\u00fclernamen, von Zahlen, von B\u00fcchern, von verschiedenen Eintr\u00e4gen 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.<\/p>\n\n\n\n

Bubblesort<\/b> hatten die Sch\u00fcler 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\u00fcr grob gesch\u00e4tzt etwa n2<\/sup> Rechenschritte. Wenn n sehr klein ist, macht das nicht viel aus, aber bei gr\u00f6\u00dferen n kommt da schon einiges an Rechenzeit zusammen.
\nQuicksort<\/b> ist schneller. Wenn man mit Quicksort eine Liste von n Elementen sortiert, braucht man dazu grob gesch\u00e4tzt etwa n*log(n) Rechenschritte. Je gr\u00f6\u00dfer n wird, desto deutlicher schneller ist das im Vergleich zu Bubblesort.<\/p>\n\n\n\n

(Bei anderen Problemen steigt, abh\u00e4ngig von n, die erforderliche Rechenzeit noch viel, viel steiler an als bei Bubblesort. Hochinteressant, wenn man sich daf\u00fcr interessiert.)<\/p>\n\n\n\n

Quicksort habe ich den Sch\u00fclern erst einmal nur vorgef\u00fchrt, das Verstehen und Programmieren kommt dann sp\u00e4ter. Aber die Sch\u00fcler sollten mal ausrechnen, was der Unterschied zwischen n*log(n), n2<\/sup>, 2n<\/sup> und n! f\u00fcr verschiedene Werte von n ist. Und ausprobieren konnten sie das in Python auch.<\/p>\n\n\n\n

Und als dann zuviele Sch\u00fcler Listen von 100.000 Elementen mit Bubblesort sortieren wollten, da hat der Server dann gesagt, dass es ihm zu hei\u00df wird. Kann auch Zufall sein.<\/p>\n\n\n\n

— In Deutsch gab’s einen Sch\u00fclervortrag, der zu einem Teil aus dem WWW abgeschrieben war (eine dieser Referatsseiten). Sogar verh\u00e4ltnism\u00e4\u00dfig lieblos, im Skript waren selbst die Unterstreichungen im Text beibehalten worden. Ich glaube nicht mal, dass da viel b\u00f6ser Wille da war, nur Faulheit<\/strike> Zeitmangel und mangelndes Unrechtsbewusstsein. Dabei hatte schon das Originalreferat viel von Peter Nussers Buch \u00fcber den Kriminalroman abgeschrieben, ohne die Quelle zu nennen.
\nInsgesamt geht es gerade um Umberto Eco, Der Name der Rose<\/em>, da passt das ganz gut – am Montag kann ich den Sch\u00fclern gleich mal erkl\u00e4ren, was ein Palimpsest ist, und wie Texte immer auf anderen Texten beruhen.<\/p>\n\n\n\n

— Daf\u00fcr habe ich beim Korrigieren einer Schulaufgabe – Bert Brecht, Fragen eines lesenden Arbeiters<\/a> und dazu Kurt Bartsch, Adolf Hitler ganz allein<\/a> – 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\u00fcrlich). In allen Texten geht es um die Rolle, die die kleinen Leute spielen. Hat mich gefreut.<\/p>\n","protected":false},"excerpt":{"rendered":"

(2 Kommentare.) Im Informatikunterricht hat sich wieder der Server wegen zu gro\u00dfer Hitze verabschiedet. Vielleicht bin doch ich schuld und wir haben dem Rechner zuviel zugemutet. Es ging um Komplexit\u00e4tstheorie, Quicksort und Bubblesort im Vergleich. F\u00fcr Interessierte: Eine typische Aufgabe f\u00fcr Computer besteht darin, Mengen von Daten zu sortieren – eine Liste von Sch\u00fclernamen, von […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[101,25,6],"tags":[231,227],"class_list":["post-1015","post","type-post","status-publish","format-standard","hentry","category-deutsch","category-informatik","category-schule-alltag","tag-deutsch","tag-informatik"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/1015","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=1015"}],"version-history":[{"count":1,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/1015\/revisions"}],"predecessor-version":[{"id":56003,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/1015\/revisions\/56003"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=1015"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=1015"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=1015"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}