WEBVTT 00:06.970 --> 00:08.560 Willkommen zur Algorithmen-Vorlesung. 00:10.420 --> 00:13.860 Ganz kurzen Überblick über das, was wir heute machen und über das, was 00:13.860 --> 00:14.980 wir letztes Mal gemacht haben. 00:17.080 --> 00:22.800 Also letztes Mal hatten wir uns mit QuickSort beschäftigt und das als 00:22.800 --> 00:24.560 Mergesort andersrum eingesehen. 00:25.560 --> 00:30.460 Also in dem Sinne, dass man Teile und Herrscher betreibt, aber diesmal 00:30.460 --> 00:33.860 so, dass man die Hauptarbeit oder die eigentliche Arbeit vor dem 00:33.860 --> 00:35.040 rekursiven Abstieg macht. 00:36.200 --> 00:39.240 Wir hatten gesehen, dass QuickSort ein Algorithmus ist, der hat 00:39.240 --> 00:42.380 eigentlich eine schlechte Worst-Case-Laufzeit und die Best-Case 00:42.380 --> 00:44.840 -Laufzeit ist auch gar nicht mal so gut. 00:45.140 --> 00:48.300 Also die Best-Case-Laufzeit ist NlogN, wohingegen... 00:48.300 --> 00:51.740 also Theta von NlogN, wohingegen zum Beispiel InsertionSort sogar eine 00:51.740 --> 00:53.960 Best -Case-Laufzeit von Theta von N hatte. 00:54.840 --> 00:59.040 Aber die hauptpositive Eigenschaft von QuickSort, die wir letztes Mal 00:59.040 --> 01:02.520 eingesehen haben, ist, dass wenn wir dieses Pivot-Element, das die 01:02.520 --> 01:05.880 Aufteilung bestimmt, also ich habe gleich nochmal eine kurze Folie 01:05.880 --> 01:09.300 dazu, zur Erinnerung, wie QuickSort lief, weil wir darauf heute 01:09.300 --> 01:14.220 aufbauen, wenn wir dieses Pivot-Element zufällig wählen, dann haben 01:14.220 --> 01:16.220 wir eine gute Laufzeit, also Theta von NlogN. 01:16.580 --> 01:20.380 Also so wie Mergesort im deterministischen Fall schon hinkriegt. 01:21.380 --> 01:25.040 Wir hatten uns ein paar Varianten angeguckt, insbesondere, ich glaube, 01:25.300 --> 01:28.480 der Laser-Pointer stirbt gerade. 01:29.980 --> 01:31.640 Naja, man kann es vielleicht noch so ein bisschen sehen. 01:31.780 --> 01:34.680 Also wir hatten eine halbrekursive Implementierung angeguckt, die 01:34.680 --> 01:40.860 zumindest mal den zusätzlichen Platzbedarf, den QuickSort braucht, 01:40.980 --> 01:44.040 nach oben abschätzt durch, also die Anzahl, die Tiefe des 01:44.040 --> 01:46.080 logarithmischen Abstiegs abschätzt durch LogN. 01:47.220 --> 01:48.100 Okay, was machen wir heute? 01:49.060 --> 01:50.300 Wir schließen QuickSort ab. 01:50.460 --> 01:52.120 Das dauert vermutlich nicht so lange. 01:53.340 --> 01:56.060 Wir gucken uns noch eine weitere Variante an, die einen Vorteil 01:56.060 --> 01:57.740 gegenüber der Variante von letztem Mal hat. 01:58.660 --> 02:00.400 Und wir vergleichen es vor allem mit Mergesort. 02:00.840 --> 02:03.720 Und anschließend gucken wir uns ein neues Problem an, das 02:03.720 --> 02:04.420 Auswahlproblem. 02:04.920 --> 02:09.020 Das hat zum einen als Problem direkten Bezug zu QuickSort, weil uns 02:09.020 --> 02:12.400 ein effizienter Algorithmus für dieses Problem auch eine 02:12.400 --> 02:15.560 deterministische Lösung für QuickSort liefert, also eine, wo man nicht 02:15.560 --> 02:17.160 mit Erwartungswerten herumrechnen muss. 02:18.160 --> 02:21.040 Und wir werden das tatsächlich auch mit ähnlichen Techniken wie in 02:21.040 --> 02:22.020 QuickSort implementieren. 02:23.100 --> 02:27.380 Und schließlich sprechen wir schon mal an, noch nicht endgültig durch, 02:27.500 --> 02:31.640 aber wir sprechen schon mal an, wie man diese untere Schranke, die wir 02:31.640 --> 02:35.200 etabliert hatten, für die Laufzeit vergleichsbasierter 02:35.200 --> 02:37.300 Sortieralgorithmen, wie wir die durchbrechen. 02:39.340 --> 02:40.720 Okay, also zunächst mal zur Erinnerung. 02:41.500 --> 02:42.560 Wie funktioniert QuickSort? 02:42.640 --> 02:44.220 Wir wählen ein Pivot-Element. 02:44.720 --> 02:47.280 Also wir wollen eine Folge A sortieren, als Array gegeben. 02:47.460 --> 02:51.320 Das ist schon die Inplace-Variante von QuickSort, also da, wo wir mit 02:51.320 --> 02:55.000 einem Array rechnen und keinen zusätzlichen Platz benötigen, bis auf 02:55.000 --> 02:58.040 die Variablen, die von rekursivem Abstieg benötigt werden. 02:59.160 --> 03:02.000 Wir wählen als erstes mal ein Pivot-Element irgendwie, zum Beispiel 03:02.000 --> 03:09.900 zufällig, und partitionieren dann dieses Array in Elemente, die 03:09.900 --> 03:12.440 kleiner als das Pivot-Element sind, die gleich dem Pivot-Element sind 03:12.440 --> 03:13.960 und die größer als das Pivot-Element sind. 03:14.060 --> 03:18.060 Tatsächlich hatten wir uns hier eine spezielle Variante angeguckt, wo 03:18.060 --> 03:21.720 wir nur einen Mittelpunkt haben, und das ist die Grenze von allen 03:21.720 --> 03:24.380 Elementen, die kleiner gleich dem Pivot-Element sind, zu den 03:24.380 --> 03:26.420 Elementen, die echt größer dem Pivot-Element sind. 03:27.340 --> 03:29.580 Und dann sortieren wir beide Hälften rekursiv. 03:31.820 --> 03:34.460 Dann hatten wir diesen Partitionierungsalgorithmus, da will ich jetzt 03:34.460 --> 03:36.420 auf die Details gar nicht mehr eingehen, den hatten wir letztes Mal 03:36.420 --> 03:36.840 besprochen. 03:37.560 --> 03:42.180 Das Wichtige ist, am Ende landen wir bei einem partitionierten Array, 03:42.400 --> 03:45.360 wo alle Elemente kleiner gleich P auf der linken Seite sind. 03:45.960 --> 03:49.940 Dann haben wir das Pivot-Element selbst, das könnte aber links zum 03:49.940 --> 03:51.160 Beispiel noch ein paar Mal vorkommen. 03:51.520 --> 03:52.500 Also das ist jetzt ganz wichtig. 03:53.760 --> 03:56.740 Es gibt keine Garantie, dass hier links bei dem kleiner gleich P, also 03:56.740 --> 03:59.840 P wie Pivot-Element, dass da nicht auch Elemente drin sind, die noch 03:59.840 --> 04:02.000 dem Pivot-Element genau entsprechen, also Kopien. 04:02.680 --> 04:06.260 Und dann haben wir rechts von dieser Stelle I nur Elemente, die größer 04:06.260 --> 04:07.160 dem Pivot-Element sind. 04:08.780 --> 04:13.220 Okay, jetzt behaupte ich, das hat man uns letztes Mal angeguckt und 04:13.220 --> 04:16.400 ich behaupte, das ist in manchen Situationen, die gar nicht so 04:16.400 --> 04:20.240 unnatürlich sind, gar keine so gute Idee, weil das einen sehr 04:20.240 --> 04:23.220 schlechten Sortieralgorithmus liefert, der in quadratischer Zeit 04:23.220 --> 04:23.600 läuft. 04:24.620 --> 04:28.420 Und diese Situationen, die treten dann auf, wenn Sie sich vorstellen, 04:28.540 --> 04:33.860 was passiert, wenn wir ein Array aus lauter gleichen Elementen 04:33.860 --> 04:34.260 sortieren. 04:34.860 --> 04:40.760 Also das Szenario ist, wir haben ein Array A und wir sortieren das mit 04:40.760 --> 04:44.740 Quicksort und in diesem Array A stehen lauter Elemente drin, die sehen 04:44.740 --> 04:46.660 alle aus wie das Pivot-Element, die sind alle gleich. 04:47.320 --> 04:49.780 Also klar, wenn wir dann eins auswählen als Pivot-Element, wird das 04:49.780 --> 04:51.860 natürlich auch eins von diesen gleichen Elementen sein. 04:51.940 --> 04:52.420 Was passiert? 04:53.460 --> 04:56.040 So wie dieser Algorithmus hier funktioniert, diese Partitionierung 04:56.040 --> 05:00.400 wird das dann so aussehen, dass wir, egal wie wir das Pivot-Element 05:00.400 --> 05:02.540 wählen, dass wir immer ungünstig partitionieren. 05:02.540 --> 05:08.120 In dem Sinne, wir teilen das in diese zwei Hälften ein und jetzt ist 05:08.120 --> 05:11.700 es so, jetzt sind alle Elemente kleiner gleich P. Das heißt, wir haben 05:11.700 --> 05:15.880 rechts eins von diesen P's aussortiert, das steht dann ganz rechts bei 05:15.880 --> 05:20.540 diesem R am Ende und links davon ist alles kleiner gleich P. Also es 05:20.540 --> 05:22.560 gibt keine größer P-Elemente, weil alle gleich sind. 05:23.020 --> 05:24.560 Was bedeutet das für unseren Algorithmus? 05:25.760 --> 05:28.400 Das bedeutet, wir partitionieren ein bisschen ungünstig, weil dann 05:28.400 --> 05:32.540 eine Hälfte, also Hälfte ist jetzt vielleicht schlecht, ein Block, den 05:32.540 --> 05:36.380 wir dann nochmal, ein Unterblock, ein Unterarray, das wir dann 05:36.380 --> 05:42.060 sortieren wollen, das hat dann fast die volle Größe, nämlich n-1 05:42.060 --> 05:45.780 Elemente und das andere Array ist leer, also das andere Teilarray 05:45.780 --> 05:46.040 davon. 05:47.400 --> 05:48.080 Und was passiert? 05:48.240 --> 05:50.140 Das wird natürlich beim rekursiven Abstieg wieder und wieder 05:50.140 --> 05:50.560 passieren. 05:51.040 --> 05:54.880 Also wir werden quasi immer dümmstmöglich einteilen und dann wird der 05:54.880 --> 05:58.080 Algorithmus wieder, wie ganz am Anfang im Worst-Case, eine 05:58.080 --> 05:59.200 quadratische Laufzeit haben. 05:59.940 --> 06:04.480 Das heißt, auf Eingaben, die eigentlich ganz natürlich sind, nämlich 06:04.480 --> 06:07.440 nur gleiche Elemente, das könnte schon mal, ist es denkbar, dass das 06:07.440 --> 06:11.680 mal vorkommt, ist dieser Algorithmus ausgesprochen langsam, obwohl das 06:11.680 --> 06:13.280 Problem eigentlich ziemlich einfach ist. 06:15.980 --> 06:17.560 Okay, was kann man da tun? 06:17.920 --> 06:22.860 Man kann einmal diese Partitionierung in diese zwei Unterblöcke kann 06:22.860 --> 06:25.360 man ein bisschen effizienter gestalten, oder nicht effizienter, aber 06:25.360 --> 06:27.320 ein bisschen klüger vielleicht gestalten. 06:27.980 --> 06:32.160 Was man tun kann, ist, man kann zum Beispiel, wenn man nach diesem 06:32.160 --> 06:36.060 Pivot -Element hier einteilt in zwei Klassen, dann kann man das so 06:36.060 --> 06:40.000 machen, dass man auch rechts einen Block von Elementen hat, die größer 06:40.000 --> 06:40.760 gleich P sind. 06:41.660 --> 06:45.000 Das wäre an sich noch nichts, was uns jetzt stören würde. 06:45.460 --> 06:47.720 Also wenn wir links kleiner gleich und rechts größer gleich P haben, 06:48.480 --> 06:50.640 dann würde das nichts, was die Sortierung an sich stören würde. 06:51.060 --> 06:53.420 Dann könnten wir uns also, wenn wir in diesem 06:53.420 --> 06:56.740 Partitionierungsalgorithmus alle Elemente der Reihe nach durchgehen 06:56.740 --> 07:00.580 und eine in einen von diesen zwei Töpfen werfen, dann könnten wir zum 07:00.580 --> 07:05.000 Beispiel das erste Element, was gleich P ist, in den linken Topf 07:05.000 --> 07:08.000 werfen, das zweite in den rechten, das dritte wieder in den linken und 07:08.000 --> 07:09.680 immer so abwechselnd in diese Töpfe werfen. 07:10.260 --> 07:11.140 Das wäre eine Möglichkeit. 07:12.220 --> 07:15.940 Dann haben wir nur zwei Töpfe und also nur zwei von diesen Unterfolgen 07:18.020 --> 07:21.260 hier und die sind am Ende aber bei nur gleichen Elementen auch 07:21.260 --> 07:22.200 gleichmäßig verteilt. 07:22.300 --> 07:22.880 Kann man machen. 07:24.200 --> 07:25.700 Da wird auch so etwas in der Art im Buch vorgestellt. 07:27.180 --> 07:31.060 Was wir aber hier tun ist, wir machen das ein bisschen mehr so, wie 07:31.060 --> 07:33.980 wir es am Anfang bei der Diskussion, bei der ursprünglichen 07:33.980 --> 07:37.540 Vorstellung von Quicksort uns überlegt haben oder vorgestellt haben, 07:37.620 --> 07:40.480 nämlich verteilen das Ganze in drei verschiedene Blöcke ein. 07:41.880 --> 07:46.480 Das heißt, wir machen jetzt Ternäre-Vergleiche, also lauter Vergleiche 07:46.480 --> 07:47.800 mit drei möglichen Ausgängen. 07:49.920 --> 07:53.820 Bevor ich jetzt hier auf den Algorithmus eingehe, vielleicht schon mal 07:53.820 --> 07:57.760 auf der nächsten Folie so, dass man versteht, was passieren soll. 07:58.340 --> 08:01.820 Also gucken Sie jetzt hier vielleicht nur ganz unten diesen Block an. 08:01.880 --> 08:03.580 Das ist unser Ziel der Partitionierung. 08:03.700 --> 08:04.780 Wir partitionieren immer noch. 08:05.760 --> 08:08.520 Aber unser Ziel ist jetzt, dass am Ende drei Blöcke dastehen und nicht 08:08.520 --> 08:09.280 zwei. 08:10.460 --> 08:13.500 Also jetzt haben wir den Block von Elementen, die echt kleiner als P 08:13.500 --> 08:13.700 sind. 08:13.700 --> 08:16.300 Dann kommt ein ganzer Block von Elementen, die alle gleich P sind. 08:16.960 --> 08:20.820 Und in unserem Fall, wo wir komplett nur gleiche Elemente haben, wäre 08:20.820 --> 08:22.200 dieser Block dann halt natürlich alles. 08:22.440 --> 08:24.040 Dann wäre es das ganze Array A. 08:24.560 --> 08:27.360 Und dann gibt es einen dritten Block von Elementen, der steht rechts 08:27.360 --> 08:27.720 daneben. 08:27.860 --> 08:33.280 Das sind lauter Elemente, die sind echt größer P. Das ist unser Ziel. 08:34.440 --> 08:36.940 Und wenn wir das haben, dann kann man auch einsehen, dann wird das 08:36.940 --> 08:38.240 Problem halt auch ein bisschen einfacher. 08:38.400 --> 08:42.860 Dann haben wir kein grundsätzliches Problem mehr mit unbalancierten 08:42.860 --> 08:47.260 Blöcken, wenn wir nur gleiche Elemente haben. 08:47.360 --> 08:49.860 Dann haben wir zwar einen riesigen gleich P-Block in dem Fall. 08:50.520 --> 08:52.480 Das stört uns aber nicht, weil den müssen wir nicht mehr sortieren. 08:52.760 --> 08:53.680 Das ist nicht die Aufgabe. 08:54.900 --> 08:56.860 Also der gleich P-Block ist schon sortiert. 08:57.200 --> 09:00.120 Und da wir da nicht rekursiv absteigen, haben wir da kein Teilproblem 09:00.120 --> 09:01.300 mehr, was auf einmal riesig ist. 09:02.500 --> 09:05.000 Okay, also dann gucken wir uns nochmal kurz diese Variante an von 09:05.000 --> 09:05.380 Quicksort. 09:06.480 --> 09:07.440 Und die funktioniert so. 09:09.700 --> 09:12.080 Was wir tun, ist dasselbe wie vorher. 09:12.220 --> 09:14.200 Wir wählen erstmal ein Pivot-Element. 09:15.880 --> 09:18.880 In der zweiten Zeile ist jetzt vielleicht eine Änderung, die ganz 09:18.880 --> 09:19.560 interessant ist. 09:20.540 --> 09:22.340 Wir partitionieren jetzt in drei Blöcke. 09:23.140 --> 09:26.840 Und die Ausgabe von dieser Partitionierung ist, da es drei Blöcke 09:26.840 --> 09:30.320 sind, sind das jetzt auch zwei Schranken oder zwei Indizes von 09:30.320 --> 09:30.820 Übergängen. 09:31.640 --> 09:37.320 Dieses M ist der Index von dem Übergang des kleiner P-Blocks zu dem 09:37.320 --> 09:37.980 gleich P-Block. 09:39.060 --> 09:43.420 Und das M' ist der Index von dem Übergang des gleich P-Blocks zu dem 09:43.420 --> 09:44.560 größer P-Block. 09:46.080 --> 09:48.700 Und was wir dann tun müssen, ist wir müssen den linken Block von 09:48.700 --> 09:50.780 kleiner P-Elementen, die sind noch nicht sortiert, die müssen wir 09:50.780 --> 09:51.580 rekursiv sortieren. 09:51.840 --> 09:54.660 Den mittleren Block von gleich P-Elementen können wir... 09:54.660 --> 09:56.480 also der ist schon sortiert, da brauchen wir nichts mehr machen. 09:57.280 --> 09:58.680 Und dann sortieren wir den rechten Block. 09:58.680 --> 10:04.100 Und das sind die Blöcke von den Indizes L bis M minus 1, M plus 1 oder 10:04.100 --> 10:05.280 M' plus 1 bis R. 10:06.100 --> 10:07.760 Und wenn wir die sortiert haben, sind wir fertig. 10:09.500 --> 10:09.560 Okay? 10:12.520 --> 10:15.640 Gut, da will ich jetzt vielleicht nur mal ein bisschen grob drüber 10:15.640 --> 10:18.240 gehen über die Folie, weil eigentlich ist das jetzt so ein bisschen 10:19.260 --> 10:21.200 handwerkliche Arbeit, was wir da machen, aber das ist jetzt kein 10:21.200 --> 10:21.700 Tiefsinn. 10:21.780 --> 10:24.740 Man muss halt nur aufpassen, dass man keinen zusätzlichen Platz 10:24.740 --> 10:26.780 braucht und dass es einigermaßen schnell läuft. 10:28.040 --> 10:28.560 Also was passiert? 10:28.680 --> 10:34.220 Wir starten zunächst mal mit einer Folge, also wir starten mit I und J 10:34.220 --> 10:40.820 als Schranken für diese Blöcke kleiner P und größer P. Wie gehabt, da 10:40.820 --> 10:44.240 starten wir an der linken Schranke und am Anfang wird bei dieser 10:44.240 --> 10:47.640 Variablenbelegung I gleich R, J gleich L und K gleich R, da werden 10:47.640 --> 10:52.960 diese Zeiger I und J beide ganz links stehen und K wird ganz rechts 10:52.960 --> 10:53.200 stehen. 10:53.320 --> 10:56.960 Das heißt, alles was zwischen J und K steht, dieser Fragezeichenblock, 10:57.020 --> 10:59.700 der ist noch nicht bearbeitet, der ist noch nicht, naja, einsortiert 10:59.700 --> 11:02.500 ist jetzt das falsche Wort, also in diese drei Blöcke einsortiert, 11:02.560 --> 11:03.640 noch nicht vollständig sortiert. 11:03.980 --> 11:07.080 Das sind alle Elemente, die haben wir noch nicht eingeteilt und die 11:07.080 --> 11:10.100 sind dann am Ende, am Anfang sind das noch alle, bis auf das Pivot 11:10.100 --> 11:11.860 -Element, das steht ganz rechts. 11:14.900 --> 11:18.280 Okay, und was wir dann tun, ist, genauso wie bei der Partitionierung 11:18.280 --> 11:21.240 vorher, wir vergrößern oder vielmehr wir verkleinern diesen 11:21.240 --> 11:22.160 Fragezeichenblock. 11:23.100 --> 11:26.180 Das heißt, wir gucken uns das Element an, was jetzt an dieser, das 11:26.180 --> 11:29.320 erste Fragezeichen-Element, was bei J steht, und je nachdem, ob das 11:29.320 --> 11:33.420 dann gleich P ist, schieben wir das ganz nach rechts, also am Anfang 11:33.420 --> 11:36.740 stehen diese gleichen Elemente, der dritte Block, also der mittlere 11:36.740 --> 11:39.880 Block, der eigentlich in der Mitte stehen sollte am Ende, den schieben 11:39.880 --> 11:40.760 wir noch ganz nach rechts. 11:42.500 --> 11:45.900 Und wenn wir dann halt so ein Element für diesen Gleichblock haben, 11:46.560 --> 11:49.140 dann schieben wir das nach rechts durch so eine Swap-Operation und 11:49.140 --> 11:50.660 vergrößern diesen Gleichblock. 11:51.820 --> 11:53.080 Und ansonsten machen wir das wie gehabt. 11:53.300 --> 12:00.480 Das heißt, wir vergrößern in jedem Fall J und eventuell haben wir dann 12:00.480 --> 12:02.780 ein Element, was in diesen linken Block gehört, und das müssen wir 12:02.780 --> 12:04.860 dann durch einen Austausch an die richtigen Positionen bringen und 12:04.860 --> 12:05.620 dann I vergrößern. 12:06.440 --> 12:08.840 Also eigentlich ein bisschen mechanisch und passiert auch nicht so 12:08.840 --> 12:15.220 viel Spannendes mit einer einzigen zusätzlichen Fallunterscheidung. 12:15.320 --> 12:18.420 Und zwar, wenn wir Gleich-P-Elemente haben, dann schmeißen wir die auf 12:18.420 --> 12:21.060 einen neuen Haufen mit Gleich-P-Elementen ganz rechts. 12:21.740 --> 12:24.660 Wenn wir das haben, dann sind wir am Ende in so einer Situation, erst 12:24.660 --> 12:27.100 kommen die kleineren P-Elemente, dann die größeren P-Elemente und dann 12:27.100 --> 12:28.080 die Gleich-P-Elemente. 12:28.220 --> 12:34.060 Und das Letzte, was wir tun, ist, wir tauschen diesen Gleich-P-Block 12:34.060 --> 12:37.120 aus mit dem Block, der nach I steht. 12:38.300 --> 12:41.480 Und das machen wir durch so eine Fallunterscheidung, wo wir gucken, 12:41.700 --> 12:43.260 welche von diesen beiden Blöcken ist größer. 12:43.360 --> 12:48.240 Je nachdem, ob dieser größere P-Block größer ist oder der Gleich-P 12:48.240 --> 12:51.140 -Block größer, haben wir dann unterschiedlich viele Operationen oder 12:51.140 --> 12:55.580 eine obere Schranke für unsere Swap-Operationen. 12:55.940 --> 12:58.360 Also hier steht es als eine Swap-Operation, das ist aber ein ganzer 12:58.360 --> 12:59.060 Block jeweils. 12:59.420 --> 13:01.180 Also wir tauschen da ganze Blöcke aus. 13:02.220 --> 13:08.160 Und welche Blöcke wir austauschen, wie lang der Block ist, den wir 13:08.160 --> 13:11.160 austauschen, richtet sich danach, welcher von diesen beiden 13:11.160 --> 13:12.580 Teilblöcken hier größer ist. 13:13.680 --> 13:14.840 Und dann sind wir hier unten. 13:16.280 --> 13:17.520 Und da wollen wir eigentlich hin. 13:17.740 --> 13:19.960 Denn was wir jetzt tun, ist, wir können jetzt rekursiv den linken 13:19.960 --> 13:22.900 Block sortieren mit kleiner P-Elementen, dann rekursiv den rechten 13:22.900 --> 13:26.440 Block mit größer P-Elementen und dann sind wir fertig, dann haben wir 13:26.440 --> 13:27.000 alles sortiert. 13:28.700 --> 13:34.000 Das ist jetzt die letzte Variation zu QuickSort. 13:34.100 --> 13:34.880 Gibt es dazu Fragen? 13:38.600 --> 13:40.680 Also warum das nötig ist, oder warum das vielleicht in manchen 13:40.680 --> 13:43.500 Situationen eine gute Idee ist, was wir hier machen, mit so einem Drei 13:43.500 --> 13:47.560 -Wege -Vergleich oder so einer Drei-Wege-Einteilung und wie das 13:47.560 --> 13:48.020 funktioniert? 13:48.280 --> 13:48.800 Keine Fragen? 13:50.840 --> 13:52.000 Okay, gut. 13:53.780 --> 13:57.900 Mit QuickSort sind wir jetzt eigentlich durch, bis auf einen Vergleich 13:57.900 --> 13:59.720 mit MergeSort. 14:01.640 --> 14:05.940 Weil das zwei wichtige Algorithmen sind, die Vor- und Nachteile haben 14:05.940 --> 14:08.520 und es ist a priori gar nicht klar, welchen von beiden man nehmen 14:08.520 --> 14:08.800 sollte. 14:08.900 --> 14:12.400 Deshalb hier so eine Gegenüberstellung von positiven oder negativen 14:12.400 --> 14:15.080 Eigenschaften von QuickSort und MergeSort, die wir bis jetzt so 14:15.080 --> 14:15.680 betrachtet haben. 14:16.400 --> 14:19.980 Und was wir dann danach noch mit QuickSort machen, ist, wie schon 14:19.980 --> 14:23.040 gesagt, wir werden noch einen sehr verwandten Algorithmus mit 14:23.040 --> 14:24.400 QuickSort vorstellen. 14:24.840 --> 14:25.960 Aber zunächst mal zum Vergleich. 14:26.860 --> 14:31.040 Also das ist tatsächlich gar nicht so einfach zu sagen, was man jetzt 14:31.040 --> 14:31.980 verwenden sollte. 14:32.100 --> 14:33.160 QuickSort oder MergeSort. 14:33.400 --> 14:36.440 Und würde es einen Algorithmus geben, den man auf jeden Fall verwenden 14:36.440 --> 14:38.380 sollte, dann hätten wir halt nur den vorgestellt natürlich. 14:38.580 --> 14:40.740 Aber die haben halt beide individuelle Vor- und Nachteile. 14:41.500 --> 14:42.220 Was kann man sagen? 14:43.840 --> 14:49.640 MergeSort kann zum einen natürlich deterministisch in OVN-End-Log-End 14:49.640 --> 14:50.540 -Zeit sortieren. 14:50.640 --> 14:51.760 Das heißt, wir brauchen keinen Zufall. 14:51.820 --> 14:52.860 Wir haben echte Garantien. 14:52.860 --> 14:56.220 Wir haben die Garantie für den Fall, dass wir halt nach N-Log-N, also 14:56.220 --> 15:00.200 eine kleine Konstante mal N-Log-N vielen Schritten fertig sind, weil 15:00.200 --> 15:02.160 wir immer perfekt partitionieren. 15:03.140 --> 15:04.320 Wenn man das so nennen will. 15:04.400 --> 15:05.660 Wir teilen es einfach in der Mitte auf. 15:06.600 --> 15:08.960 Und sortieren dann Teilprobleme, die immer gleich groß sind. 15:09.040 --> 15:09.720 Zumindest ungefähr. 15:09.940 --> 15:10.600 Plus, minus eins. 15:12.500 --> 15:16.660 Und da könnte jetzt jemand sagen, der QuickSort toll findet, okay, in 15:16.660 --> 15:18.960 der Forschung, da gibt es auch deterministische Varianten. 15:18.960 --> 15:22.940 Dazu vielleicht später noch ein kurzer Ausblick, wie das funktionieren 15:22.940 --> 15:24.280 könnte oder wie das funktioniert. 15:26.300 --> 15:30.220 Also zumindest diese deterministische Schranke, die kriegt man auch 15:30.220 --> 15:31.080 bei QuickSort rein. 15:31.660 --> 15:35.160 Das einzige Problem dabei ist, QuickSort ist da so ein bisschen im 15:35.160 --> 15:40.060 Nachteil, weil die Konstanten für die Laufzeit, die sind schlechter. 15:40.220 --> 15:43.520 Tatsächlich kriegt man es auch bei QuickSort in N-Log-N plus OVN 15:43.520 --> 15:49.320 -Elementvergleichen hin, was schon nah an der Schranke ist. 15:49.440 --> 15:52.540 Aber die Konstanten in diesem O, die sind halt ziemlich schlecht. 15:53.520 --> 15:54.340 Warum sind die schlecht? 15:54.440 --> 15:55.220 Oder wo kommt das her? 15:56.140 --> 15:59.040 Also wenn man sich überlegt, dass man bei QuickSort das Problem hat, 15:59.260 --> 16:03.360 dass man ein Problem der Größe N in zwei Teilprobleme aufteilt. 16:03.480 --> 16:05.980 Und das Hauptproblem ist, dass die nicht balanciert sein könnten. 16:06.100 --> 16:08.760 Es könnte sein, dass die sehr ungleichmäßig sind. 16:08.820 --> 16:10.020 Und dann kriegt man eine lange Laufzeit. 16:11.160 --> 16:14.780 Dann kann man einfach mehr Zeit investieren, um eine gute Aufteilung 16:14.780 --> 16:15.320 zu finden. 16:15.720 --> 16:18.120 In dem konkreten Fall heißt das, man kann mehr Zeit investieren, um 16:18.120 --> 16:19.380 dieses Pivot-Element zu suchen. 16:19.820 --> 16:23.740 Man möchte gerne ein Pivot-Element haben, sodass dieses Pivot-Element 16:24.320 --> 16:27.600 ungefähr ein Median ist, also so ein Element, was in der Mitte liegt, 16:27.680 --> 16:28.460 in der sortierten Folge. 16:30.400 --> 16:32.520 Wenn man da mehr Zeit investiert, dann dauert das länger. 16:32.600 --> 16:35.100 Das führt dann zu einer größeren Konstante bei diesem OVN. 16:35.920 --> 16:40.840 Aber man kriegt es dann auch wirklich in N-Log-N plus OVN hin. 16:44.720 --> 16:48.380 Ein weiterer Vorteil, den Merge Sort noch hat, Merge Sort ist stabil. 16:48.760 --> 16:54.840 Stabilität heißt, in der sortierten Folge sind Elemente, die gleich 16:54.840 --> 16:58.000 sind, also die den gleichen Key haben, der Key, nach dem wir 16:58.000 --> 17:01.260 sortieren, die wir vergleich halten, sind die auch in derselben 17:01.260 --> 17:03.560 Reihenfolge, in der sie in der ursprünglichen Folge waren. 17:03.940 --> 17:08.520 Also wenn sie nur über einen kurzen Key sortieren, dann kann es sein, 17:09.260 --> 17:12.900 dass sie nachher auch möchten, dass die Elemente in derselben 17:12.900 --> 17:14.540 Reihenfolge wie vorher da stehen. 17:14.620 --> 17:17.920 Eine Anwendung sehen wir am Ende dieser oder vielmehr am Anfang der 17:17.920 --> 17:24.960 nächsten Vorlesung, wo Stabilität einfach ein wichtiges Tool ist, um 17:24.960 --> 17:27.080 schneller als N-Log-N zu sortieren. 17:28.500 --> 17:30.360 Und vielleicht hat Ihre Anwendung auch die Eigenschaft, dass Sie auf 17:30.360 --> 17:32.620 keinen Fall Elemente, die gleich sind, durcheinander bringen wollen. 17:34.240 --> 17:35.820 Bei Merge Sort geht es ganz einfach. 17:35.940 --> 17:39.660 Da folgt es natürlich aus dem Mischalgorithmus, so wie wir das 17:39.660 --> 17:40.260 definiert haben. 17:41.840 --> 17:46.900 Bei QuickSort geht es auch, wenn wir diese etwas naive, diesen ersten 17:46.900 --> 17:49.680 Versuch von QuickSort nehmen, wo wir neue Folgen bilden und das Ganze 17:49.680 --> 17:50.620 nicht in einem Array machen. 17:51.460 --> 17:54.300 Wenn Sie diese In-Place-Eigenschaft, dass alles in demselben Array 17:54.300 --> 17:57.260 stattfinden soll, aufgeben, geht es recht einfach. 17:57.540 --> 18:00.700 Auch da können Sie dann halt einfach neue Folgen bilden und diese 18:00.700 --> 18:05.180 neuen Folgen dann halt getrennt bearbeiten und nachher wieder 18:05.180 --> 18:05.880 aneinander fügen. 18:06.700 --> 18:10.260 Der Grund, weshalb QuickSort in unserer Implementierung, in der In 18:10.260 --> 18:13.460 -Place -Implementierung, keine Stabilität hat, ist, dass wir hin und 18:13.460 --> 18:15.780 her Elemente vertauschen und das kreuz und quer. 18:16.240 --> 18:20.300 Und da können auch Elemente vertauscht werden, also Elemente in 18:20.300 --> 18:22.960 unterschiedliche Positionen gebracht werden, in unterschiedliche 18:22.960 --> 18:24.980 relative Positionen, die halt gleich sind. 18:25.440 --> 18:28.440 Also wie gesagt, das, was wir getan haben, das basiert, wegen dieser 18:28.440 --> 18:31.440 In -Place-Eigenschaft, also man sieht es ja auch hier, ganz viel auf 18:31.440 --> 18:34.400 Vertauschungsoperationen und die bringen so eine Stabilität 18:34.400 --> 18:34.920 durcheinander. 18:36.760 --> 18:39.980 Okay, das spricht jetzt alles ziemlich für Merge Sort, aber QuickSort 18:39.980 --> 18:42.980 hat einen sehr großen Vorteil. 18:43.080 --> 18:45.820 QuickSort kann nämlich In-Place implementiert werden oder Fast In 18:45.820 --> 18:46.120 -Place. 18:47.120 --> 18:47.820 Also warum Fast? 18:48.880 --> 18:52.240 Fast, weil wir immer noch diesen rekursiven Abstieg haben und wir 18:52.240 --> 18:55.700 müssen halt zumindest mal von Log N viele Elemente auf den Stapel 18:55.700 --> 18:55.920 nehmen. 18:57.000 --> 18:59.660 Aber davon abgesehen ist QuickSort In-Place. 18:59.800 --> 19:01.380 Das heißt, wir brauchen keinen extra Platz. 19:01.580 --> 19:03.380 Und da haben wir auch Implementierungen gesehen, die das können. 19:05.260 --> 19:08.640 Und das macht es zum einen schneller, eventuell cache-effizienter, je 19:08.640 --> 19:11.120 nachdem, wie ihr Cache ausgelegt ist. 19:13.040 --> 19:15.600 Und natürlich offensichtlich brauchen sie auch weniger Platz. 19:15.760 --> 19:16.920 Sie brauchen keine neuen Folgen. 19:16.920 --> 19:20.440 Wer weiß, wo sie die im Speicher reservieren müssen für neue Elemente, 19:20.460 --> 19:21.840 wie bei Merge Sort, für neue Folgen. 19:22.600 --> 19:24.020 Und das kriegt man auch in Merge Sort. 19:24.100 --> 19:25.980 Da hat Merge Sort jetzt nicht so viel zu zu sagen. 19:26.540 --> 19:31.820 Also man kriegt es mit weniger Extra-Platz hin, dass man nicht O von N 19:31.820 --> 19:34.420 Extra -Platz braucht, sondern nur, also natürlich braucht man immer 19:34.420 --> 19:38.480 noch O von N, aber dass man sowas wie N Viertel viele Elemente an 19:38.480 --> 19:39.860 Extra -Platz braucht. 19:40.280 --> 19:43.680 Aber so ganz weg kriegt man diesen Extra-Platz nicht bei Merge Sort. 19:47.550 --> 19:51.330 Okay, und dann gibt es vielleicht noch das Argument, vielleicht 19:51.330 --> 19:55.210 aufgrund dieser In-Place-Eigenschaft ist QuickSort oft als schneller 19:55.210 --> 19:57.330 empfunden oder empfohlen. 19:59.290 --> 20:04.470 Das ist jetzt vielleicht keine so richtig harte Aussage und ich kann 20:04.470 --> 20:05.450 es auch nicht wirklich belegen. 20:06.510 --> 20:09.550 Das Problem ist, diese Aussage, QuickSort ist schneller, ist 20:09.550 --> 20:11.870 vielleicht eine Aussage gemittelt über alle Anwendungsfälle, die man 20:11.870 --> 20:12.510 so erlebt hat. 20:13.450 --> 20:15.130 Das heißt, es hängt von vielen Dingen ab. 20:15.130 --> 20:18.250 Wie gesagt, wie ist die Größe der Elemente? 20:18.790 --> 20:20.710 Wie teuer ist es, extra Speicher anzulegen? 20:20.810 --> 20:22.110 Welche Speicherverwaltung nutzen Sie? 20:22.950 --> 20:25.470 Was brauchen Sie hier noch an Stabilitätseigenschaften? 20:25.570 --> 20:27.710 Müssen Sie womöglich diese In-Place-Eigenschaft aufgeben von 20:27.710 --> 20:28.130 QuickSort? 20:28.570 --> 20:29.750 Das hängt von ganz vielen Dingen ab. 20:29.890 --> 20:31.050 Wie teuer ist ein Elementvergleich? 20:33.910 --> 20:36.190 Also das ist, wie gesagt, eine vage Aussage. 20:36.270 --> 20:38.110 Das ist deshalb auch ein Fragezeichen versehen. 20:42.490 --> 20:46.550 Okay, also das sind so die beiden Algorithmen im Vergleich. 20:48.170 --> 20:49.310 Gibt es dazu Fragen? 20:53.490 --> 20:56.270 Also das ist auch so eine beliebte Klausuraufgabe. 20:57.630 --> 21:00.970 Versuchen Sie mal, oder nennen Sie mal Vorteile von MergeSort 21:00.970 --> 21:02.630 gegenüber QuickSort oder umgekehrt. 21:03.290 --> 21:08.270 Nennen Sie Vorteile jeweils von diesen Algorithmen im Vergleich und 21:08.270 --> 21:09.630 vielleicht auch nicht nur MergeSort und QuickSort. 21:09.750 --> 21:10.510 Vielleicht kann man sich da auch noch einige Fragen stellen. 21:11.350 --> 21:14.130 Also wir werden noch einen zumindest mal kennenlernen, einen 21:14.130 --> 21:19.830 Sortieralgorithmus in diesem Kapitel und auch noch einen später. 21:20.170 --> 21:22.270 Also wir werden eigentlich noch mehrere kennenlernen. 21:24.670 --> 21:29.150 Okay, dann zu unserem nächsten Problem. 21:31.150 --> 21:34.650 Und wie ich schon gesagt habe, die Idee ist jetzt, dass wir die 21:34.650 --> 21:37.910 Techniken, die wir bei QuickSort kennengelernt haben, zum einen 21:37.910 --> 21:41.090 anwenden, um ein anderes Problem zu lösen und zwar überraschend 21:41.090 --> 21:41.410 schnell. 21:42.890 --> 21:45.590 Und zum anderen ist es aber auch eine Anwendung, die wieder in 21:45.590 --> 21:46.990 QuickSort verwendet werden kann. 21:49.650 --> 21:50.930 Okay, also was ist das Problem? 21:51.170 --> 21:55.630 Zunächst mal das Problem, das wir lösen wollen, ist, dass wir ein 21:55.630 --> 21:58.670 Element von einem bestimmten Rang finden wollen. 21:58.770 --> 22:00.110 Was ist ein Rang von einem Element? 22:00.830 --> 22:04.110 Also ein Rang von einem Element ist immer nur ein Rang von einem 22:04.110 --> 22:05.330 Element in einer bestimmten Folge. 22:05.330 --> 22:09.830 Also wir haben eine Folge von Elementen S, S wie Sequence. 22:11.010 --> 22:12.710 Und da stehen lauter solche Elemente E drin. 22:13.990 --> 22:19.010 Und der Rang von einem Element, der Rang K von einem Element E in so 22:19.010 --> 22:22.790 einer Folge, das ist die Position von E in der sortierten Folge. 22:23.610 --> 22:26.850 Das heißt, es ist völlig egal, wo E in der Folge erstmal steht. 22:27.090 --> 22:29.450 Wichtig ist nur, wo E in der sortierten Folge stehen würde. 22:32.230 --> 22:34.510 Den Rang von einem Element können wir zum Beispiel ganz einfach 22:34.510 --> 22:37.010 berechnen, indem wir die Folge sortieren und dann gucken, wo steht es 22:37.010 --> 22:37.170 denn. 22:39.390 --> 22:45.210 Frage, dieser Rang ist, wenn wir das so definieren, zumindest mit 22:45.210 --> 22:48.870 unserer Definition von sortierter Folge, noch nicht eindeutig 22:48.870 --> 22:49.310 bestimmt. 22:49.910 --> 22:50.310 Warum nicht? 22:52.570 --> 22:52.910 Eine Idee? 22:53.530 --> 22:54.130 Ja, 23:05.480 --> 23:05.480 genau. 23:08.140 --> 23:09.120 Richtige Antwort. 23:09.940 --> 23:11.300 Ich wiederhole es nochmal. 23:12.300 --> 23:15.740 Das Problem ist, Sie wissen nicht, an welcher Stelle in der sortierten 23:15.740 --> 23:18.400 Folge das genau steht, wenn Sie mehrere gleiche Elemente haben. 23:18.500 --> 23:20.140 Es gibt dann mehrere sortierte Folgen. 23:21.100 --> 23:24.560 Also die sortierte Folge ist auch nicht eindeutig bestimmt, sondern 23:24.560 --> 23:27.340 sie ist nur eine mögliche Sortierung dieser Folge. 23:28.260 --> 23:30.560 Und wenn Sie gleiche Elemente haben, wie gesagt, dann gibt es viele 23:30.560 --> 23:31.020 mögliche. 23:31.020 --> 23:35.980 Und wenn E eines von diesen gleichen Elementen ist, dann ist auch die 23:35.980 --> 23:38.020 Position in der sortierten Folge nicht eindeutig. 23:38.240 --> 23:40.060 Da machen wir gleich noch ein Beispiel dazu. 23:41.020 --> 23:46.640 Ein bisschen abstrakter ausgedrückt, was wir tun wollen, ist eine 23:46.640 --> 23:54.120 Funktion Select implementieren, die uns bei einem gegebenen K, also 23:54.120 --> 23:59.800 bei einem gegebenen Rang, ein Element des Ranges K gibt. 24:01.660 --> 24:03.640 Da kann man sich mehrere Fragen stellen. 24:04.500 --> 24:05.340 Warum ist das gut? 24:05.620 --> 24:06.820 Oder warum braucht man das? 24:06.900 --> 24:07.720 Wozu ist es nützlich? 24:08.200 --> 24:10.840 Und die zweite Frage ist, wie kriegt man das möglichst schnell hin? 24:13.160 --> 24:14.660 Vielleicht noch eine kleine Bemerkung. 24:15.140 --> 24:17.520 Es gibt verschiedene Definitionen von Rang in der Literatur. 24:17.640 --> 24:20.020 Da kann es zum Beispiel sein, dass die doppelte Elemente oder 24:20.020 --> 24:21.520 mehrfache Elemente gar nicht zählen. 24:22.800 --> 24:25.620 Oder es kann auch sein, dass Sie eine stabile Sortierung hier oben 24:25.620 --> 24:27.720 fordern und da ist der Rang auf einmal eindeutig bestimmt. 24:29.620 --> 24:33.420 Was wir hier tun, ist eine Definition, wo es mehrere mögliche 24:33.420 --> 24:34.400 Antworten gibt. 24:35.800 --> 24:40.540 Sie könnten hier bei einem Select-Aufruf mehrere mögliche Elemente 24:40.540 --> 24:41.120 zurückkriegen. 24:42.120 --> 24:43.000 Bei demselben K. 24:46.920 --> 24:47.400 Beispiel. 24:48.600 --> 24:51.440 Wir haben hier eine Folge, das sind die Nachkommestellen von Pi. 24:52.820 --> 24:56.140 Und wenn wir die sortieren, dann hat die diese Form. 24:56.140 --> 24:59.300 1, 2, 3, 3, 4, 5, 5, 5, 6, 8, 9. 25:00.680 --> 25:05.840 Und die verschiedenen Elemente, da gibt es jetzt mehrere mögliche 25:05.840 --> 25:07.040 Ränge dieser Elemente. 25:07.560 --> 25:09.320 Also die 1 hat immer den Rang 1. 25:09.940 --> 25:11.780 Weil sie in der sortierten Folge als erstes steht. 25:14.220 --> 25:15.020 Das ist relativ laut. 25:16.600 --> 25:17.900 Es ist langweilig. 25:17.960 --> 25:18.700 Gibt es Fragen? 25:18.960 --> 25:23.480 Oder ist es so, dass Sie nicht mitkommen? 25:24.240 --> 25:25.460 Geben Sie mir eine Rückmeldung. 25:31.100 --> 25:31.220 Okay. 25:34.060 --> 25:35.940 Für die 2 gibt es auch nur eine Möglichkeit. 25:36.100 --> 25:37.340 Die steht immer an der zweiten Position. 25:37.640 --> 25:41.680 Aber das Interessante ist jetzt vielleicht, die 3, da gibt es zwei 25:41.680 --> 25:42.280 Möglichkeiten. 25:43.000 --> 25:47.600 Und wenn ich Sie frage nach einem Element des Ranges 3 oder 4. 25:49.560 --> 25:50.440 Oder umgekehrt. 25:50.600 --> 25:53.140 Wenn Sie fragen, welchen Rang hat denn das Element 3? 25:55.300 --> 25:58.180 Dann kann die Antwort 3 oder die Antwort kann auch 4 sein. 25:58.680 --> 26:02.360 Und genauso, wenn ich Sie frage, welchen Rang hat das Element 5? 26:02.460 --> 26:04.300 Da kann die Antwort auch 6, 7 oder 8 sein. 26:05.080 --> 26:09.700 Und wenn ich Sie danach frage, ein Element zurückzugeben, das den Rang 26:09.700 --> 26:10.860 7 hat zum Beispiel. 26:11.480 --> 26:14.480 Dann wäre jede dieser 5, wenn Sie die irgendwie noch unterscheiden 26:14.480 --> 26:16.860 können, dann wäre jede dieser 5 eine gültige Antwort. 26:19.180 --> 26:19.280 Okay. 26:20.300 --> 26:23.560 Also damit möchte ich nur erklären, es gibt hier Mehrdeutigkeiten und 26:23.560 --> 26:24.820 wie sind die beschaffen. 26:24.940 --> 26:26.620 Und wir machen es hier eigentlich relativ einfach. 26:27.140 --> 26:29.340 Bei der Definition von dem Problem. 26:31.800 --> 26:31.920 Okay. 26:33.460 --> 26:35.500 Also zunächst mal die Frage, warum braucht man das? 26:37.520 --> 26:39.860 Ein wichtiger Spezialfall ist die Median-Auswahl. 26:40.240 --> 26:40.380 Warum? 26:41.280 --> 26:43.820 Der Median ist das Element, was in der sortierten Folge in der Mitte 26:43.820 --> 26:44.140 steht. 26:44.140 --> 26:45.500 Also irgendwie gerundet natürlich. 26:47.380 --> 26:51.460 Zum einen ist der Median in der Statistik auch ein guter Ersatz für 26:51.460 --> 26:52.880 den Mittelwert, der stabiler ist. 26:53.960 --> 26:54.980 Das ist so eine Anwendung. 26:56.620 --> 27:00.140 Stellen Sie sich vor, Sie berechnen das mittlere Einkommen von einem 27:00.140 --> 27:05.440 Dorf, von Leuten, die in einem Dorf wohnen und Sie berechnen das mit 27:05.440 --> 27:08.000 dem Mittelwert und Sie berechnen aber auch den Median. 27:08.760 --> 27:11.880 Dann ist der Median in dem Sinne stabiler, wenn jetzt Bill Gates in 27:11.880 --> 27:16.100 das Dorf zieht, dann kann es sein, dass der Mittelwert auf einmal sehr 27:16.100 --> 27:19.680 stark abweicht oder sehr stark sich verändert. 27:20.660 --> 27:25.420 Der Median aber, das ist quasi in der Sortierung das Einkommen 27:25.420 --> 27:29.500 desjenigen, der ungefähr in der Mitte ist, der ist stabiler. 27:29.620 --> 27:34.880 Also da wird sich höchstwahrscheinlich das Einkommen von jemandem, der 27:34.880 --> 27:37.980 so mittelfiel verdient, nicht groß ändern. 27:39.060 --> 27:46.500 Also wie gesagt, deshalb ein etwas robusteres oder stabilere Form oder 27:46.500 --> 27:49.800 Ersatz für den Erwartungswert in der Statistik und eine konkrete 27:49.800 --> 27:53.280 technische Anwendung dafür wäre auch, dass wir in dem QuickSort 27:53.280 --> 27:57.220 -Algorithmus, wenn wir da den Median effizient wählen können, dann 27:57.220 --> 28:02.100 können wir auch in deterministischer Zeit N log N oder O von N log N 28:02.100 --> 28:02.540 sortieren. 28:03.880 --> 28:07.500 Einfach weil, wenn wir den Median kennen, dann können wir als Pivot 28:07.500 --> 28:14.460 -Element den Median nehmen und mit dem partizinieren wir dann perfekt. 28:14.800 --> 28:16.640 Also mit dem partizinieren wir dann genau balanciert. 28:16.960 --> 28:18.040 Und das können wir immer wieder machen. 28:18.460 --> 28:20.840 Dazu muss man natürlich eine effiziente Methode haben, um diesen 28:20.840 --> 28:21.720 Median zu bestimmen. 28:23.500 --> 28:28.360 Man kann das auch verallgemeinern und dann interessiert sie halt ein 28:28.360 --> 28:34.820 typischer Repräsentant in einem bestimmten Quantil. 28:34.820 --> 28:38.520 Also dass sie sagen, sie möchten jemanden haben, der typischerweise, 28:38.800 --> 28:43.040 also ein typischer Repräsentant von einem mittleren Einkommen ist, von 28:43.040 --> 28:44.720 einem hohen Einkommen, von einem niedrigen Einkommen. 28:45.460 --> 28:47.620 Und dass sie da halt nicht nur einen Durchschnitt berechnen, weil der 28:47.620 --> 28:50.640 nicht so stabil ist, sondern dass sie das dann halt auch mit einem 28:50.640 --> 28:54.300 Rang oder mit einem Auswahlproblem machen. 28:56.000 --> 28:57.980 Das gibt ihnen halt auch wieder stabilere Werte. 29:01.820 --> 29:04.060 Okay, also das sollte so ein bisschen motivieren, warum das eine gute 29:04.060 --> 29:05.040 Idee ist, das zu berechnen. 29:05.180 --> 29:08.160 Also wenn alles andere nicht ausreicht, kann man immer noch sagen, wir 29:08.160 --> 29:10.400 wollen Quicksort effizienter kriegen, dazu müssen wir den Median 29:10.400 --> 29:11.780 berechnen. 29:13.880 --> 29:16.440 So, und die Lösung, also die nächste Frage ist, wie kriegt man das 29:16.440 --> 29:16.640 hin? 29:17.300 --> 29:21.500 Und da ist die Lösung, man kann das zum Beispiel mit so einer Variante 29:21.500 --> 29:28.320 von Quicksort machen, die ein bisschen effizienter ist, weil sie nur 29:28.320 --> 29:29.920 sehr selektiv absteigt. 29:31.160 --> 29:35.340 Also, angenommen, Sie möchten den Median bestimmen, das Einfachste 29:35.340 --> 29:36.460 ist, die Folge zu sortieren. 29:38.020 --> 29:40.120 Aber wenn Sie die Folge sortieren, dann haben Sie schon eine 29:40.120 --> 29:41.500 Komplexität von N log N. 29:41.660 --> 29:44.880 Das wäre zum Beispiel für Quicksort, um das zu benutzen in Quicksort, 29:44.960 --> 29:46.320 wieder nicht so prickelnd. 29:46.400 --> 29:47.620 Außerdem, Sie wollen ja gerade sortieren. 29:48.980 --> 29:53.400 Das heißt, was man tun kann, ist stattdessen, man sortiert so intuitiv 29:53.400 --> 29:55.920 die Folge nur da, wo es sie auch interessiert. 29:57.500 --> 30:00.580 Also es könnte sein, wenn Sie zum Beispiel das kleinste Element oder 30:00.580 --> 30:04.040 ein Element, das nahe bei den kleinsten Elementen ist, das also einen 30:04.040 --> 30:08.160 niedrigen Rang hat, wenn Sie nur das interessiert, dann müssen Sie 30:08.160 --> 30:10.920 beispielsweise die rechte Hälfte von dieser ganzen Folge eigentlich 30:10.920 --> 30:11.580 gar nicht angucken. 30:11.940 --> 30:14.060 Sie müssen nur wissen, wo die rechte Hälfte anfängt. 30:15.280 --> 30:17.720 Das heißt, was wir tun ist, wir lassen einfach den Quicksort 30:17.720 --> 30:22.860 -Algorithmus laufen, aber steigen nur da rekursiv ab, wo es uns auch 30:22.860 --> 30:23.380 interessiert. 30:24.420 --> 30:25.460 Also was bedeutet das? 30:25.540 --> 30:26.160 Wir fangen mal an. 30:26.320 --> 30:29.080 Für einen Augenblick können Sie vielleicht diese If-Abfragen mal kurz 30:29.080 --> 30:29.600 ignorieren. 30:30.520 --> 30:32.680 Wenn Sie das tun, dann steht hier im Wesentlichen der 30:32.680 --> 30:36.020 Partitionierungsschritt erstmal von dem Quicksort-Algorithmus. 30:36.340 --> 30:39.200 Das heißt, wir teilen das ein in so drei Töpfe A, B, C. 30:40.080 --> 30:44.120 Wir wählen erstmal ein Pivot-Element und diese Töpfe A, B, C sind dann 30:44.120 --> 30:47.140 so definiert, in A sind alle Elemente kleiner Pivot drin, in C alle 30:47.140 --> 30:50.260 größer Pivot, in den B sind alle die Elemente drin, die gleich dem 30:50.260 --> 30:51.060 Pivot -Element sind. 30:51.960 --> 30:58.240 Okay, das haben Sie jetzt gemacht und wenn Sie jetzt sich überlegen, 30:58.400 --> 31:04.840 Sie möchten jetzt ein Element vom Rang K finden, dann müssen Sie 31:04.840 --> 31:07.800 eigentlich nur wissen, ist K irgendwo eine Zahl, die einen Index 31:07.800 --> 31:10.640 angibt in diesem ersten Block, in diesem zweiten Block oder in dem 31:10.640 --> 31:11.120 dritten Block. 31:12.020 --> 31:14.360 Also diese Zeile unten, auf der ich im Moment zeige, das ist ein 31:14.360 --> 31:16.980 Beispiel dafür, dass K halt relativ groß ist. 31:17.580 --> 31:22.240 Das heißt, das muss irgendein Element sein in diesem dritten Block. 31:22.860 --> 31:25.880 Also Sie wissen, die Grenzen dieser Blöcke untereinander, die würden 31:25.880 --> 31:27.460 sich im weiteren Sortieren nicht verschieben. 31:27.820 --> 31:31.900 A und C sind noch unsortiert, also B ist trivialerweise sortiert, da 31:31.900 --> 31:35.120 nur gleiche Elemente drin sind, A und C sind noch unsortiert, also Sie 31:35.120 --> 31:38.480 wissen nicht genau, welches Element da einen Rang K hätte, aber in dem 31:38.480 --> 31:43.320 Beispiel, da könnten Sie sich schon abzählen, dieses K muss irgendwo 31:43.320 --> 31:44.460 im dritten Block drin liegen. 31:44.460 --> 31:48.540 Und genauso, wenn K klein ist, würde das halt schon im ersten Block 31:48.540 --> 31:49.260 irgendwo drin liegen. 31:50.380 --> 31:53.940 Und was Sie jetzt tun ist, Sie sortieren die Folge mit QuickSort oder 31:53.940 --> 31:56.440 naja, nicht wirklich mit QuickSort, sondern mit so einer Art einseitig 31:56.440 --> 32:00.920 mit QuickSort weiter, aber Sie steigen nur da ab, hier in diesem Teil 32:00.920 --> 32:05.420 halt in C, wo es Sie auch interessiert und berechnen halt, welches das 32:05.420 --> 32:07.480 Element ist, auf das dieses K da zeigt. 32:09.160 --> 32:10.700 Okay, ein bisschen konkreter, was heißt das? 32:10.700 --> 32:12.740 Jetzt kommen wir zu den IF-Abfragen. 32:14.640 --> 32:18.920 Angenommen, Sie finden erst mal diese erste Einteilung, Sie finden 32:18.920 --> 32:22.820 diesen ersten Block, und der hat schon so viele Elemente, dass da ein 32:22.820 --> 32:24.380 Element vom Rang K drin sein muss. 32:24.940 --> 32:28.760 Das heißt, K ist kleiner gleich der Größe oder der Länge von A. 32:29.740 --> 32:32.960 Was Sie dann tun müssen ist, Sie müssen einfach nur rekursiv absteigen 32:32.960 --> 32:33.940 auf diesem ersten Block. 32:34.100 --> 32:36.060 Sie haben gerade Ihr Problem schon, die Größe des Problems 32:36.060 --> 32:36.580 verkleinert. 32:38.500 --> 32:41.120 Das heißt, was jetzt mit C oder B passiert, das müssen Sie gar nicht 32:41.120 --> 32:42.960 mehr ausrechnen, das interessiert jetzt gar nicht mehr. 32:44.200 --> 32:46.620 Und das heißt, da steigen Sie einfach rekursiv ab. 32:47.720 --> 32:54.460 Wenn Sie herausfinden, dass dieser Index K, der liegt irgendwo in der 32:54.460 --> 33:02.040 B -Menge, in dem Sinne, dieses K ist größer als die Größe von A, es 33:02.040 --> 33:04.120 ist aber kleiner gleich der Größe von A plus B. 33:04.120 --> 33:05.820 Das heißt, es muss irgendwo in der Mitte sein. 33:06.840 --> 33:09.680 Dann wissen Sie, das muss ein Element sein, das gleich dem Pivot ist 33:09.680 --> 33:10.940 und Sie können den Pivot zurückgeben. 33:11.500 --> 33:14.120 Denn Sie wissen, der Pivot könnte in der Sortierung an genau dieser 33:14.120 --> 33:14.880 Stelle K stehen. 33:15.260 --> 33:15.920 Dann sind Sie fertig. 33:17.360 --> 33:20.120 Und die dritte Möglichkeit ist, das ist das Einzige, was jetzt noch 33:20.120 --> 33:23.260 übrig bleibt, jetzt muss dieses K, also irgendein Element in diesem 33:23.260 --> 33:24.280 Block C sein. 33:24.780 --> 33:26.060 Das heißt, dann finden Sie den Block C. 33:26.060 --> 33:30.000 Und jetzt ein kleines bisschen müssen Sie aufpassen, diesen Index 33:30.000 --> 33:31.620 hier, den müssen Sie anpassen. 33:31.760 --> 33:34.960 Das heißt, jetzt interessiert Sie eigentlich nicht, wie sieht ein 33:34.960 --> 33:40.100 Element vom Rang K in Block C aus oder in der Unterfolge, die C ist, 33:40.620 --> 33:42.860 sondern Sie müssen natürlich den Index hier anpassen. 33:43.040 --> 33:45.440 Das heißt, Sie ziehen da das, was links davon steht, ab. 33:46.720 --> 33:48.240 Also wir gucken das auch noch mal an, Beispiel an. 33:48.320 --> 33:49.280 Gibt es bis dahin Fragen? 33:53.800 --> 33:55.740 Dann wird es am Beispiel hoffentlich klar. 33:57.540 --> 34:00.120 Also das ist unsere Folge am Anfang, wieder die Nachkommastellen von 34:00.120 --> 34:01.440 Pi, das ist noch unsortiert. 34:02.900 --> 34:07.180 Und wir suchen ein Element von Rang 6, also K gleich 6. 34:08.380 --> 34:11.700 Und dann wählen wir als erstes Mal als Pivot, das ist jetzt nicht 34:11.700 --> 34:14.100 weiter wichtig, wie, oder wir können uns vorstellen, das wäre zufällig 34:14.100 --> 34:17.080 gewählt, wählen wir diese zwei hier. 34:17.080 --> 34:22.380 Dann teilen wir, wir partitionieren diese Menge S, diese Folge. 34:23.360 --> 34:25.860 Die partitionieren wir in unsere drei Töpfe, also A, B, C. 34:26.420 --> 34:28.480 Kleiner Pivot, Gleich Pivot, Größer Pivot. 34:29.380 --> 34:33.040 Und dann stellen wir raus, ich suche ein Element vom Rang 6, das muss 34:33.040 --> 34:36.240 also irgendwo in diesem dritten Topf hier, in dieser dritten Folge C 34:36.240 --> 34:36.780 drin liegen. 34:38.800 --> 34:41.500 Jetzt weiß ich aber, die ersten beiden Elemente, die stehen auf jeden 34:41.500 --> 34:42.520 Fall vor der Folge C. 34:42.520 --> 34:47.040 Das heißt, ich suche in C jetzt kein Element mehr des Ranges 6, 34:47.300 --> 34:48.800 sondern ein Element vom Rang 4. 34:48.920 --> 34:50.700 Das heißt, ich ziehe, was hier vorne ist, ab. 34:51.900 --> 34:56.820 Mein einziger rekursiver Aufruf ist dann dieser Select-Aufruf mit K 34:56.820 --> 34:58.300 gleich 4 und der Folge C. 34:59.860 --> 35:02.460 Dann wähle ich wieder ein Pivot-Element, sagen wir diesmal ist es die 35:02.460 --> 35:02.700 6. 35:03.320 --> 35:05.960 Dann teile ich das wieder ein in meine Folgen, kleiner, gleich, 35:06.180 --> 35:07.240 größer, den Pivot. 35:07.640 --> 35:12.760 Und dann stellt sich heraus, jetzt muss mein Element vom Rang 4 in der 35:12.760 --> 35:15.640 ersten Folge liegen, da die erste Folge mindestens vier Elemente hat. 35:16.820 --> 35:19.560 Dann mache ich wieder einen rekursiven Aufruf auf der kleineren Folge, 35:19.760 --> 35:23.120 die jetzt vorher A war, und die schreibe ich dann nach links und suche 35:23.120 --> 35:26.200 wieder ein Element vom Rang 4, wähle ein Pivot-Element, das ist 35:26.200 --> 35:30.420 diesmal 5, und auf einmal stelle ich fest, dieses Element vom Rang 4 35:30.420 --> 35:31.160 muss in B sein. 35:31.940 --> 35:34.960 Das heißt, jetzt kann ich irgendein Element, was gleich dieser 5 ist, 35:35.060 --> 35:35.460 zurückgeben. 35:36.680 --> 35:37.080 Also z.B. 35:37.240 --> 35:39.200 genau das Pivot-Element, was ich mir ausgesucht habe. 35:41.400 --> 35:41.900 Okay, Fragen? 35:43.580 --> 35:43.740 Ja? 35:54.790 --> 35:57.150 Die Frage ist, kann man das Pivot-Element irgendwie schlauer wählen? 35:57.270 --> 35:59.190 Ich habe ja eigentlich gar nicht gesagt, wie man das Pivot-Element 35:59.190 --> 35:59.930 jetzt hier wählt. 36:00.010 --> 36:02.050 Ich habe jetzt hier gesagt, stellen Sie sich vor, zufällig. 36:03.970 --> 36:07.850 An der Stelle ist es halt so, die ideale Wahl für ein Pivot-Element 36:07.850 --> 36:12.290 wäre eigentlich der Median, weil ich damit in linke und rechte Teile 36:12.290 --> 36:13.930 einteile, die gleich groß sind ungefähr. 36:14.950 --> 36:17.790 Den Median möchte ich aber gerade, vielleicht nicht den Median, 36:17.870 --> 36:19.750 sondern ein allgemeineres Problem möchte ich gerade lösen. 36:20.690 --> 36:23.890 Also an der Stelle möchte ich jetzt nicht eine speziellere Wahl 36:23.890 --> 36:24.350 nutzen. 36:25.410 --> 36:31.570 Kann man machen, indem man halt ein Karten-Rangelement-Problem 36:31.570 --> 36:32.970 reduziert auf Mediansuche. 36:33.510 --> 36:36.970 Aber an der Stelle können wir uns einfach mal vorstellen, wir halten 36:36.970 --> 36:39.130 es einfach und wählen den Median. 36:39.130 --> 36:40.850 Wir wählen dieses Pivot-Element zufällig. 36:41.210 --> 36:44.290 Der Grund ist, wenn man es zufällig wählt, hat man im Schnitt, genau 36:44.290 --> 36:46.070 wie bei Quicksort, eigentlich eine gute Einteilung. 36:47.030 --> 36:48.930 Also wie gesagt, das ist wieder dieses Argument, es klappt vielleicht 36:48.930 --> 36:54.630 nicht immer gut mit einer zufälligen Wahl, aber im Erwartungswert ist 36:54.630 --> 36:57.910 es eine gute Einteilung, wenn man zufälliges Pivot-Element wählt. 36:58.070 --> 37:00.690 Also als zufälliges Element hier aus der Folge. 37:03.490 --> 37:05.130 Das ist nochmal der Algorithmus. 37:06.010 --> 37:09.190 Man kann nämlich jetzt zeigen, mit denselben Methoden wie für 37:09.190 --> 37:12.950 Quicksort hat dann Quickselect auch eine Ausführungszeit, die ist, 37:13.370 --> 37:15.570 naja, jetzt steigen wir nicht zweimal rekursiv ab, sondern nur noch 37:15.570 --> 37:15.870 einmal. 37:16.810 --> 37:20.830 Also im Prinzip hat es eine erwartete Ausführungszeit, die der 37:20.830 --> 37:25.010 Ausführungszeit entsprechen würde, wie wenn man deterministisch 37:25.010 --> 37:28.690 irgendwie das Pivot, das Median-Element hier schon wählen würde zum 37:28.690 --> 37:30.330 Einteilen und dann perfekt absteigen würde. 37:30.330 --> 37:34.030 Dann würde das Master-Theorem sagen, dann wäre die Ausführungszeit 37:34.030 --> 37:34.350 linear. 37:35.270 --> 37:37.590 Und das kriegen wir tatsächlich auch erwartet bei einer zufälligen 37:37.590 --> 37:38.610 Pivot -Wahl raus. 37:39.110 --> 37:41.970 Also der Beweis, der funktioniert so ähnlich wie bei Quicksort, nur 37:41.970 --> 37:44.370 dass man nur einmal rekursiv absteigt. 37:44.430 --> 37:45.450 Das ist der entscheidende Unterschied. 37:48.620 --> 37:50.340 Okay, gut. 37:51.980 --> 37:56.700 Dann jetzt vielleicht noch ein kurzer Ausblick, was sonst noch zu 37:56.700 --> 37:59.120 diesem Auswahlproblem existiert. 37:59.120 --> 38:01.060 Da würde ich jetzt auch nicht im Detail drauf eingehen. 38:02.200 --> 38:05.040 Man kann das erstmal noch ein bisschen tunen, indem man das zum 38:05.040 --> 38:06.640 Beispiel zu einem Inplace-Algorithmus macht. 38:07.120 --> 38:10.120 Was wir gerade hatten, das war ein Algorithmus, der war nicht Inplace, 38:10.180 --> 38:11.280 weil der neue Folgen anlegt. 38:11.880 --> 38:14.000 Und das kann man aber auch mit denselben Tricks zu einem Inplace 38:14.000 --> 38:15.980 -Algorithmus machen mit so einer Array-Implementierung. 38:16.120 --> 38:17.740 Also ganz analog zu Quicksort. 38:17.840 --> 38:21.040 Man kann auch zwei Wege-Vergleiche benutzen und das Ganze iterativ 38:21.040 --> 38:21.360 machen. 38:21.360 --> 38:25.240 Also diesmal wirklich vollständig iterativ und nicht rekursiv, weil 38:25.240 --> 38:27.000 man nur einmal rekursiv absteigen würde. 38:27.140 --> 38:29.420 Und das ist dann so eine Art Last-Line-Rekursion, die kann man 38:29.420 --> 38:29.940 auflösen. 38:31.860 --> 38:36.800 Man kann auch, wie schon angedeutet, diese Pivot-Wahl ein bisschen 38:36.800 --> 38:42.060 besser machen oder günstiger machen, indem man etwas tut, was halt 38:42.060 --> 38:46.120 beweisbar eine annähernd gute Aufteilung bietet oder eine annähernd 38:46.120 --> 38:47.180 gute Pivot-Wahl. 38:47.600 --> 38:50.100 Das ist dann ein bisschen komplexer und man kann da Zeit investieren 38:50.100 --> 38:55.740 und was man rauskriegt, ist dann, dass man Quick-Select tatsächlich 38:55.740 --> 38:58.500 deterministisch mit linearer Laufzeit hinkriegt. 38:59.340 --> 39:02.500 Wie gesagt, möchte ich nicht so sehr darauf eingehen, wie das geht. 39:02.580 --> 39:05.040 Das ist ein etwas komplexerer Algorithmus, der das dann alles in 39:05.040 --> 39:09.220 Fünfergruppen einteilt und dann so fünf Teilmediane versucht zu 39:09.220 --> 39:12.020 berechnen und dann ist eine davon garantiert gut. 39:15.600 --> 39:16.980 Also was hat man dann gewonnen? 39:17.940 --> 39:21.540 Wenn man deterministisch das Ganze lösen kann in linearer Zeit, dann 39:21.540 --> 39:24.160 kann man insbesondere auch Quick-Sort deterministisch machen. 39:25.100 --> 39:30.960 Wenn man den Median deterministisch in Linearzeit bestimmen kann, dann 39:30.960 --> 39:33.980 kann man Quick-Sort, das kann man einfach einsetzen als Pivot-Wahl für 39:33.980 --> 39:38.380 Quick -Sort und hat dann deterministisch diese Laufzeit, die fast n 39:38.380 --> 39:40.840 log n ist, also n log n plus einen linearen Anteil. 39:41.200 --> 39:44.020 Und der lineare Anteil, der richtet sich danach, wie groß diese 39:44.020 --> 39:47.980 Konstanten bei der deterministischen Auswahl oder bei den 39:47.980 --> 39:50.880 deterministischen Berechnungen von den Medianen ist. 39:52.200 --> 39:56.440 Man kann es auch noch verallgemeinern, indem man nicht nur ein Element 39:56.440 --> 39:59.060 vom Rang k wählt, sondern ganz viele, also k Stück. 39:59.160 --> 40:05.540 Man möchte die Elemente vom Rang kleiner gleich k finden, womöglich 40:05.540 --> 40:06.200 auch sortiert. 40:07.180 --> 40:12.360 Das ist dann eine Aufgabe, da wird etwas sehr analoges oder ähnliches 40:12.360 --> 40:13.420 auf dem Übungsblatt vorgestellt. 40:14.480 --> 40:17.060 Deshalb gehe ich da auch hier gar nicht weiter drauf ein. 40:17.640 --> 40:23.020 Aber die Idee ist halt, dass man noch mehr Elemente von Quick-Sort 40:23.020 --> 40:23.980 sozusagen verwendet. 40:25.920 --> 40:27.700 Man kann es auch noch weiter verallgemeinern. 40:28.140 --> 40:32.140 Eine Arbeit, die in einer anderen Forschergruppe von Peter Sanders 40:32.140 --> 40:36.000 gemacht wurde, zu denen ist Google gekommen und hat gesagt, was die 40:36.000 --> 40:38.600 brauchen, ist eine Range-Median-Berechnung. 40:39.660 --> 40:42.680 Das ist scheinbar genau das, was Google an der Stelle gebraucht hat. 40:43.700 --> 40:46.760 Und was das bedeutet, ist, sie haben einen riesen Datensatz, der ist 40:46.760 --> 40:50.060 nicht sortiert, oder der ist vielleicht nach irgendwas anderem 40:50.060 --> 40:52.700 sortiert, nach Datum oder Eintreffen oder sowas. 40:53.780 --> 40:57.700 Und dann sollen bestimmte Records oder bestimmte Einträge 40:57.700 --> 40:59.560 rausgegriffen werden von A bis B. 41:01.080 --> 41:05.340 Und unter diesen Einträgen soll halt bezüglich irgendeines anderen 41:05.340 --> 41:08.840 Keys, also bezüglich irgendeiner anderen Sortierung, ein Element vom 41:08.840 --> 41:11.260 Rang K berechnet werden, zum Beispiel ein Median oder sowas. 41:11.340 --> 41:13.380 Da möchte man dann typische Elemente rausgreifen. 41:14.280 --> 41:16.200 Also kann man sich überlegen, dass das vielleicht im Data-Mining 41:16.200 --> 41:17.360 -Anwendungen hat. 41:19.880 --> 41:23.880 Und die Idee ist, wenn man einmal vorberechnet, und das ist jetzt 41:23.880 --> 41:26.260 natürlich was komplexeres als einfach eine Sortierung, weil dann 41:26.260 --> 41:28.100 würden diese Indizes A und B kaputt gehen. 41:29.420 --> 41:34.480 Wenn man einmal so lange wie Sortieren dauert, vorberechnet, dann 41:34.480 --> 41:37.780 kriegt man diese Range Queries ziemlich schnell hin, nämlich in 41:37.780 --> 41:38.620 logarithmischer Zeit. 41:39.900 --> 41:42.160 Und da spielt Sortieren, wie gesagt, auch eine Rolle, aber es ist 41:42.160 --> 41:43.100 jetzt nicht einfach sortieren. 41:47.620 --> 41:51.300 Das sollte vielleicht jetzt alles zum Auswahlproblem sein. 41:51.760 --> 41:54.740 An der Stelle Fragen, weil sonst machen wir einen kleinen Sprung zum 41:54.740 --> 41:56.320 nächsten Sortieralgorithmus. 41:59.840 --> 42:05.580 Genau, ich hatte letztes Mal schon versprochen oder zumindest 42:05.580 --> 42:09.620 angedeutet, dass man diese untere Schranke, die wir bewiesen haben, 42:10.040 --> 42:13.640 also vergleichsbasierte Algorithmen brauchen mindestens n log n minus 42:13.640 --> 42:17.200 o von n viele Vergleiche und so viel Laufzeit natürlich auch 42:17.200 --> 42:21.980 insbesondere, dass das eine untere Schranke ist, die einen vielleicht 42:21.980 --> 42:24.400 nicht so sehr demotivieren sollte, sondern die sollte einem vielleicht 42:24.400 --> 42:28.340 eher sagen, was man anders machen muss, damit man schneller sortiert. 42:29.920 --> 42:33.980 Und die entscheidende Sache da ist, dass wir für die untere Schranke 42:33.980 --> 42:37.260 die Annahme gemacht haben, dass das Einzige, was man tun kann, um 42:37.260 --> 42:40.740 rauszufinden, in welcher Relation zwei Elemente stehen, dass das 42:40.740 --> 42:43.600 Einzige, was man tun kann, da Vergleiche sind. 42:44.340 --> 42:46.720 Also das Einzige, was man tun kann, sind Vergleiche. 42:47.760 --> 42:50.240 Also insbesondere die Elemente sehen wie schwarze Kisten aus, da kann 42:50.240 --> 42:52.600 man nicht reingucken, man kann keine Bitstruktur oder sowas nutzen, 42:52.880 --> 42:53.980 man kann sie nur vergleichen. 42:54.120 --> 42:57.840 Und dann ist es tatsächlich so, das Beste, was man tun kann, das muss 42:57.840 --> 42:59.700 in Zeit o von n log n laufen. 43:01.100 --> 43:03.900 Und für uns bedeutet das, wenn wir schneller sortieren wollen, müssen 43:03.900 --> 43:06.060 wir natürlich mit den Elementen irgendwas anderes machen als 43:06.060 --> 43:06.600 vergleichen. 43:07.600 --> 43:12.560 Und das ist der Ausgangspunkt für den nächsten Algorithmus. 43:12.760 --> 43:16.500 Und den würde ich jetzt nur mal andeuten und noch nicht genau 43:16.500 --> 43:16.920 besprechen. 43:18.620 --> 43:23.140 Der Ausgangspunkt ist etwas, das man Eimer sortieren oder im 43:23.140 --> 43:24.240 Englischen Bucket Sort nennt. 43:24.360 --> 43:26.000 Auf Deutsch hört sich das ein bisschen komisch an. 43:26.180 --> 43:28.940 Also wir sagen dann auch nicht Eimer sortieren, das ist vielleicht ein 43:28.940 --> 43:32.280 bisschen plump, sondern wir sagen K-Sort oder K-Sortieren. 43:33.760 --> 43:35.680 Manche Leute nennen das auch ganzteiliges Sortieren. 43:37.040 --> 43:41.720 Und was damit gemeint ist, ist konzeptionell was ziemlich Einfaches. 43:42.500 --> 43:49.600 Also wir haben hier, wenn wir insgesamt K-Keys haben, also K-mögliche 43:49.600 --> 43:52.280 Werte, nach denen wir die Elemente sortieren möchten. 43:52.980 --> 43:55.020 Also stellen Sie sich vor, wir haben da vielleicht Jahreszahlen, nach 43:55.020 --> 43:57.580 denen wir die sortieren möchten und da sind nur 100 Jahreszahlen 43:57.580 --> 43:57.880 relevant. 43:58.740 --> 44:02.880 Dann gibt es für uns 100 mögliche Schlüssel, nach denen wir die 44:02.880 --> 44:03.740 Elemente sortieren. 44:04.280 --> 44:05.580 Also da wäre K gleich 100. 44:06.880 --> 44:13.500 Und was wir dann tun ist, wir bauen uns neue Folgen, nämlich 100 44:13.500 --> 44:13.800 Stück. 44:14.100 --> 44:16.440 Oder diese Folgen sind genau das, was man dann vielleicht als Eimer 44:16.440 --> 44:17.780 betrachten könnte oder als Buckets. 44:19.520 --> 44:23.220 Und wir gehen die Elemente, die wir sortieren möchten, einfach von 44:23.220 --> 44:28.680 links nach rechts durch in irgendeine Reihenfolge und sortieren die 44:28.680 --> 44:33.140 Elemente nacheinander jeweils in den Eimer, der dem Sortierschlüssel 44:33.140 --> 44:33.640 entspricht. 44:34.880 --> 44:36.840 Also wie gesagt, gleich auch noch ein kurzes Beispiel. 44:38.000 --> 44:40.540 Aber die Idee ist, wir gehen die Elemente der Reihe nach durch und 44:40.540 --> 44:45.380 sortieren die in Bucket Nummer Key von E, also Key von E ist der 44:45.380 --> 44:47.340 Schlüssel, nach dem wir sortieren möchten, ein. 44:48.240 --> 44:52.080 Und wenn wir dann fertig sind, dann haben wir halt in dem ersten Eimer 44:52.080 --> 44:58.420 B von 0, da haben wir alle Elemente, die den kleinsten Key haben, die 44:58.420 --> 44:59.620 den kleinsten Schlüssel haben. 44:59.700 --> 45:02.240 In dem zweiten, die mit dem zweitkleinsten Schlüssel und so weiter. 45:02.240 --> 45:05.000 Das heißt im Prinzip, wenn wir die Eimer der Reihe nach durchgehen, 45:05.120 --> 45:07.500 dann haben wir eine Sortierung nach diesen Schlüsseln. 45:07.660 --> 45:08.440 Die ist sogar stabil. 45:08.760 --> 45:12.120 Also wenn wir das jeweils immer ans Ende ranhängen, an diese Liste, 45:12.540 --> 45:17.540 die der Eimer ist und dann am Ende die Eimer von links nach rechts 45:17.540 --> 45:23.740 durchgehen, dann haben wir eine Sortierung, die sogar stabil ist. 45:24.200 --> 45:25.260 Also das ist auch genau, was wir tun. 45:25.340 --> 45:30.480 Die Rückgabe oder die neue Liste, die neue Folge ist dann einfach die 45:30.480 --> 45:34.480 Konkatenierung dieser Folgen B von 0 bis B von K minus 1. 45:36.200 --> 45:40.520 Der Nachteil ist, wir brauchen ziemlich viele Teilfolgen, ziemlich 45:40.520 --> 45:41.580 viele Folgen hier unten. 45:43.620 --> 45:47.300 Und das klappt also tatsächlich nur dann, wenn K relativ klein ist. 45:48.640 --> 45:53.260 Auf der anderen Seite, die gute Nachricht ist, wir brauchen eigentlich 45:53.260 --> 45:57.840 nur Zeit O von N, also plus diese Initialisierung der Teilfolgen. 45:58.140 --> 46:00.440 Aber wir brauchen ansonsten nur lineare Zeit, um die Elemente 46:00.440 --> 46:00.940 durchzugehen. 46:01.040 --> 46:02.840 Jedes Element kann dann schnell einsortiert werden. 46:03.460 --> 46:06.080 Oder reingelegt werden in einen dieser Buckets. 46:09.130 --> 46:09.650 Beispiel. 46:10.550 --> 46:14.010 Wir haben jetzt hier Elemente, die sind jeweils gegeben durch ein Key, 46:14.630 --> 46:19.090 3, 1, 2 und das eigentliche Element. 46:19.210 --> 46:20.410 Das trägt vielleicht mehr Informationen. 46:20.630 --> 46:23.750 Es ist vielleicht ein ganzer Datensatz und der Key ist vielleicht nur 46:23.750 --> 46:25.770 die Jahreszahl oder irgendeine Nummer oder sowas. 46:27.250 --> 46:30.970 Und wenn wir dann nach dem Key sortieren möchten, in dem Fall, also 46:30.970 --> 46:33.090 hier oben steht nur noch mal der Algorithmus Keysort, wie eben. 46:34.690 --> 46:41.390 Was wir dann tun ist, wir bilden halt diese vier Folgen für die vier 46:41.390 --> 46:45.230 verschiedenen möglichen Werte von dem Schlüssel und sortieren dann, 46:45.270 --> 46:48.690 wir gehen dann diese Folge S durch und sortieren dann jeweils ein oder 46:48.690 --> 46:50.230 hängen jeweils an an die richtige Folge. 46:50.350 --> 46:53.030 Das heißt, wir gehen hier durch und das Erste, was passiert, ist, dass 46:53.030 --> 46:59.430 wir 3, A hier an diese rechte, also an die vierte Folge hängen. 46:59.550 --> 47:04.670 Und dann kommt 1, B, das hängen wir an diese zweite Folge vorne dran. 47:05.470 --> 47:06.650 Und so gehen wir das der Reihe nach durch. 47:06.750 --> 47:08.710 Und am Ende müssen wir eigentlich nur noch B ablesen. 47:09.490 --> 47:10.950 Also die Folgen aneinander hängen. 47:15.440 --> 47:21.140 Wie das im Pseudocode aussieht, das gucken wir uns das nächste Mal an. 47:21.140 --> 47:23.960 Hier erstmal die Frage, gibt es von Ihrer Seite Fragen, wie das so 47:23.960 --> 47:24.520 funktioniert? 47:24.820 --> 47:26.700 Also ich hoffe, das System ist klar. 47:28.300 --> 47:33.040 Das kann man dann auch als Ausgangspunkt nutzen, um dann für deutlich 47:33.040 --> 47:39.720 größere Schlüssel als nur solche von 0 bis K-1 für deutlich größere 47:39.720 --> 47:42.440 Schlüssel oder Schlüsselmengen einen effizienten 47:43.180 --> 47:44.200 Linearzeitsortieralgorithmus zu bauen. 47:45.800 --> 47:46.600 Grundprinzip klar? 47:48.340 --> 47:52.480 Okay, wenn ja, wäre das ein guter Übergang für die Übung und dann 47:52.480 --> 47:54.280 bedanke ich mich schon mal für die Aufmerksamkeit. 47:55.840 --> 47:58.120 Hallo und herzlich willkommen zur sechsten Übung. 47:58.640 --> 48:02.120 Ich hoffe, dass das perfekt jetzt auch funktioniert. 48:02.620 --> 48:04.080 Schön, dass ihr alle da seid. 48:04.700 --> 48:08.500 Wir werden heute viel sortieren, wie ihr wahrscheinlich schon erwartet 48:08.500 --> 48:08.700 habt. 48:08.700 --> 48:10.900 Am Anfang ein paar organisatorische Dinge. 48:13.180 --> 48:16.560 Nur noch meine Erinnerung, das sollte in den Tutorien auch schon mal 48:16.560 --> 48:17.840 gesagt werden. 48:20.680 --> 48:24.420 Unsere Regelung bei Abschreiben ist, beim ersten Mal Abschreiben gibt 48:24.420 --> 48:28.460 es eine Verwarnung und auf die Aufgabe 0 Punkte und ab dem zweiten Mal 48:28.460 --> 48:32.720 Abschreiben kann kein Übungsschein, also keine Bonuspunkte für die 48:32.720 --> 48:35.680 Klausur mehr erhalten werden. 48:36.280 --> 48:39.020 Also Abschreiben gilt nicht nur Abschreiben von anderen, sondern auch 48:39.020 --> 48:42.440 Abschreiben von Lösungen, die es schon gibt. 48:42.580 --> 48:46.660 Nur, dass ihr es wisst und dass es euch eben nicht passiert. 48:48.900 --> 48:52.900 Und weil es immer noch häufig vorkommt, werden wir uns in Zukunft oder 48:52.900 --> 48:56.560 weil es eben viele Übungsblätter sind, werden wir uns in Zukunft 48:56.560 --> 49:00.660 vorbehalten, auch Punktabzüge zu geben, wenn die Tutoriumsnummer fehlt 49:00.660 --> 49:03.020 und das Stackblatt fehlt. 49:03.120 --> 49:06.640 Also wir werden euch auch sehr dankbar, wenn ihr das macht, weil es 49:06.640 --> 49:12.380 sonst schwierig ist beim Sortieren und auch Sortieren. 49:14.540 --> 49:18.340 Und als Erinnerung, in zwei Wochen wird die Probeklausur stattfinden 49:18.340 --> 49:22.060 statt der Übung und der Vorlesung. 49:22.400 --> 49:25.780 Es ist freiwillig, aber ich würde euch alle ermutigen mitzumachen. 49:25.920 --> 49:27.640 Ihr könnt nur gewinnen dabei. 49:27.760 --> 49:28.880 Ihr kriegt es korrigiert. 49:29.140 --> 49:31.120 Die Klausur wird in den Tutorien besprochen. 49:31.740 --> 49:32.940 Ihr seht, wo ihr steht. 49:33.620 --> 49:37.740 Ihr seht schon mal, wie ihr in der Klausur abgeschnitten hättet. 49:37.900 --> 49:41.820 Und das zählt nicht irgendwie negativ, wenn es schlecht ist. 49:41.940 --> 49:43.200 Also ihr könnt dabei nichts verlieren. 49:43.780 --> 49:45.660 Ich würde euch raten, allen mitzumachen. 49:50.820 --> 49:52.440 So genau, jetzt geht es los. 49:52.500 --> 49:53.920 Das war es zum Organisatorischen. 49:54.260 --> 49:56.240 Jetzt geht es los mit Sortieren. 49:58.240 --> 50:00.520 Also wir werden heute viel Quicksort machen. 50:00.520 --> 50:03.280 Das war ja auch diese Woche das Hauptthema. 50:05.520 --> 50:07.460 Und genau dazu noch mal. 50:07.720 --> 50:12.440 Ich habe Zahlen mitgebracht und können wir sortieren. 50:16.020 --> 50:17.900 Also vielleicht noch mal eine kurze Erinnerung. 50:20.820 --> 50:24.900 Letzte Woche habt ihr Merge Sort kennengelernt. 50:26.360 --> 50:29.520 Merge Sort ist wie Quicksort ein Teil- und Herrscher-Algorithmus. 50:31.660 --> 50:35.620 Bei dem das Problem in kleinere Teilprobleme zerlegt wird. 50:37.260 --> 50:40.300 Und die kleineren Probleme dann gelöst werden. 50:40.380 --> 50:43.700 Der Unterschied oder ein großer Unterschied von Merge Sort und 50:43.700 --> 50:48.280 Quicksort ist, wenn ihr euch erinnert, bei Merge Sort habt ihr erstmal 50:48.280 --> 50:49.720 die Eingabe aufgeteilt. 50:50.680 --> 50:52.520 Machen wir es vielleicht erstmal mit 4. 50:58.260 --> 51:03.840 Aufgeteilt und dann nochmal aufgeteilt und dann 0 und 8 sortiert. 51:04.120 --> 51:06.480 3 und 7 und dann hier verglichen. 51:07.520 --> 51:11.540 Die zwei verglichen 3, die zwei verglichen 7 und 8. 51:11.860 --> 51:14.840 Das heißt, der aufwendige Teil, die Vergleiche finden beim 51:14.840 --> 51:17.980 Zusammensetzen statt und nicht beim Auseinandersortieren. 51:18.840 --> 51:20.640 Und bei Quicksort ist es genau umgekehrt. 51:20.680 --> 51:22.560 Da habt ihr die Arbeit nicht beim Zusammensetzen. 51:22.640 --> 51:26.100 Beim Zusammensetzen müsst ihr gar nichts mehr machen, sondern bei 51:26.100 --> 51:31.260 Quicksort habt ihr die Arbeit, wenn ihr es beim Auseinandersortieren. 51:33.200 --> 51:35.480 Als Erinnerung an Quicksort 51:40.600 --> 51:44.960 ist hier der Pseudocode dafür. 51:48.160 --> 51:52.720 Der erste Schritt ist ein Pivot, ein sogenanntes Pivot. 51:52.820 --> 51:59.280 Das Pivot ist jeweils das Element, so dass ihr den Rest in Elemente, 51:59.380 --> 52:01.060 die kleiner und größer sind, sortiert. 52:01.280 --> 52:06.820 Also wenn wir uns hier zum Beispiel als Pivot 3 wählen, dann sortieren 52:06.820 --> 52:09.360 wir in Elemente, die kleiner sind, nämlich 0. 52:11.220 --> 52:14.760 Das ist der Partition-Schritt und Elemente, die größer sind, der Rest. 52:15.140 --> 52:17.460 Ihr seht jetzt schon, das war nicht so eine gute Wahl. 52:17.520 --> 52:23.280 Eine bessere Wahl wäre offensichtlich zum Beispiel 5 gewesen. 52:23.720 --> 52:29.460 Bei 5 hätten wir nämlich 0.3 links davon gehabt und den Rest rechts 52:29.460 --> 52:32.240 davon mit dem Pivot. 52:32.540 --> 52:34.080 Und dann geht es einfach weiter. 52:34.520 --> 52:37.400 Ihr wisst jetzt, dass links davon nur noch kleinere Elemente sind, 52:37.500 --> 52:39.220 rechts davon größere Elemente. 52:39.260 --> 52:42.980 Der setzt hier fest und dann wird rekursiv erst die Teilliste noch 52:42.980 --> 52:43.480 sortiert. 52:44.560 --> 52:45.400 Wird wieder ein Pivot. 52:45.640 --> 52:48.280 In dem Fall gibt es jetzt nichts mehr zu sortieren, aber ich müsste 52:48.280 --> 52:49.540 mir trotzdem die 3 anschauen. 52:49.660 --> 52:53.060 Dann sehe ich, die 0 ist kleiner, dann gebe ich es wieder zurück und 52:53.060 --> 52:54.140 genauso mit dem Rest. 52:54.620 --> 52:58.300 Hier als Pivot ist natürlich das Beste, wenn wir die 6 wählen würden 52:58.300 --> 53:00.000 und dann in 7 und 8 einteilen. 53:00.920 --> 53:01.740 Nee, die 7 natürlich. 53:04.220 --> 53:05.220 Zählen muss man können. 53:05.620 --> 53:08.960 Und dann hätten wir den anderen Teil gemacht. 53:11.900 --> 53:15.760 Das Problem bei Quicksort, wie jetzt gerade schon vielleicht auch 53:15.760 --> 53:20.620 erkenntlich geworden ist, die Wahl von dem Pivot-Element, die Wahl, wo 53:20.620 --> 53:23.160 ich das Intervall aufteile, ist ganz wichtig. 53:23.500 --> 53:26.540 Wenn ich da immer das kleinste Element oder immer das größte Element 53:26.540 --> 53:29.220 wähle, dann komme ich auf eine quadratische Laufzeit. 53:30.780 --> 53:34.440 Und in der Vorlesung habt ihr dann gelernt, dass eine Möglichkeit es 53:34.440 --> 53:39.040 aufzulösen ist, wie wir es auch schon vorher öfter mal gelernt haben, 53:39.120 --> 53:44.020 das Pivot-Element zufällig zu wählen, um dann auf eine erwartete 53:44.020 --> 53:46.720 Laufzeit von NlogN zu kommen. 53:46.920 --> 53:49.800 Also erwartet auch nicht schlechter abzuschneiden als z.B. 53:49.940 --> 53:50.460 Merge Sort. 53:53.700 --> 54:01.580 Ich habe jetzt gerade einfach die Zahlen auseinander sortiert, aber da 54:01.580 --> 54:04.240 gibt es jetzt Algorithmen, die in place funktionieren. 54:04.480 --> 54:08.660 Also die in place das Ganze, die diesen dritten Schritt, diesen 54:08.660 --> 54:10.620 Partition -Schritt in place machen. 54:10.960 --> 54:13.240 Einen davon habt ihr in der Vorlesung kennengelernt. 54:14.780 --> 54:19.660 Der sieht folgendermaßen aus, den will ich jetzt auch einmal noch kurz 54:19.660 --> 54:25.060 veranschaulichen, wie der funktioniert, damit ihr den einmal gesehen 54:25.060 --> 54:25.420 habt. 54:25.980 --> 54:28.280 Und danach, ihr habt es ja schon kurz gesehen, werden wir noch einen 54:28.280 --> 54:32.680 zweiten Partition-Algorithmus kennenlernen und zwar vorgetanzt von der 54:32.680 --> 54:34.220 rumänischen Tanzgruppe. 54:41.110 --> 54:45.640 Ich nehme die gleichen Zahlen, wie gleich verwendet werden. 54:46.720 --> 54:49.160 Also 3, 0, 54:54.060 --> 55:04.840 1, 8, 7, 2, 5, 55:13.910 --> 55:15.470 und dann fehlen noch 2, 55:18.550 --> 55:20.050 4, 9, 6. 55:29.510 --> 55:29.870 Okay. 55:31.630 --> 55:33.650 Wie funktioniert der Algorithmus jetzt? 55:33.790 --> 55:37.210 Und zwar, als erstes schauen wir uns die erste Zeile an. 55:37.730 --> 55:41.890 Als Pivot nehmen wir jetzt das erste Element aus dem Grund, weil das 55:41.890 --> 55:43.830 nachher auch so gemacht wird in dem Video. 55:44.270 --> 55:46.110 Das heißt, als Pivot nehmen wir uns die 3. 55:48.430 --> 55:53.910 Dann setzen wir i und j als die beiden an die linke Seite von unserem 55:53.910 --> 55:54.410 Intervall. 55:54.610 --> 55:58.450 Also haben wir hier i und j und 3 ist unser Pivot-Element. 56:01.960 --> 56:05.720 Und was wir dann als nächstes machen, wir tauschen das Pivot-Element 56:05.720 --> 56:07.520 mit dem letzten Eintrag. 56:07.680 --> 56:11.280 Das heißt, wir vertauschen hier einmal, dann sieht es so aus. 56:14.680 --> 56:19.680 Okay, und jetzt, jetzt gehen wir mit j einmal komplett durch den Array 56:19.680 --> 56:22.140 durch, bis wir am Ende ankommen. 56:22.580 --> 56:28.080 Und zwar überprüfen wir, ob ai kleiner gleich p ist. 56:28.640 --> 56:32.760 In dem Fall ist es der Fall. 56:36.260 --> 56:39.020 Nee, im ersten Fall ist es nicht der Fall, weil wir im ersten Fall 56:39.020 --> 56:41.660 noch auf 6 zeigen, also i und j zeigen auf 6. 56:42.140 --> 56:44.300 Und das heißt, ai6 ist größer als 3. 56:44.300 --> 56:47.620 Das heißt, wir überspringen die if-Bedingungen und wir erhöhen nur j 56:47.620 --> 56:48.240 um 1. 56:49.620 --> 56:51.240 Dann machen wir das gleiche nochmal. 56:52.740 --> 56:55.940 Jetzt ist tatsächlich, habe ich gerade schon vorgegriffen, die 0 ist 56:55.940 --> 56:57.440 tatsächlich kleiner gleich p. 56:58.200 --> 57:02.380 Dann tauschen wir die zwei und erhöhen j um 1. 57:05.020 --> 57:06.640 Wir erhöhen i um 1. 57:07.600 --> 57:08.520 Also die zwei werden vertauscht. 57:10.180 --> 57:11.560 Und j erhöhen wir auch um 1. 57:11.560 --> 57:14.120 Und die, die wir schon verglichen haben, die wollen wir farbig 57:14.120 --> 57:14.540 markieren. 57:14.740 --> 57:17.560 Also unsere 0 wissen wir schon, dass die kleiner ist als j. 57:18.200 --> 57:22.700 Und die 6 haben wir auch schon angeschaut, die ist mindestens größer 57:22.700 --> 57:23.780 als unser Pivot-Element. 57:25.000 --> 57:26.640 Jetzt gucken wir uns die 1 an. 57:30.480 --> 57:32.880 Bei unserer 1 passiert wieder genau das gleiche. 57:35.740 --> 57:38.120 Wir tauschen die 1 mit der 6. 57:42.090 --> 57:44.470 Erhöhen i um 1, 57:47.480 --> 57:50.820 dann mit der 8 machen wir nichts, erhöhen nur j um 1. 57:54.170 --> 57:57.090 Bei der 7 machen wir nichts, erhöhen nur j um 1. 58:00.620 --> 58:08.740 Bei der 2, da vertauschen wir die 6 und die 2 und erhöhen i um 1 und j 58:08.740 --> 58:09.360 um 1. 58:11.840 --> 58:13.240 Dann nehmen wir die 5. 58:15.360 --> 58:22.920 Da tun wir wieder nichts, 5 ist größer als 3, 4 ist größer als 3 und 58:22.920 --> 58:24.660 schließlich 9 ist größer als 3. 58:28.320 --> 58:38.160 Wenn wir am Ende angelangt sind, dann müssen wir noch ai und aj oder 58:38.160 --> 58:39.980 ar vertauschen, den letzten. 58:41.760 --> 58:46.320 Und dann haben wir in place unseren Array mit der Methode aus der 58:46.320 --> 58:57.220 Vorlesung sortiert, dann können wir i zurückgeben und bekommen so und 58:57.220 --> 59:01.380 können dann rekursiv weiter mit dem ersten Teil und mit dem zweiten 59:01.380 --> 59:01.980 Teil machen. 59:04.680 --> 59:09.940 Jetzt sehen wir das Ganze mit einem alternativen Algorithmus. 59:10.760 --> 59:13.000 Achtet mal drauf, ich werde auch immer wieder was dazu sagen, 59:16.260 --> 59:20.080 wie der Partitionsnährungsalgorithmus hier funktioniert. 59:28.320 --> 59:32.840 Also die Hüte, der linke Hut, der schwarze Hut ist hier das i und das 59:32.840 --> 59:35.180 Pivot -Element und der rechte Hut ist das j. 59:37.920 --> 59:41.780 Hier geht das j von rechts an und wird erniedrigt. 59:41.920 --> 59:47.300 Und die Invariante ist, dass alle, die größer sind, also rechts von 59:47.300 --> 59:50.100 dem j, dass die auch tatsächlich alle größer als das Pivot-Element 59:50.100 --> 59:50.880 sind. 01:00:11.500 --> 01:00:15.600 Genau, jetzt hat ein Tausch stattgefunden und jetzt haben sich nicht 01:00:15.600 --> 01:00:18.800 nur die Elemente vertauscht, sondern auch die Indizes i und j haben 01:00:18.800 --> 01:00:23.460 sich vertauscht und die Invariante ist, dass alle außerhalb von i und 01:00:23.460 --> 01:00:27.420 j, links von i und j sind kleiner und die rechts sind größer. 01:00:28.320 --> 01:00:30.980 Und j wandert jetzt von unten nach unten. 01:00:51.740 --> 01:00:55.800 Die drei vergleicht sich noch mit sich selbst und dann ist der erste 01:00:55.800 --> 01:00:58.780 Schritt abgeschlossen, die erste Partitionierung. 01:01:01.280 --> 01:01:05.440 Genau, und jetzt wird geteilt und weitergemacht. 01:01:07.960 --> 01:01:16.400 Die zwei ist das i und das Pivot-Element und die eins ist bei j ist 01:01:16.400 --> 01:01:17.700 bei index eins. 01:02:06.370 --> 01:02:11.610 Genau, das ist das Pivot-Element und das Pivot-Element ist bei 01:02:52.600 --> 01:02:56.800 Also man sieht schon, dass der Partitionierung-Algorithmus eine andere 01:02:56.800 --> 01:03:00.680 Reihenfolge im ersten Schritt gemacht hat als der andere, aber beide 01:03:00.680 --> 01:03:03.560 funktionieren in linearer Zeit. 01:03:03.680 --> 01:03:06.400 Bei beiden muss ich nur einmal durch den Array durchlaufen. 01:03:07.960 --> 01:03:12.060 Bei j dem ersten passiert es sortiert von links nach rechts und bei 01:03:12.060 --> 01:03:15.040 dem hier eben immer abwechselnd springend von oben nach unten. 01:04:14.980 --> 01:04:19.620 Als Pivot-Element wird hier immer, wie gesagt, das unterste Element, 01:04:19.900 --> 01:04:22.000 das linkeste Element gewählt. 01:04:22.520 --> 01:04:25.260 Das könnte man natürlich auch zufällig wählen und dann den gleichen 01:04:25.260 --> 01:04:28.400 Partitionierungs -Algorithmus nehmen, im Prinzip. 01:04:47.270 --> 01:04:55.930 Das ist das Pivot-Element und das Pivot-Element ist bei Also man sieht 01:04:55.930 --> 01:04:56.330 schon, dass der Partitionierung-Algorithmus eine andere Reihenfolge im 01:04:56.330 --> 01:04:56.370 ersten Schritt gemacht hat als der andere, aber beide funktionieren 01:04:56.410 --> 01:05:03.130 Bei j ist das Pivot -Element und das Pivot-Element ist bei 01:05:44.710 --> 01:06:10.550 Also Also ich hoffe, ihr habt jetzt alle verstanden, wie Quicksort 01:06:10.550 --> 01:06:11.350 funktioniert. 01:06:12.770 --> 01:06:14.430 Wir schauen uns nochmal kurz an. 01:06:14.570 --> 01:06:18.570 Das wird auch die erste Aufgabe auf dem Übungsplatz sein, dass ihr es 01:06:18.570 --> 01:06:21.310 nochmal selber einmal übt. 01:06:21.870 --> 01:06:27.310 So sieht der Partitionierungsalgorithmus aus, der gerade vorgetanzt 01:06:27.310 --> 01:06:27.650 wurde. 01:06:28.690 --> 01:06:33.370 Wie ich schon gesagt habe, die haben immer das erste Pivot-Element 01:06:33.370 --> 01:06:37.490 genommen und haben dann angefangen, vom Array ganz oben runter zu 01:06:37.490 --> 01:06:37.830 zählen. 01:06:38.110 --> 01:06:44.030 Man kann natürlich ein zufälliges Element wählen, irgendwo im Array 01:06:44.030 --> 01:06:46.210 und das dann einfach am Anfang tauschen. 01:06:46.210 --> 01:06:49.390 Genauso funktioniert der Partitionierungsalgorithmus aus der Vorlesung 01:06:49.390 --> 01:06:51.930 ja auch, dass es einfach ans Ende getauscht wird. 01:06:52.010 --> 01:06:55.150 Das ist dieser Schritt, dieser Tauschschritt hier. 01:06:56.330 --> 01:06:59.950 Dann was wir für eine Invariante haben, also unsere I und J, die 01:06:59.950 --> 01:07:01.290 vertauschen sich ja auch immer. 01:07:01.830 --> 01:07:05.070 Aber wir haben immer die Invariante, dass das, was außerhalb von I und 01:07:05.070 --> 01:07:06.670 J ist, dass das schon sortiert ist. 01:07:06.850 --> 01:07:09.830 Also das, was außerhalb von I und J ist, ist auf der richtigen Seite 01:07:09.830 --> 01:07:10.670 vom Pivot-Element. 01:07:11.710 --> 01:07:15.570 Und genau, wenn I kleiner J ist, dann gehe ich von J von oben das 01:07:15.570 --> 01:07:20.750 Intervall runter und sobald das Pivot-Element, sobald unsere 01:07:20.750 --> 01:07:26.130 Bedingungen, die wir immer erfüllt haben, sobald unsere Invariante 01:07:26.130 --> 01:07:30.750 verletzt ist, tauschen wir die Pivot-Elemente, tauschen die Indizes 01:07:30.750 --> 01:07:34.950 und dann gehen wir von J von unten nach oben hoch, was da ja auch 01:07:34.950 --> 01:07:35.450 passiert ist. 01:07:35.530 --> 01:07:40.650 Als das Pivot-Element die 3 mit der 2 getauscht hat, dann wurde der 01:07:40.650 --> 01:07:43.190 Hut dann nicht mehr von rechts nach links, sondern von links nach 01:07:43.190 --> 01:07:44.150 rechts weitergegeben. 01:07:44.970 --> 01:07:49.850 Und genau, wenn wir, wenn jetzt nicht mehr I unten ist und J oben, 01:07:49.930 --> 01:07:52.990 sondern J unten und I oben, was eben in dem Fall passiert, immer dann, 01:07:53.110 --> 01:07:58.370 wenn ein Tausch stattfindet, dann passiert es, dann geht es genau 01:07:58.370 --> 01:07:59.170 andersrum weiter. 01:07:59.270 --> 01:08:02.650 Dann wird J so lange hochgezählt, bis es nicht mehr kleiner gleich das 01:08:02.650 --> 01:08:07.410 Pivot -Element ist, wenn das, bis solange es noch kleiner gleich das 01:08:07.410 --> 01:08:10.510 Pivot -Element ist, solange die, sobald die Invariante verletzt worden 01:08:10.510 --> 01:08:14.430 würde, tausche ich die Elemente, tausche die Indizes und gehe dann 01:08:14.430 --> 01:08:16.450 wieder runter und bin dann wieder in einem anderen Schritt. 01:08:17.030 --> 01:08:22.110 Ich breche ab, wenn I gleich J ist und ich, und dann weiß ich wegen 01:08:22.110 --> 01:08:26.250 unserer Invariante, dass tatsächlich auch die restlichen Elemente sich 01:08:26.250 --> 01:08:28.870 auf den richtigen Plätzen befinden. 01:08:29.370 --> 01:08:32.870 Das Ganze geht in Place und in linearer Zeit, weil ich offensichtlich 01:08:32.870 --> 01:08:35.730 oder ihr habt es in dem Video gesehen, man kann es sich auch hier 01:08:35.730 --> 01:08:39.070 überlegen, ich muss jedes Element tatsächlich nur einmal anschauen, 01:08:39.230 --> 01:08:40.310 deshalb lineare Zeit. 01:08:42.170 --> 01:08:49.070 Okay, jetzt eine Idee ist nicht nur, um das zu verbessern, ist nicht 01:08:49.070 --> 01:08:52.770 nur zwei Pivot-Elemente zu verwenden, sondern nicht nur ein Pivot 01:08:52.770 --> 01:08:56.410 -Element zu verwenden, sondern zwei Pivot-Elemente und dann die 01:08:56.410 --> 01:08:59.930 Elemente in kleine, mittlere und große Elemente zu zerteilen. 01:09:01.990 --> 01:09:07.110 Historisch wurden die ersten Vorschläge dazu, haben keine Verbesserung 01:09:07.110 --> 01:09:09.930 gebracht, weder in Theorie noch Praxis. 01:09:10.450 --> 01:09:13.090 Es ist aber trotzdem keine Zeitverschwendung, dass wir uns das jetzt 01:09:13.090 --> 01:09:13.670 anschauen. 01:09:14.550 --> 01:09:19.730 Von 2009 gab es nämlich einen Ansatz von Jaroslawski, der praktisch 01:09:19.730 --> 01:09:20.910 und theoretisch besser war. 01:09:20.990 --> 01:09:26.190 Ein Multipivot-Ansatz und der deshalb auch in Java 7 Standard wurde 01:09:26.190 --> 01:09:27.090 2011. 01:09:29.090 --> 01:09:33.030 Und genau, den wollen wir uns jetzt anschauen. 01:09:33.790 --> 01:09:37.010 Also wie gesagt, die Idee ist, ich wähle mir nicht nur ein Pivot 01:09:37.010 --> 01:09:41.530 -Element P, sondern Pivot-Element P und Q und ich sortiere alle 01:09:41.530 --> 01:09:44.710 Elemente, die kleiner als P sind, die zwischen P und Q liegen und die 01:09:44.710 --> 01:09:45.870 größer als Q sind. 01:09:46.750 --> 01:09:50.190 Und dann mache ich das Ganze rekursiv auf drei Intervallen weiter 01:09:50.190 --> 01:09:51.030 statt auf zwei. 01:09:52.270 --> 01:09:57.370 Und leider gibt es da kein Video davon von der Tanzgruppe, deswegen 01:09:57.370 --> 01:09:58.690 müsst ihr mir nochmal zuschauen. 01:10:03.660 --> 01:10:05.900 Und wir müssen das hier machen. 01:10:10.080 --> 01:10:15.740 Außer, wie gesagt, es finden sich nochmal zehn Freiwillige, die einmal 01:10:15.740 --> 01:10:16.740 vortanzen möchten. 01:10:22.520 --> 01:10:27.400 Also wir fangen an mit einem Array, der so aussieht. 01:10:29.340 --> 01:10:29.780 3, 01:10:33.550 --> 01:10:41.270 1, 5, 01:10:47.720 --> 01:10:50.040 2, 7, 8, 01:10:55.730 --> 01:11:02.000 4, 0, 9, 6. 01:11:06.590 --> 01:11:11.870 Und dann gehen wir Schritt für Schritt den Pseudocode durch, damit ihr 01:11:11.870 --> 01:11:15.450 mal eine Partitionierung seht, weil wenn man sich das jetzt nur so 01:11:15.450 --> 01:11:19.830 anschaut, dann... Also man muss es einmal gemacht haben, damit man 01:11:19.830 --> 01:11:20.770 sieht, was da passiert. 01:11:21.370 --> 01:11:22.930 Okay, als erstes. 01:11:24.990 --> 01:11:31.870 Also hier wird standardmäßig wieder das ganz linke und rechte Element 01:11:31.870 --> 01:11:33.390 werden als Pivot-Elemente genommen. 01:11:33.790 --> 01:11:38.870 Auch hier verwendet man natürlich eine randomisierte Variante, dann 01:11:38.870 --> 01:11:42.550 kann ich die wieder einfach ans Ende tauschen und dann kann ich das im 01:11:42.550 --> 01:11:43.890 Prinzip genau gleich machen. 01:11:45.050 --> 01:11:49.990 Ich setze dann I an die Stelle L plus 1. 01:11:50.110 --> 01:11:53.610 L ist immer der linke Rand vom Intervall und R der rechte. 01:11:54.190 --> 01:11:57.230 Und J setze ich an die Stelle... Das mache ich mal unten. 01:11:58.690 --> 01:11:59.410 Kann man alle zahlen? 01:11:59.570 --> 01:12:00.150 Ja, wunderbar. 01:12:00.790 --> 01:12:04.790 Und dann habe ich noch ein K und hier ist K die Lauf-Variante, die 01:12:04.790 --> 01:12:06.190 durch den Array durchläuft. 01:12:07.990 --> 01:12:09.870 Genau, das war schon der nächste Schritt. 01:12:10.990 --> 01:12:14.170 Und solange K jetzt kleiner als J ist, also ich gehe hier durch alle 01:12:14.170 --> 01:12:15.350 Elemente einmal durch. 01:12:15.890 --> 01:12:20.270 Und der erste Fall ist, dass AK kleiner als mein kleines Pivot-Element 01:12:20.270 --> 01:12:20.530 ist. 01:12:20.650 --> 01:12:22.250 Also AK kleiner als 3. 01:12:22.790 --> 01:12:24.750 1 ist tatsächlich kleiner als 3. 01:12:25.570 --> 01:12:27.750 Dann tauschen wir AK und I. 01:12:28.050 --> 01:12:30.950 In unserem Fall passiert da gar nichts, weil K und I die gleiche 01:12:30.950 --> 01:12:34.130 Position haben und erhöhen I um 1. 01:12:35.270 --> 01:12:39.190 In den S-Zweig gehen wir da nicht rein, sondern erhöhen direkt auch K 01:12:39.190 --> 01:12:39.790 um 1. 01:12:43.420 --> 01:12:45.740 Dann das gleiche nochmal von vorne. 01:12:46.260 --> 01:12:50.260 Diesmal kommen wir in den S-Zweig, weil K ist nicht kleiner als 3, 01:12:51.200 --> 01:12:53.060 aber K ist auch nicht größer als Q. 01:12:53.180 --> 01:12:55.000 Das heißt, wir machen gar nichts. 01:12:56.140 --> 01:13:03.300 Wir stellen fest, die 5 ist mittelgroß, deswegen grün und wir erhöhen 01:13:03.300 --> 01:13:04.880 K um 1 und gehen weiter. 01:13:07.020 --> 01:13:08.560 Das Ganze nochmal von vorne. 01:13:10.520 --> 01:13:16.420 Jetzt sind wir wieder in unserem Fall, dass wir die 2 und die 5 01:13:16.420 --> 01:13:17.300 tauschen müssen, 01:13:20.820 --> 01:13:26.120 I um 1 erhöhen, dann noch K um 1 erhöhen und es geht weiter. 01:13:26.920 --> 01:13:34.040 Okay, jetzt kommt nochmal ein neuer Fall und zwar AK ist größer als 3 01:13:34.040 --> 01:13:36.380 und nicht nur das, es ist auch größer als 6. 01:13:36.480 --> 01:13:42.860 7 ist auch größer als 6 und deswegen komme ich jetzt hier in das IF 01:13:42.860 --> 01:13:43.180 rein. 01:13:44.860 --> 01:13:49.500 Die Invariante ist, wie ihr hier schon seht, dass links von dem I sind 01:13:49.500 --> 01:13:53.080 nur Elemente, die kleiner sind als das kleine Pivot-Element und was 01:13:53.080 --> 01:13:57.400 jetzt passiert, ich erhöhe und niedrige jetzt J so lange, bis hier was 01:13:57.400 --> 01:14:00.900 Kleineres steht, was was nicht mehr größer ist als die 6. 01:14:01.120 --> 01:14:05.020 Das muss ich nur einmal erniedrigen und rechts von dem J stehen dann 01:14:05.020 --> 01:14:11.020 nur Elemente, die tatsächlich auch größer sind als mein rechtes Pivot 01:14:11.020 --> 01:14:13.500 -Element, also in dem Fall jetzt genau. 01:14:14.520 --> 01:14:17.500 Das war jetzt die Waldschleife, die bricht jetzt hier ab, weil ich die 01:14:17.500 --> 01:14:17.980 0 habe. 01:14:19.640 --> 01:14:29.100 Dann tausche ich die 0 mit der 5, AK und AJ, ich tausche die 0 mit der 01:14:29.100 --> 01:14:29.380 7. 01:14:31.500 --> 01:14:37.580 Von der 7 weiß ich jetzt schon, dass sie größer ist und setze das J um 01:14:37.580 --> 01:14:38.300 1 runter. 01:14:38.800 --> 01:14:41.100 Und jetzt, was ich jetzt noch machen muss, jetzt muss ich noch 01:14:41.100 --> 01:14:46.720 schauen, das was jetzt an der Stelle AK gelandet ist, ist das hier 01:14:46.720 --> 01:14:47.060 richtig? 01:14:47.460 --> 01:14:51.120 Nein, das ist hier nicht richtig, weil die 0 ist kleiner als die 3. 01:14:51.260 --> 01:14:53.380 Das heißt, die 0 und die 5 müssen wir noch tauschen. 01:14:53.480 --> 01:14:55.200 AK und AI müssen wir tauschen. 01:14:58.650 --> 01:15:00.790 I um 1 erhöhen, K um 1 erhöhen. 01:15:05.730 --> 01:15:08.770 Und jetzt mit 8 und 4, jetzt ist es nicht mehr so spannend, was 01:15:08.770 --> 01:15:09.250 passiert. 01:15:12.130 --> 01:15:19.150 Es passiert wieder, ich gucke mir die 8 an, die 8 ist größer als 3, 01:15:19.270 --> 01:15:20.570 aber auch größer als die 6. 01:15:21.170 --> 01:15:24.070 Die J steht schon auf etwas, was kleiner ist. 01:15:24.210 --> 01:15:26.070 Das heißt, ich kann die 4 und die 8 tauschen. 01:15:30.770 --> 01:15:33.610 Ich werde J um 1 erniedrigen und K um 1 erhöhen. 01:15:34.570 --> 01:15:36.690 Und dann sieht man jetzt auch schon, dass wir fertig sind. 01:15:37.090 --> 01:15:42.130 Und das ist jetzt auch der Fall, weil jetzt J tatsächlich kleiner ist 01:15:42.130 --> 01:15:42.570 als K. 01:15:42.730 --> 01:15:44.570 Das heißt, die Waldschleife bricht ab. 01:15:45.190 --> 01:15:50.710 Wir erniedrigen I um 1, erhöhen J um 1 und tauschen dann noch unsere 01:15:50.710 --> 01:15:52.810 Pivot -Elemente jeweils hierhin. 01:15:54.390 --> 01:15:55.610 Das ist der letzte Schritt. 01:16:02.380 --> 01:16:06.500 Und dann sind wir fertig und dann haben wir unseren Array tatsächlich 01:16:06.500 --> 01:16:10.280 in drei Teile zerlegt mit zwei Pivot-Elementen anstatt nur in zwei 01:16:10.280 --> 01:16:11.820 Teile, wie wir es vorher gemacht haben. 01:16:14.840 --> 01:16:17.100 Und ist es tatsächlich... ja, ist da eine Frage? 01:16:21.660 --> 01:16:22.120 Wie bitte? 01:16:26.710 --> 01:16:28.930 Genau, 5 und 4 sind jetzt noch nicht sortiert. 01:16:29.430 --> 01:16:32.250 Das war tatsächlich nur eine Partitionierung mit dem Array. 01:16:32.370 --> 01:16:37.930 Das Einzige, was gemacht wurde, ist, dass die Zahlen, die kleiner sind 01:16:37.930 --> 01:16:41.210 als 3 nach links sortiert wurden, die Zahlen zwischen 3 und 6 in die 01:16:41.210 --> 01:16:43.810 Mitte und die Zahlen größer als die 6 nach rechts. 01:16:43.930 --> 01:16:46.330 Hier müsste auch die 8 und die 9 noch vertauscht werden. 01:16:46.770 --> 01:16:50.090 Um tatsächlich den kompletten Array zu sortieren, müssen wir das nicht 01:16:50.090 --> 01:16:53.210 nur einmal machen, sondern jetzt wieder, wie bei dem Original 01:16:53.210 --> 01:16:54.350 -QuickSort -Rekursiv. 01:16:54.390 --> 01:16:57.090 Wir müssen das jetzt für das Intervall, das zufällig schon sortiert 01:16:57.090 --> 01:17:01.070 ist, das Intervall und das Intervall das gleiche mit zwei Pivot 01:17:01.070 --> 01:17:03.710 -Elementen nochmal machen. 01:17:04.950 --> 01:17:13.350 Und erst wenn wir in dem Fall angekommen sind, dass tatsächlich nur 01:17:13.350 --> 01:17:16.690 noch ein Element übrig ist, dann bricht die Rekursion ab. 01:17:18.570 --> 01:17:22.030 Und wir sind fertig und können dann das Intervall zusammensetzen. 01:17:22.330 --> 01:17:24.970 Das war jetzt nur ein Partitionierungsschritt, wie vorhin zur 01:17:24.970 --> 01:17:25.810 Veranschaulichung. 01:17:26.050 --> 01:17:27.530 Das geht jetzt genauso weiter. 01:17:28.610 --> 01:17:30.070 Gibt es sonst noch Fragen dazu? 01:17:32.850 --> 01:17:33.090 Okay. 01:17:34.610 --> 01:17:34.910 Gut. 01:17:37.070 --> 01:17:37.330 Genau. 01:17:37.490 --> 01:17:40.330 Und es gibt auch eine Analyse dazu, die zeigt, dass es tatsächlich 01:17:40.330 --> 01:17:44.130 besser ist als das ursprüngliche QuickSort mit einem zufällig 01:17:44.130 --> 01:17:44.930 gewählten Pivot. 01:17:45.290 --> 01:17:49.210 Da ist die Anzahl von erwarteten Vergleichen ungefähr 2N Log N. 01:17:50.550 --> 01:17:56.110 Und 2012 hat eine Analyse von Wild und Nebel gezeigt, dass das 01:17:56.110 --> 01:18:00.890 Jaroslawski -QuickSort, das auch wie gesagt in der Praxis verwendet 01:18:00.890 --> 01:18:06.090 wird, eine Anzahl von erwarteten Vergleichen von 1,9N Log N minus 2 01:18:06.090 --> 01:18:10.850 ,46N plus was in O von Log N verwendet, also tatsächlich besser ist 01:18:10.850 --> 01:18:14.310 als das QuickSort mit einem Pivot-Element. 01:18:16.730 --> 01:18:17.490 Okay. 01:18:18.510 --> 01:18:22.130 Es ist natürlich immer noch ein vergleichsbasiertes Sortieren. 01:18:22.510 --> 01:18:29.350 Das heißt, die Laufzeit ist bestenfalls in O von N Log N. 01:18:30.470 --> 01:18:34.990 In Omega von N Log N, wie ihr eben die untere Schranke gezeigt habt 01:18:34.990 --> 01:18:37.030 für vergleichsbasiertes Sortieren. 01:18:37.890 --> 01:18:42.410 Gibt es zu QuickSort oder zu vergleichsbasiertem Sortieren jetzt noch 01:18:42.410 --> 01:18:42.830 Fragen? 01:18:46.300 --> 01:18:48.780 Dann würde ich nämlich weitermachen. 01:18:49.120 --> 01:18:55.000 Das wurde ja auch schon kurz angesprochen von Herrn Hofheinz gerade. 01:18:56.460 --> 01:18:58.020 Ganzzahliges Sortieren bzw. 01:18:58.800 --> 01:18:59.780 Alternativen dazu. 01:18:59.920 --> 01:19:01.680 Wir wollen die untere Schranke doch brechen. 01:19:03.960 --> 01:19:04.840 Geht es? 01:19:05.000 --> 01:19:06.060 Wurde schon beantwortet. 01:19:06.140 --> 01:19:09.340 Es geht, indem wir einfach... Es geht natürlich nicht mit 01:19:09.340 --> 01:19:10.980 vergleichsbasiertem Sortieren. 01:19:11.060 --> 01:19:12.320 Das wurde in der Vorlesung bewiesen. 01:19:12.320 --> 01:19:15.720 Aber wenn wir alternative Ansätze finden, wie wir Dinge sortieren, 01:19:16.060 --> 01:19:17.280 dann können wir auch z.B. 01:19:17.400 --> 01:19:18.740 in linnerer Zeit sortieren. 01:19:21.220 --> 01:19:22.320 Und... Genau. 01:19:22.480 --> 01:19:24.740 Eine Möglichkeit davon ist eben BucketSort. 01:19:26.620 --> 01:19:31.080 Wenn ich... Also eine Möglichkeit, wo man BucketSort anwenden kann, 01:19:31.460 --> 01:19:35.680 ist, wenn ich weiß, dass es nur ganze Zahlen sind, die im Intervall 01:19:35.680 --> 01:19:39.840 von 1 bis K liegen, dann ist sortieren möglich in O von N plus K. 01:19:40.260 --> 01:19:43.000 Nochmal kurz, wie das dann aussieht vielleicht. 01:19:43.720 --> 01:19:45.360 Ihr habt es ja auch schon in der Vorlesung gesehen. 01:19:45.700 --> 01:19:46.800 Die Idee ist ganz einfach. 01:19:46.860 --> 01:19:48.440 Ich sortiere einfach in Eimer ein. 01:19:49.160 --> 01:19:56.360 Also wenn wir jetzt hier Eimer haben, dann kann der Array, solange N 01:19:56.360 --> 01:20:00.180 größer gleich K ist, wenn ich weiß, mein Array ist viel länger als die 01:20:00.180 --> 01:20:03.480 Anzahl von Buckets, die ich habe oder ungefähr gleich lang, dann bin 01:20:03.480 --> 01:20:05.320 ich tatsächlich in linearer Zeit. 01:20:05.620 --> 01:20:08.360 Das heißt, auch wenn ich hier meine ganzen Zahlen nehme, die ich von 01:20:08.360 --> 01:20:08.980 vorhin habe, 01:20:17.800 --> 01:20:20.980 und eben 0 und 9 darf ich jetzt nicht nehmen, weil wir haben jetzt 01:20:20.980 --> 01:20:23.520 gesagt, nur Zahlen zwischen 1 und 18 sind erlaubt, 01:20:33.040 --> 01:20:36.640 dann kann ich einfach sortieren, indem ich in die eine einsortiere. 01:20:36.780 --> 01:20:51.220 Also ich würde jetzt hier 1 und dann 8, 5, 1, 2, 3, 4, 5, 7, 8, 9, 10, 01:20:51.220 --> 01:20:54.960 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 01:20:54.960 --> 01:20:56.860 28, 29, 30, 32, 33, 34, 34, 35, 36, 37, 38, 39, 40, 40, 41, 42, 43, 01:20:56.860 --> 01:20:56.860 44, 45, 46, 47, 48, 48, 49, 50, 50. 01:20:57.340 --> 01:21:03.440 Und wenn ich die jetzt dahinter füge, dann habe ich die Liste 1, 1, 2, 01:21:03.860 --> 01:21:07.460 3, 4, 4, 5, 5, 7 und 8, 8. 01:21:07.700 --> 01:21:10.900 Damit hab ich sortiert und ich musste die Liste nur einmal durchgehen. 01:21:11.320 --> 01:21:14.600 Und insbesondere war kein einziger Vergleich nötig. 01:21:14.720 --> 01:21:17.080 Ich musste keinen einzigen Elementvergleich vornehmen. 01:21:17.580 --> 01:21:23.360 Und deswegen gilt die untere Schranke Und damit kann man noch ganz 01:21:23.360 --> 01:21:26.000 viele andere tolle Sachen machen, die ich heute auch eigentlich machen 01:21:26.000 --> 01:21:29.300 wollte, aber ich sehe gerade, dass die Zeit schon fast vorbei ist. 01:21:29.660 --> 01:21:34.060 Ich denke, dass der Lukas dann nächste Woche nochmal ausführlich auf 01:21:34.060 --> 01:21:35.660 Ganzteiliges sortieren bzw. 01:21:36.180 --> 01:21:41.340 sortieren, wenn wir gewisse Annahmen über die Eingabe treffen können, 01:21:41.680 --> 01:21:42.440 machen wird. 01:21:42.960 --> 01:21:47.180 Und ja, vielen Dank für eure Aufmerksamkeit und eine schöne Woche.