WEBVTT NOTE Podcast: Eigenraum Episode: EIG004 Puzzleteile sortieren Publishing Date: 2022-09-21T13:16:23+02:00 Podcast URL: https://eigenpod.de Episode URL: https://eigenpod.de/eig004-puzzleteile-sortieren/ 00:00:00.000 --> 00:00:06.360 Ja, hallo zusammen. Hier ist der Eigenraum zum vierten Mal. Freue mich, dass ihr da seid. 00:00:06.360 --> 00:00:10.960 Ich bin Thomas, ich bin Mathematiker und ich frage mich schon so ein bisschen, wie ihr 00:00:10.960 --> 00:00:17.960 das hier hört. Es gibt diesen Podcast jetzt auf Spotify und sogar auf YouTube. Ich bin 00:00:17.960 --> 00:00:23.560 da ganz plump und will meine Reichweite vergrößern und da habe ich neulich festgestellt, dass 00:00:23.560 --> 00:00:28.080 YouTube die zweitgrößte Suchmaschine der Welt ist. Ihr könnt euch denken, was die größte 00:00:28.560 --> 00:00:34.120 Suchmaschine der Welt ist. Und es gibt tatsächlich Leute, die Podcasts auf YouTube finden. Das 00:00:34.120 --> 00:00:38.000 ist natürlich nicht die beste Art und Weise, Podcasts zu hören. Wer mich kennt oder viel 00:00:38.000 --> 00:00:41.480 Podcasts hört, der weiß vielleicht, dass die beste Art und Weise eine Podcast-App ist. 00:00:41.480 --> 00:00:46.640 Und das würde ich euch auch empfehlen, eine Podcast-App zu verwenden. Bei vielen Handys 00:00:46.640 --> 00:00:51.640 zum Beispiel ist schon eine dabei. Und es gibt auch in den diversen App-Stores noch 00:00:51.640 --> 00:00:57.920 bessere. Ich selbst benutze Overcast, was eine App für iOS ist. Und wenn ihr die benutzt, 00:00:57.920 --> 00:01:03.200 dann merkt ihr sich, was ihr schon gehört habt und schlägt euch auch immer neue Folgen 00:01:03.200 --> 00:01:08.640 vor, wenn sie dann erscheinen. Und es ist alles ziemlich komfortabel. Also, wenn ihr 00:01:08.640 --> 00:01:12.160 diesen Podcast auf YouTube entdeckt habt, dann freue ich mich sehr, dass ihr jetzt auch 00:01:12.160 --> 00:01:19.160 dabei seid und würde mich noch mehr freuen, wenn ich euch dann im RSS-Feed auf einer Podcast-App 00:01:19.440 --> 00:01:23.840 begrüßen könnte. Da sucht ihr dann einfach nach Eigenraum und zum Beispiel könnt ihr 00:01:23.840 --> 00:01:29.120 dann die Show Notes direkt sehen in den meisten Apps oder sogar Kapitelmarken nutzen. 00:01:29.120 --> 00:01:36.120 So, das aber nur zur Vorrede. Nachdem es letzte Woche ja etwas länger und fast schon 00:01:36.120 --> 00:01:40.680 ein bisschen politisch war, möchte ich euch diese Woche eine Geschichte über Ordnung 00:01:40.680 --> 00:01:44.880 erzählen. Und die wird hoffentlich auch nicht so lang. Ich habe übrigens neulich gelernt, 00:01:44.880 --> 00:01:50.040 dass es sowas wie pränumerische Mathematik gibt. Pränumerische Mathematik ist sozusagen 00:01:50.120 --> 00:01:55.960 der Matheunterricht in der Kita. Ich denke eigentlich, dass Zahlen eine ziemlich primäre 00:01:55.960 --> 00:02:01.000 Erfahrung sind. Hatten wir ja schon in der früheren Folge dieses Zählen, wenn man nicht 00:02:01.000 --> 00:02:05.160 so viele Zahlen kennt. Ich habe ein Gummibärchen, ich habe zwei Gummibärchen, ich habe viele 00:02:05.160 --> 00:02:10.520 Gummibärchen. Ihr erinnert euch vielleicht. Aber naja, am Anfang fängt man in der Mathematik 00:02:10.520 --> 00:02:14.720 irgendwie auch an mit Sortieren. Ich glaube, pränumerische Mathematik, da geht es um so 00:02:14.720 --> 00:02:21.720 Farben und Formen. Und das scheint der Matheunterricht in der Kita, ich kenne mich da nicht so aus. 00:02:21.720 --> 00:02:25.600 Ich habe mal in der Kita Matheunterricht gegeben, aber da ging es auch wirklich um Gummibärchen 00:02:25.600 --> 00:02:31.360 und Teilbarkeit. Aber es geht auch pränumerische Mathematik. Naja, also da muss man irgendwie 00:02:31.360 --> 00:02:35.480 so Sachen sortieren. Sortieren erinnert mich an Puzzle, ich mache gern Puzzle. Puzzle kennt 00:02:35.480 --> 00:02:40.600 ihr ja, das ist so ein kaputtes Bild. Man kauft von Ravensburger ein kaputtes Bild und 00:02:40.600 --> 00:02:44.280 obwohl man es gerade gekauft hat, ist es schon kaputt. Und da muss man es reparieren, obwohl 00:02:44.280 --> 00:02:49.200 man es selbst nicht kaputt gemacht hat. Und da gibt es ja so verschiedene Strategien. 00:02:49.200 --> 00:02:53.840 Die meisten Leute, die sortieren erstmal den Rand raus. Das mache ich auch. Es gibt auch 00:02:53.840 --> 00:02:57.700 total Sinn, denn wenn man irgendwie die Randteile erstmal hat, erstmal sind die Randteile leicht 00:02:57.700 --> 00:03:02.240 zu finden. Und wenn man die hat, dann kann man erstmal so eine Art eindimensionales Puzzle 00:03:02.240 --> 00:03:07.320 lösen. Das macht einfach die Randteile in die richtige Reihenfolge. Und wenn man dann 00:03:07.320 --> 00:03:11.120 noch ein Bild hat, ist es meistens leicht, die irgendwie zuzuordnen, in welcher Reihenfolge 00:03:11.120 --> 00:03:16.760 die kommen. Puzzle mit Bildern sind beliebt. Es gibt aber auch Puzzle ohne Bilder. Neulich 00:03:16.760 --> 00:03:20.880 hatte ich so einen Puzzle, das hieß Krypt. Ich sage es mal nicht von welcher Firma, aber 00:03:20.880 --> 00:03:25.400 ihr findet das schon. Das hatte den Slogan für Dauerpuzzler, Durchhalter und Dranbleiber 00:03:25.400 --> 00:03:28.840 und alle, die nie aufgeben. Und der Witz an dem Puzzle war, dass es komplett einfarbig 00:03:28.840 --> 00:03:33.960 war. Dafür hatten aber die Teile in ganz interessante Formen. Da gab es so verschiedene 00:03:33.960 --> 00:03:40.300 Bereiche in dem Puzzle. Also dass in einem Bereich die Teile immer eine bestimmte Eigenschaft 00:03:40.300 --> 00:03:44.660 hatten oder in bestimmte Richtungen ausgerichtet waren. Aber die waren eben alle schwarz in 00:03:44.660 --> 00:03:49.300 meinem Fall. Aber was für eine Mathematik steckt eigentlich jetzt so im Puzzlen? Sagen 00:03:49.300 --> 00:03:51.980 wir mal, man hat jetzt so einen Puzzle vor sich und vielleicht hat man jetzt auch schon 00:03:51.980 --> 00:03:57.860 den Rand gepuzzelt und will jetzt irgendwie effizient vorwärts kommen. Also eigentlich 00:03:57.860 --> 00:04:00.620 will man sich ja die Zeit vertreiben mit so einem Puzzle, aber man will ja doch effizient 00:04:00.620 --> 00:04:04.820 vorwärts kommen. Das ist wie so ein kleiner Widerspruch. Aber also sagen wir mal, man 00:04:04.820 --> 00:04:09.380 hat jetzt so einen 1000-Teile-Puzzle vor sich. Übrigens wusste der, dass die meisten Puzzle 00:04:09.380 --> 00:04:14.060 nicht die richtige Anzahl Teile auf der Schachtel stehen haben. Denn wenn man jetzt mal 1000 00:04:14.060 --> 00:04:19.660 nimmt, dann hat es ja gar nicht so viele Teile. Versuchen wir mal die Teile von 1000 kurz 00:04:19.660 --> 00:04:25.260 zu bestimmen. Ja, ich habe jetzt mal kurz 4 für euch gemacht. Also 1000 ist ganz einfach, 00:04:25.260 --> 00:04:30.500 das ist nämlich einfach 2 hoch 3 mal 5 hoch 3. Das ist die Primfaktor zur Legung. Also 00:04:30.500 --> 00:04:39.340 8 mal 5 mal 5 mal 5. 5 mal 5 ist 25 und 5 mal 25 ist 125 und 125 mal 8 ist 1000. Also 00:04:39.340 --> 00:04:44.180 es stecken nur 2 in und 5 drin. Das heißt also, wenn man den Rand jetzt könnte man es zum 00:04:44.180 --> 00:04:50.300 Beispiel in 50 mal 20 oder so. Also ausgehend davon, dass alle Teile zumindest auf so einem 00:04:50.300 --> 00:04:54.740 rechteckigen Muster basiert. Also das ist ein Produkt von zwei Zahlen, ist die Anzahl Teile. 00:04:54.740 --> 00:04:58.900 Und dann klappt das meistens nicht. Dann sind es irgendwie 1008 Teile oder irgendwie eine andere 00:04:58.900 --> 00:05:05.460 Zahl. Obwohl 1000 ja auch 40 mal 25 ist, was ein schönes rechtwinkliges Format ergeben könnte. 00:05:05.460 --> 00:05:11.700 Also es ist vielleicht bei tausender Puzzlen okay, aber hunderte Puzzle stellen einen da schon von 00:05:11.700 --> 00:05:17.580 eine schwierigere Herausforderung. Denn ein 2 mal 50 Puzzle ist vielleicht nicht so interessant. 00:05:17.580 --> 00:05:22.740 Oder irgendwie jedenfalls anders. Aber das nur am Rande. Also zurück zu unserem Puzzle sagen wir, 00:05:22.740 --> 00:05:28.100 wir haben die 1000 Teile vor uns oder 1008. Und die meisten Leute fangen jetzt irgendwie an zu 00:05:28.100 --> 00:05:34.060 sortieren. Ich mache das auch so. Und die Frage, die ich mir gestellt habe ist, warum funktioniert 00:05:34.060 --> 00:05:39.880 das? Warum ist sortieren bei einem Puzzle so eine effiziente Methode um vorwärts zu kommen? Und das 00:05:39.880 --> 00:05:46.780 hat damit zu tun, dass es einfacher ist, zwei 500 Teile Puzzle zu lösen als 1000er Teil. Das kann 00:05:46.780 --> 00:05:51.540 man sich auch leicht überlegen mit so einem Modell. Also mal so eine Überschlagsrechnung oder so ein 00:05:51.540 --> 00:05:56.300 kleines Denkmodell. Sagen wir mal, man geht irgendwie so vor, dass man sich an irgendeiner Stelle von dem 00:05:56.300 --> 00:06:00.020 Puzzle befindet und jetzt das passende Teil dazu sucht. Also ich habe mir genau überlegt, ich will 00:06:00.020 --> 00:06:03.580 jetzt hier sagen wir den Rand habe ich fertig und jetzt bin ich links oben in der Ecke und suche genau 00:06:03.580 --> 00:06:07.500 das Teil, was dahin kommt. Da könnte ich natürlich erst mal so ganz doof vorgehen. Ich probiere 00:06:07.500 --> 00:06:11.980 einfach drein nach alle Teile, die ich noch über habe durch. Und meine Approximation ist, dass man 00:06:11.980 --> 00:06:16.180 das jetzt so macht. Also ohne sortieren gucke ich vielleicht auch die Bilder gar nicht an. Ich 00:06:16.180 --> 00:06:20.500 probiere einfach die Teile der Reihe nach durch. Jedes Teil durchzuprobieren dauert irgendwie eine 00:06:20.500 --> 00:06:27.340 bestimmte Zeit. Die nehme ich jetzt auch mal an für alle Teile gleich. Und das ist jetzt Zufall, 00:06:27.340 --> 00:06:32.700 kann ich Glück haben oder Pech haben. Aber über die Anzahl Teile ermittelt sich das alles raus. Ich 00:06:32.700 --> 00:06:40.420 brauche irgendwie eine konstante Zeit mal die Anzahl der Teile, die noch da liegen. Sagen wir so 00:06:40.420 --> 00:06:43.980 im Mittel bin ich immer nach der Hälfte, finde ich das richtige Teil. Für jedes Teil brauche ich drei 00:06:43.980 --> 00:06:48.220 Sekunden. Also brauche ich irgendwie drei Sekunden mal Hälfte der Anzahl der Teile und drei Sekunden 00:06:48.220 --> 00:06:54.420 mal Hälfte ist irgendwie dieser Proportionalitätsfaktor. Und mal hat man Glück, mal hat man weniger Glück, 00:06:54.420 --> 00:06:59.580 aber das mittelt sich eben draus, wenn man es so oft macht. Und man merkt ja auch, dass man dann am 00:06:59.580 --> 00:07:03.500 Ende immer schneller wird, weil die Teile, die man noch über hat, unter denen man sucht, eben 00:07:03.500 --> 00:07:08.060 weniger werden. Also kann man das approximieren, indem man diese ganzen Zeiten alle zusammen addiert. 00:07:08.060 --> 00:07:13.700 Und sagen wir mal, mein Puzzle hat N Teile, dann habe ich jetzt beim ersten muss ich aus diesen 00:07:13.700 --> 00:07:19.380 N Teilen die linke obere Ecke suchen und dann muss ich aus den N-1 verbleibenden Teilen das nächste 00:07:19.380 --> 00:07:24.780 suchen. Und jetzt mal habe ich diese Konstante, also kann ich die Konstante ausklammern und summiere 00:07:24.780 --> 00:07:30.780 einfach N plus N minus eins plus N minus zwei und so geht es immer weiter bis eins. Also summiere 00:07:30.780 --> 00:07:37.460 ich einfach die Zahlen von N bis eins absteigend auf, hat man also die Summe der ersten N Zahlen 00:07:37.460 --> 00:07:44.340 mal diesen Faktor, diesen konstanten Faktor. Und das ist eben dieser kleine Gauss, das soll 00:07:44.340 --> 00:07:50.500 angeblich der Karl Friedrich Gauss, der berühmte Mathematiker, als Schüler berechnet haben. Und 00:07:50.500 --> 00:07:56.220 da kommt raus N mal N plus eins halbe, wenn man die ersten N Zahlen aufsummiert. Also hat er so 00:07:56.220 --> 00:08:00.580 gemacht, er nimmt die N, also die, sagen wir mal, er will die Zahlen von eins bis hundert addieren, 00:08:00.580 --> 00:08:04.180 nimmt er die hundert mit der eins zusammen, kriegt er hundert eins, nimmt er die 99 mit der zwei 00:08:04.180 --> 00:08:08.020 zusammen, kriegt er auch wieder hundert eins, kriegt er die 98 mit der drei zusammen, auch wieder hundert 00:08:08.020 --> 00:08:18.700 eins. Also kriegt er N halbe mal N plus eins, wenn das genau das N gerade war oder eben im anderen 00:08:18.700 --> 00:08:26.140 Fall, fügt man einfach noch eine Null hinzu und kriegt dann N plus eins halbe Paare mal, 00:08:26.140 --> 00:08:34.860 jedes Paar ergibt N, ergibt auch wieder die gleiche Zahl. So rechnen wir das eben aus. Und wie diese 00:08:34.860 --> 00:08:39.980 Form jetzt genau aussieht, interessiert mich gar nicht so genau, sondern nur, dass N mal N plus 00:08:39.980 --> 00:08:48.300 eins halbe quadratisch in N ist. Also das war meine Zeit für das Auffinden eines Puzzleteils. Und 00:08:48.300 --> 00:08:52.780 jetzt möchte ich eben sehen, wie das von dem N abhängt und das hängt quadratisch von diesem 00:08:52.780 --> 00:08:59.580 N ab. Und wenn ich jetzt zwei 500er Puzzle lösen will, dann habe ich sowas wie zweimal 500 quadrat 00:08:59.580 --> 00:09:07.220 und wenn ich ein 1000er Puzzle lösen will, kriege ich 1000 ins Quadrat und 1000 ist zweimal 500, 00:09:07.220 --> 00:09:12.300 also kriege ich zweimal 500 in Klammern ins Quadrat, was viermal 500 Quadrat ist, also doppelt so lange 00:09:12.300 --> 00:09:19.820 wie meine zwei 500er Puzzle. Natürlich habe ich noch einen gewissen Overhead, also eine gewisse 00:09:19.820 --> 00:09:24.380 Zusatzzeit, die ich für das Sortieren brauche. Also wenn ich mein 1000er Puzzle in zwei 500er 00:09:24.380 --> 00:09:28.380 Puzzle aufteilen könnte, angenommen ich wüsste schon, welches die linke und die rechte Hälfte 00:09:28.380 --> 00:09:32.780 ist, dann hätte ich ja zwei 500er Puzzle, dann würde ich zwar schneller vorankommen, aber irgendwie 00:09:32.780 --> 00:09:37.420 muss ich das noch schaffen, das in die linke und die rechte Hälfte zu unterteilen. Meine Tante, 00:09:37.420 --> 00:09:40.540 die macht immer sowas komisches, wenn die Puzzle fertig hat und es wieder einpackt in die Schachtel, 00:09:40.540 --> 00:09:44.620 dann macht sie zwei Tüten, eine für die linke Hälfte, eine für die rechte Hälfte. Ich finde 00:09:44.620 --> 00:09:48.700 das irgendwie ein bisschen übergriffig, aber na gut, ist auf jeden Fall leichter zu lösen, wie wir uns 00:09:48.700 --> 00:09:54.060 gerade überlegt haben. Man kann den Vorteil noch verbessern, indem man statt einen 1000er in zwei 00:09:54.060 --> 00:10:00.500 500er zu unterteilen, einen 1000er in 10 100er Puzzle unterteilt oder noch besser in 1000 Einer Puzzle. 00:10:00.500 --> 00:10:07.980 Hä? Moment mal, 1000 Einer Puzzle? Was soll das denn bedeuten? Ja, also da kommt dann der Overhead zum 00:10:07.980 --> 00:10:13.300 Sortieren richtig zu tragen. Also 1000 Einer Puzzle bedeutet irgendwie sowas wie, man weiß 00:10:13.300 --> 00:10:17.500 eigentlich immer sofort, welches Teil man nehmen soll als nächstes und muss es nur noch hinsetzen. 00:10:17.500 --> 00:10:24.940 Dann muss aber das Puzzle schon vorher sehr gut sortiert sein. Aber diese 10 100er Puzzle, das 00:10:24.940 --> 00:10:29.820 bedeutet irgendwie, es gibt eine natürliche Unterteilung der Puzzleteile, die man hat, 00:10:29.820 --> 00:10:37.380 in so Gruppen, sagen wir von Größe 100, 10 Gruppen von Größe 100 und man kann sich ganz sicher sein, 00:10:37.380 --> 00:10:41.580 welches in welcher Gruppe ist. Ich kann mir bei einem Puzzle erst mal a priori nicht sicher sein, 00:10:41.580 --> 00:10:44.900 welches in der linken Hälfte ist und welches in der rechten Hälfte ist. Das sehe ich einem Teil 00:10:44.900 --> 00:10:49.380 meistens nicht so leicht an. Aber wenn man ein Bild hat, was sich farblich unterscheidet, 00:10:49.380 --> 00:10:53.700 starker Kontrast da hat oder so, also Farbunterschiede, dann kann man eben sortieren 00:10:53.700 --> 00:10:58.580 nach die roten Teile und die grünen Teile und bekommt dann eine natürliche Unterteilung in so 00:10:58.580 --> 00:11:04.380 Unterpuzzle. Naja und dann hat man eben diese Verbesserung, indem man irgendwie nach Farbe 00:11:04.380 --> 00:11:08.180 sortiert oder irgendwelchen anderen Informationen. Ich benutze zum Beispiel auch gerne diese 00:11:08.180 --> 00:11:12.740 Formkriterien. Wichtig ist jedenfalls, dass es sortieren irgendwie leicht ist und zügig geht, 00:11:12.740 --> 00:11:17.860 irgendwie fast schon algorithmisch. Habe ich darüber nachgedacht, dass es irgendwas mit 00:11:17.860 --> 00:11:22.620 Sortieralgorithmen zu tun hat? Ich will es auch gar keine große Sortieralgorithmen-Vorlesung 00:11:22.620 --> 00:11:28.020 halten. Das könnt ihr dann im Informatikstudium machen oder auch im Selbststudium lernen. Das 00:11:28.020 --> 00:11:32.460 sind so Sachen, die sehr schön auf Wikipedia oder verschiedenen Blogs beschrieben sind. Ich möchte 00:11:32.460 --> 00:11:38.580 euch mal einen Algorithmus vorstellen, der meiner Meinung nach viel zu wenig Bedeutung hat oder viel 00:11:38.580 --> 00:11:44.140 zu wenig Beachtung bekommt. Und der Algorithmus heißt Slow Sort, also langsames Sortieren. In 00:11:44.140 --> 00:11:48.020 gewisser Hinsicht ist das ja auch das, worum es beim Puzzlen geht. Ich sage euch erstmal, 00:11:48.020 --> 00:11:53.220 wie der Algorithmus geht. Slow Sort funktioniert so. Man hat eine Liste von Dingen, die man sortieren 00:11:53.220 --> 00:11:58.700 möchte. Das ist jetzt ein bisschen anders als ein Puzzle sortieren. Man hat nämlich eine Liste von 00:11:58.700 --> 00:12:05.020 Dingen und man kann für je zwei Dinge sagen, ob eins größer ist als das andere oder ob sie gleich 00:12:05.020 --> 00:12:09.980 groß sind. Und man möchte die Liste jetzt der Größe nach sortieren. Bei einem Puzzle ist es 00:12:09.980 --> 00:12:13.640 irgendwie so, dass man nach Kategorien sortiert. Natürlich kann man die Kategorien irgendwie 00:12:13.640 --> 00:12:20.820 beliebig anordnen und dann wäre es auch so eine vergleichbare Algorithmus. Also diese Liste zu 00:12:20.820 --> 00:12:26.500 sortieren, die wie man sagt, partiell geordnet ist, also mit so einer ist größer gleich, 00:12:26.500 --> 00:12:32.500 ist kleiner gleich oder gleich. Groß Eigenschaft ist eine Verallgemeinerung von dem, was wir beim 00:12:32.500 --> 00:12:36.420 Puzzle sortieren machen. Na gut, sagen wir mal, man hat also diese Liste von Dingen, die man 00:12:36.420 --> 00:12:40.500 sortieren möchte. Und Slow Sort ist jetzt ein rekursiver Algorithmus, der ruft sich also selbst 00:12:40.500 --> 00:12:46.300 wieder auf. Und er geht vor nach dem Paradigma multiply and surrender, also vervielfältige und 00:12:46.300 --> 00:12:52.420 gibt auf. Und das Paradigma bedeutet, dass er nur prinzipiell sinnvolle Schritte macht, 00:12:52.420 --> 00:12:57.260 also nicht irgendwie jetzt dumm rumwartet oder irgendwelche Endlosschleifen macht. Also der 00:12:57.260 --> 00:13:01.940 macht schon sinnvolle Schritte der Algorithmus. Der will aber seine Termination, hört sich auch 00:13:01.940 --> 00:13:07.420 schon so schlimm an, also das Laufzeitende so lang wie möglich herauszögern. Denn das begreift 00:13:07.420 --> 00:13:11.340 er eben als Niederlage. Surrender ist der Surrenderschritt. Deswegen versucht er, 00:13:11.340 --> 00:13:16.980 sich vorher immer zu multiplizieren, also sich möglichst oft selbst rekursiv aufzurufen. Okay, 00:13:16.980 --> 00:13:21.780 also wie geht der jetzt? Wir wollen sortieren und dazu bestimmen wir erstmal das Maximum der Liste. 00:13:21.780 --> 00:13:25.460 Also wir haben unsere Liste und bestimmen nach einem bestimmten Verfahren, das ich gleich noch 00:13:25.460 --> 00:13:31.940 erkläre, das Maximum. Dann nehmen wir dieses Maximum und platzieren das am Ende der Liste. Und 00:13:31.940 --> 00:13:37.020 dann sortieren wir den Rest der Liste mit dem gleichen Verfahren. Das ist die Rekursion. Gibt 00:13:37.020 --> 00:13:41.420 auch noch eine andere Rekursion in dem Schritt, in dem wir das Maximum bestimmen. Um das Maximum der 00:13:41.420 --> 00:13:46.620 Liste zu bestimmen, teilen wir die Liste nämlich in zwei Hälften auf und rufen den gleichen 00:13:46.620 --> 00:13:53.660 Algorithmus wieder rekursiv für die beiden Hälften auf. Und dann haben wir zwei Listen. Die sind 00:13:53.660 --> 00:13:58.940 beide in sich sortiert. Also die haben beide das Maximum ganz rechts oder ganz oben oder eben wir 00:13:58.940 --> 00:14:03.020 kennen das Maximum von der Liste, von den zwei Listen. Und dann vergleichen wir die zwei maximal 00:14:03.020 --> 00:14:06.900 und das ist das Ergebnis, was wir in dem ersten Schritt haben wollen. Nämlich das Maximum der 00:14:06.900 --> 00:14:11.980 Gesamtliste ist das Maximum von den beiden maximal. Okay, und das nehmen wir nach hinten und machen 00:14:11.980 --> 00:14:15.940 eben das Ganze. Es hört sich eigentlich gar nicht so schlimm an. Es ist eigentlich so ein 00:14:15.940 --> 00:14:22.500 ähnliches Verfahren wie Merge Sort, falls es jemand kennt. Merge Sort verfährt die ganze Zeit 00:14:22.500 --> 00:14:27.660 genauso. Merge Sort führt die beiden Listen zusammen, indem es ausnutzt, dass die schon 00:14:27.660 --> 00:14:32.420 sortiert sind und die einfach so wie so ein Reißverschluss ineinander führt, sodass die 00:14:32.420 --> 00:14:37.660 Gesamtliste sofort sortiert ist nach einem Schritt. Das machen wir bei Slow Sort aber nicht. Slow Sort 00:14:37.660 --> 00:14:42.220 verzichtet jetzt einfach auf diesen mühsamen Schritt des Zusammenführens und ist dadurch 00:14:42.220 --> 00:14:49.140 konzeptionell viel einfacher. Natürlich haben die Informatikerinnen schon untersucht, wie effizient 00:14:49.140 --> 00:14:56.980 Slow Sort ist. Und es braucht ungefähr N hoch log N Schritte. Das bedeutet für die Leute, die 00:14:56.980 --> 00:15:04.260 sich jetzt mit Komplexität nicht so auskennen, das ist ziemlich blöd, weil normalerweise will 00:15:04.260 --> 00:15:09.580 man irgendwie so eine Art polinomiellen, also man erwartet irgendwie so ein polinomielles 00:15:09.580 --> 00:15:17.660 Wachstum und N ist wieder die Länge der Liste, die man sortieren will. Und schlechte Sortieralgorithmen 00:15:17.660 --> 00:15:26.260 haben sowas wie N-Quadrat-Operationen und gute sowas wie N-Mal-Logarithmus von N. Und Merge Sort 00:15:26.260 --> 00:15:32.540 zum Beispiel ist einer in der Kategorie, der sich im Wesentlichen so wie N-Mal-Log N verhält und noch 00:15:32.540 --> 00:15:36.380 viele andere schöne Eigenschaften hat. Slow Sort hat die Eigenschaft aber nicht. Slow Sort ist 00:15:36.380 --> 00:15:42.380 langsamer als alle polinomiellen Sortieralgorithmen. Man kann das auch genau analysieren mit so Analyse 00:15:42.380 --> 00:15:46.660 von rekursiven Algorithmen. Mach ich jetzt aber hier nicht. Man kann sich das irgendwie so ein 00:15:46.660 --> 00:15:50.700 bisschen vorstellen, dass von den zwei Listen, dass eigentlich ziemlich selten was getauscht wird in 00:15:50.700 --> 00:15:54.580 diesem Algorithmus, denn von den zwei Listen wird immer nur was getauscht, wenn die beiden maximal in 00:15:54.580 --> 00:16:00.180 der falschen Reihenfolge sind. Es sind aber eine ganze Menge Vertauschungen nötig und dieser 00:16:00.180 --> 00:16:06.220 Algorithmus, der lässt sich eben Zeit und genießt das Leben ein bisschen. Und das ist vielleicht 00:16:06.220 --> 00:16:10.100 ganz wichtig in unserer hektischen Wirklichkeit, nicht immer nur auf die Effizienz zu schielen. 00:16:10.100 --> 00:16:15.300 Man sollte vielleicht auch mal einen Puzzle machen oder was mit Slow Sort sortieren. Und das ist mein 00:16:15.300 --> 00:16:20.420 Fazit dieses Sortierens und da wünsche ich euch jetzt einen guten Tag, eine gute Nacht, 00:16:20.420 --> 00:16:24.060 eine gute Zeit und lasst es mal langsam angehen. Ciao!