[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:06.62,0:00:09.18,Default,,0000,0000,0000,,Du arbeitest in der \NUniversitätsbibliothek.
Dialogue: 0,0:00:09.18,0:00:11.40,Default,,0000,0000,0000,,Es ist ein ruhiger Nachmittag,
Dialogue: 0,0:00:11.40,0:00:18.01,Default,,0000,0000,0000,,als plötzlich eine Lieferung von 1280\Nunterschiedlichen Bücher ankommt.
Dialogue: 0,0:00:18.01,0:00:21.33,Default,,0000,0000,0000,,Die Bücher wurden in einer \Nlange, geraden Reihe aufgestellt,
Dialogue: 0,0:00:21.33,0:00:23.10,Default,,0000,0000,0000,,doch sie sind nicht geordnet,
Dialogue: 0,0:00:23.10,0:00:27.03,Default,,0000,0000,0000,,und das automatische \NSortiersystem ist kaputt.
Dialogue: 0,0:00:27.03,0:00:29.67,Default,,0000,0000,0000,,Zu allem Übel fängt morgen\Nwieder der Unterricht an,
Dialogue: 0,0:00:29.67,0:00:32.00,Default,,0000,0000,0000,,was bedeutet, dass gleich morgen früh
Dialogue: 0,0:00:32.00,0:00:36.56,Default,,0000,0000,0000,,Studenten scharenweise \Nnach diesen Büchern suchen werden.
Dialogue: 0,0:00:36.56,0:00:39.29,Default,,0000,0000,0000,,Wie schaffst du es\Nalle rechtzeitig zu ordnen?
Dialogue: 0,0:00:39.29,0:00:44.59,Default,,0000,0000,0000,,Du könntest z. B. an einem Ende der Reihe\Nmit dem ersten Buchpaar anfangen.
Dialogue: 0,0:00:44.59,0:00:48.37,Default,,0000,0000,0000,,Wenn die ersten zwei Bücher \Ngeordnet sind, dann lass sie so.
Dialogue: 0,0:00:48.37,0:00:50.65,Default,,0000,0000,0000,,Ansonsten, tausche sie.
Dialogue: 0,0:00:50.65,0:00:53.22,Default,,0000,0000,0000,,Sieh dir dann das 2. und 3. Buch an,
Dialogue: 0,0:00:53.22,0:00:54.88,Default,,0000,0000,0000,,wiederhole den Vorgang,
Dialogue: 0,0:00:54.88,0:00:57.94,Default,,0000,0000,0000,,und mach so weiter bis zum Ende der Reihe.
Dialogue: 0,0:00:57.94,0:01:01.02,Default,,0000,0000,0000,,Irgendwann stößt du auf das Buch,\Ndas als letztes stehen sollte.
Dialogue: 0,0:01:01.04,0:01:04.53,Default,,0000,0000,0000,,Du tauscht es weiterhin mit \Nden darauffolgenden Büchern,
Dialogue: 0,0:01:04.53,0:01:09.18,Default,,0000,0000,0000,,und rückst es somit an \Ndas Ende der Reihe, wo es hingehört.
Dialogue: 0,0:01:09.18,0:01:12.22,Default,,0000,0000,0000,,Dann beginnst du wieder von vorne\Nund wiederholst den Vorgang,
Dialogue: 0,0:01:12.22,0:01:15.51,Default,,0000,0000,0000,,um das zweitletzte Buch \Nan seinen Platz zu bringen.
Dialogue: 0,0:01:15.51,0:01:18.56,Default,,0000,0000,0000,,So machst du weiter, \Nbis alle Bücher sortiert sind.
Dialogue: 0,0:01:18.56,0:01:21.68,Default,,0000,0000,0000,,Diese Methode heißt "Bubblesort".
Dialogue: 0,0:01:21.68,0:01:23.100,Default,,0000,0000,0000,,Sie ist sehr einfach, aber langsam.
Dialogue: 0,0:01:23.100,0:01:29.20,Default,,0000,0000,0000,,Du würdest 1279 Vergleiche\Nin der erste Runde machen,
Dialogue: 0,0:01:29.20,0:01:33.62,Default,,0000,0000,0000,,dann 1278, und so weiter.
Dialogue: 0,0:01:33.62,0:01:38.54,Default,,0000,0000,0000,,Insgesamt wären das 818 560 Vergleiche.
Dialogue: 0,0:01:38.54,0:01:41.09,Default,,0000,0000,0000,,Würde jeder Vergleich \Nnur eine Sekunde benötigen,
Dialogue: 0,0:01:41.09,0:01:44.27,Default,,0000,0000,0000,,dann würde das Verfahren\Nmehr als neun Tage dauern.
Dialogue: 0,0:01:44.27,0:01:48.57,Default,,0000,0000,0000,,Eine zweite Strategie wäre, zuerst nur\Ndie ersten beiden Bücher zu ordnen.
Dialogue: 0,0:01:48.57,0:01:51.30,Default,,0000,0000,0000,,Nimm dann das dritte Buch\Nund vergleiche es\N
Dialogue: 0,0:01:51.30,0:01:53.60,Default,,0000,0000,0000,,mit dem Buch an zweiter Stelle.
Dialogue: 0,0:01:53.60,0:01:56.99,Default,,0000,0000,0000,,Gehört es vor's zweite Buch, tausche sie.
Dialogue: 0,0:01:56.99,0:01:59.48,Default,,0000,0000,0000,,Vergleiche es dann\Nmit dem Buch an erster Stelle,
Dialogue: 0,0:01:59.48,0:02:01.49,Default,,0000,0000,0000,,und tausche die beiden, wenn nötig.
Dialogue: 0,0:02:01.49,0:02:03.88,Default,,0000,0000,0000,,Jetzt hast du die ersten\Ndrei Bücher sortiert.
Dialogue: 0,0:02:03.88,0:02:07.73,Default,,0000,0000,0000,,Füge ein Buch nach dem anderen\Nzu der geordneten Bücherreihe hinzu,
Dialogue: 0,0:02:07.73,0:02:11.81,Default,,0000,0000,0000,,indem du es mit den Büchern davor \Nvergleichst und tauschst,
Dialogue: 0,0:02:11.81,0:02:15.82,Default,,0000,0000,0000,,bis es an der richtigen Stelle\Nunter den schon sortierten Büchern steht.
Dialogue: 0,0:02:15.82,0:02:18.06,Default,,0000,0000,0000,,Dieses Verfahren heißt "Insertionsort".
Dialogue: 0,0:02:18.06,0:02:22.81,Default,,0000,0000,0000,,Anders als bei Bubblesort, muss man nicht\Njedes Buchpaar miteinander vergleichen.
Dialogue: 0,0:02:22.81,0:02:25.51,Default,,0000,0000,0000,,Im Durchschnitt erwarten wir,\Ndass wir jedes Buch
Dialogue: 0,0:02:25.51,0:02:29.14,Default,,0000,0000,0000,,nur mit der Hälfte der Bücher,\Ndie davor kommen, vergleichen müssen.
Dialogue: 0,0:02:29.14,0:02:32.03,Default,,0000,0000,0000,,In diesem Fall liegt \Ndie Gesamtzahl der Vergleiche
Dialogue: 0,0:02:32.03,0:02:35.98,Default,,0000,0000,0000,,bei 409 280,
Dialogue: 0,0:02:35.98,0:02:38.14,Default,,0000,0000,0000,,und dauert fast fünf Tage.
Dialogue: 0,0:02:38.14,0:02:40.62,Default,,0000,0000,0000,,Du machst immer noch\Nviel zu viele Vergleiche.
Dialogue: 0,0:02:40.62,0:02:42.52,Default,,0000,0000,0000,,Hier eine bessere Idee:
Dialogue: 0,0:02:42.52,0:02:44.88,Default,,0000,0000,0000,,Zuerst wählst du willkürlich ein Buch aus.
Dialogue: 0,0:02:44.88,0:02:49.61,Default,,0000,0000,0000,,Das ist das Trennelement, \Ndas du mit jedem anderen Buch vergleichst.
Dialogue: 0,0:02:49.61,0:02:51.52,Default,,0000,0000,0000,,Teile dann die Reihe,
Dialogue: 0,0:02:51.52,0:02:55.49,Default,,0000,0000,0000,,indem du alle Bücher, die vor dem \NTrennelement stehen, links davon anordnest
Dialogue: 0,0:02:55.49,0:02:58.54,Default,,0000,0000,0000,,und alle die danach kommen, rechts davon.
Dialogue: 0,0:02:58.54,0:03:00.56,Default,,0000,0000,0000,,Du hast gerade sehr viel Zeit gespart,
Dialogue: 0,0:03:00.56,0:03:03.84,Default,,0000,0000,0000,,denn du musst nie wieder\Ndie Bücher auf der linken Seite
Dialogue: 0,0:03:03.84,0:03:06.98,Default,,0000,0000,0000,,mit den Büchern auf\Nder rechten Seite vergleichen.
Dialogue: 0,0:03:06.98,0:03:09.66,Default,,0000,0000,0000,,Betrachte jetzt nur \Ndie Bücher auf der linken Seite.
Dialogue: 0,0:03:09.66,0:03:12.54,Default,,0000,0000,0000,,Du kannst hier wieder \Nein Buch als Trennelement wählen,
Dialogue: 0,0:03:12.54,0:03:16.97,Default,,0000,0000,0000,,und die Bücher, die davor und \Ndanach kommen, voneinander trennen.
Dialogue: 0,0:03:16.97,0:03:19.90,Default,,0000,0000,0000,,So kannst du immer weitere\NUnterteilungen erzeugen,
Dialogue: 0,0:03:19.90,0:03:22.38,Default,,0000,0000,0000,,bis du eine Menge\Nkleiner Teilbereiche hast,
Dialogue: 0,0:03:22.38,0:03:27.76,Default,,0000,0000,0000,,die du durch eine andere Sortiermethode,\Nwie Insertionsort, schnell ordnen kannst.
Dialogue: 0,0:03:27.76,0:03:33.01,Default,,0000,0000,0000,,Bei jeder Unterteilung fallen \Netwa 1280 Vergleiche an.
Dialogue: 0,0:03:33.01,0:03:35.47,Default,,0000,0000,0000,,Wenn deine Aufteilungen\Nrelativ gleichmäßig sind,
Dialogue: 0,0:03:35.47,0:03:40.09,Default,,0000,0000,0000,,brauchst du, wenn du die Bücher in\N128 Teilbereiche à zehn Bücher teilst,
Dialogue: 0,0:03:40.09,0:03:43.95,Default,,0000,0000,0000,,ca. 7 Runden, oder 8960 Sekunden.
Dialogue: 0,0:03:43.95,0:03:48.50,Default,,0000,0000,0000,,Das Sortieren dieser Teilbereiche\Nbraucht jeweils 22 Sekunden.
Dialogue: 0,0:03:48.50,0:03:51.96,Default,,0000,0000,0000,,Alles in allem könntest du \Nmit dieser Methode namens "Quicksort"
Dialogue: 0,0:03:51.96,0:03:54.42,Default,,0000,0000,0000,,die Bücher in unter \Ndreieinhalb Stunden ordnen.
Dialogue: 0,0:03:54.42,0:03:55.80,Default,,0000,0000,0000,,Doch das hat einen Haken:
Dialogue: 0,0:03:55.80,0:03:58.12,Default,,0000,0000,0000,,Sind die Unterteilungen ungleichmäßig,
Dialogue: 0,0:03:58.12,0:03:59.68,Default,,0000,0000,0000,,sparst du keine Zeit.
Dialogue: 0,0:03:59.68,0:04:01.53,Default,,0000,0000,0000,,Glücklicherweise passiert das selten.
Dialogue: 0,0:04:01.53,0:04:04.74,Default,,0000,0000,0000,,Deshalb ist Quicksort eine\Nder effizientesten Strategien,
Dialogue: 0,0:04:04.74,0:04:06.92,Default,,0000,0000,0000,,die heute von Programmierern benutzt wird.
Dialogue: 0,0:04:06.92,0:04:10.85,Default,,0000,0000,0000,,Damit werden in Onlineshops\Ndie Waren nach dem Preis geordnet,
Dialogue: 0,0:04:10.85,0:04:14.64,Default,,0000,0000,0000,,oder eine Liste aller Tankstellen\Nin der Nähe eines gegeben Ortes
Dialogue: 0,0:04:14.64,0:04:16.54,Default,,0000,0000,0000,,nach Entfernung sortiert.
Dialogue: 0,0:04:16.54,0:04:20.22,Default,,0000,0000,0000,,In deinem Fall bist du mit dem Ordnen\Nfertig, und hast noch Zeit über.
Dialogue: 0,0:04:20.22,0:04:23.17,Default,,0000,0000,0000,,Wieder ein anspruchsvoller Tag\Nin der Bibliothek.