Lieber Erdling,
wie geht es Dir heute? Rudi und ich haben gerade unsere Primzahlensammlung sortiert. Die ist Rudi beim Socken Aufräumen aus Versehen heruntergefallen. Mann, hat er da geflucht. Das ist immer eine Heidenarbeit, die Primzahlen wieder der Größe nach zu ordnen. Gut, dass unser Nachbar, Herr Merge, gerade auf einen Kakao vorbeikam. Der hat uns gezeigt, wie wir die Zahlen viel schneller sortieren können. Wir haben nämlich bisher immer so sortiert:
Zuerst haben wir unter unseren Zahlen die kleinste Zahl herausgesucht. Dafür haben wir irgendeine der Zahlen in die Hand genommen und haben diese dann nach und nach mit den anderen Zahlen verglichen. Sobald wir eine kleinere Zahl gefunden hatten, haben wir diese mit der Zahl in der Hand ausgetauscht und haben sie weiter mit den restlichen Zahlen verglichen. Sobald wir dann alle Zahlen angeschaut hatten, hatten wir offenbar die kleinste all unserer Zahlen in der Hand. Diese haben wir dann ins Album einsortiert und haben mit den restlichen Zahlen von vorne angefangen. Wir haben wieder die kleinste Zahl unter den verbliebenen Zahlen gesucht und diese dann ins Album einsortiert. Und so weiter.
Aber Herr Merge meinte, so würden wir ja im schlimmsten Fall jede Zahl mit jeder anderen Zahl vergleichen! Das wären ja viel zu viele Vergleiche! Was für eine Arbeit! Das ginge doch viel besser. Und verblüffenderweise erzählte er uns wieder etwas vom Teilen! Ähnlich wie beim Zahlen-Raten. Und dann hat er uns das mal an einem Beispiel erklärt. Er hat sich dafür einfach mal die folgenden Primzahlen aus unserer Sammlung genommen, hat sie durchgemischt und auf den Tisch gelegt:
Na super! Jetzt sind die ja vollkommen durcheinander! „Ganz ruhig!“, rief da Herr Merge, als er unsere entsetzten Gesicher sah. Und dann verriet er uns seinen Trick. Ich kann mich nicht mehr an seine genauen Worte erinnern, aber der Sortiertrick geht ungefähr so:
Teile die Zahlen in zwei etwa gleich große Gruppen:
Ordne beide (nur halb so große) Zahlengruppen:
Sortiere die vorsortierten Zahlengruppen zusammen:
Rudi hat sich wie ein kleiner Schneedrache gefreut, dass seine Primzahlen wieder schön geordnet waren. Dann aber hat er gestutzt und gefragt: „Und was ist jetzt an dieser Sortiermethode besser als vorher?“
Ja, das war definitiv eine gute Frage! Die Antwort von Herrn Merge ließ nicht lange auf sich warten. „Naja, zum einen ist es viel einfacher, zwei halb so große Zahlenhaufen zu sortieren als den großen Zahlenhaufen. Das kennst Du bestimmt vom Puzzeln, oder?! Zum anderen ist es total einfach, zwei schon sortierte halbe Haufen zu einem sortierten ganzen Haufen zusammenzufügen. Die jeweils kleinsten Zahlen stehen immer links. Die kleinere von beiden ist die insgesamt kleinste Zahl und diese sortieren wir ins Zahlenalbum ein und machen mit den restlichen zwei kleinen Haufen weiter.“
Schauen wir uns das mal kurz an:
Die kleinsten Zahlen jeweils sind 2 und 3. Wir nehmen also die 2 aus dem linken Haufen weg und sortieren diese ins Zahlenalbum:
Die kleinsten Zahlen sind jetzt 7 und 3. Wir nehmen also die 3 aus dem rechten Haufen weg und sortieren diese ins Zahlenalbum:
Und so geht es weiter, bis unser Album schön geordnet ist:
Und wieder strahlt Rudi wie ein Schneedrache bei einer Schneeballschlacht. „So! Und nun noch ein letzter Trick!“, posaunt da Herr Merge. „Anstatt die beiden Haufen mit jeweils 4 Zahlen wieder so langsam zu ordnen wie ihr zwei Sortierunkundigen, wiederholen wir den gleichen Teilungstrick nochmal! Jeder Haufen mit 4 Zahlen wird in zwei Haufen mit zwei Zahlen geteilt. Dann werden diese 4 Minihaufen mit je 2 Zahlen sortiert (das ist einfach!) und zu zwei sortieren Haufen mit 4 Zahlen zusammengefügt. Diese werden dann wie oben zu einem schönen Haufen aus 8 Zahlen zusammengefügt, den wir fein säuberlich im Album verstauen.“
Rudi und ich schauen uns halb verwirrt, halb verblüfft an. Wie sieht das denn bei unserem kleinen Beispiel aus?
Wir beginnen mit unserem unsortierten großen Haufen:
Wir teilen die Zahlen in zwei etwa gleich große Haufen:
Und nun teilen wir die beiden Zahlenhaufen jeweils wieder in zwei etwa gleich große Haufen:
Die 4 Minihaufen lassen sich ganz einfach sortieren:
Jetzt fügen wir je zwei sortierte Minihaufen wieder zusammen:
Schließlich fügen wir wieder die mittelgroßen vorsortierten Zahlenhaufen zusammen und fertig ist unser schönes Zahlenalbum:
Hey, das ist ja richtig cool! Wenn wir gaaanz viele Zahlen zu sortieren haben, dann haben wir nach ein paar Mal teilen zwar ganz viele Zahlenhaufen, aber die sind (wie bei unserem Partykuchen) nach ein paar Mal halbieren auch alle recht klein und lassen sich leicht sortieren. Und das Gute ist, wenn Rudi und ich gerade ein paar Freunde zu Besuch haben, dann können wir uns die Arbeit teilen! Jeder darf ein paar kleine Haufen sortieren, die wir dann nach und nach wieder zum gesamten Album zusammenfügen. Super! Dann geht es ja noch schneller! Ich glaub, ich schicke gleich mal eine Einladung für eine Sortierparty raus! Da können wir endlich mal Rudis Quadratzahlenalbum in Ordnung bringen. Vielleicht magst Du ja auch mitmachen?!
Liebe Grüße
Deine 3,7
PS: Zahlen möglichst schnell zu sortieren ist nur ein Beispiel der algorithmischen Mathematik. Ein Algorithmus ist eine Art mathematisches Rezept zum Lösen eines Problems ähnlich wie ein Rezept zum Kochen oder Backen. Mit Hilfe des Algorithmus kochen oder backen wir uns also quasi eine Lösung für ein mathematisches Problem. Du kennst sicher schon ein paar ganz einfache mathematische Rezepte: Formeln. Aber die sind meist recht langweilig, stimmt’s?! Obiges Rezept von Herrn Merge ist doch viel aufregender, oder?! Man nennt diesen Algorithmus bzw. dieses Rezept ihm zu Ehren übrigens Merge-Sort. Nein, das war nur ein Scherz von ihm. „Merge“ steht nicht für Herrn Merge, sondern kommt aus dem Englischen: to merge = zusammenfügen. Aber pssst! Das müssen wir ja nicht jedem gleich auf die Nase binden!
Es gibt noch viele andere Probleme im Alltag, wo solche mathematischen Algorithmen zum Einsatz kommen. Deine Eltern haben beim Autofahren bestimmt schon mal ein Navigationsgerät, kurz Navi, benutzt, um einen möglichst kurzen oder schnellen Weg von A nach B zu finden, oder?! Doch wie findet das Navi solch einen Weg auf einer riesigen Straßenkarte möglichst schnell? Oder wie findet man eine möglichst stabile Brückenkonstruktion, die viel Gewicht aushält? Oder wie erstellt man einen Stundenplan, bei dem die Lehrer am glücklichsten sind, weil ihre zeitlichen Wünsche vielleicht nicht alle, aber doch zumindest fast alle, erfüllt sind? Mit solchen und ähnlichen spannenden Fragen beschäftigen sich viele mathematische Optimierer an Universitäten und in Firmen. Vielleicht Du ja in ein paar Jahren auch, wenn Dir so etwas Spaß macht.
