WEBVTT

00:00.640 --> 00:02.160
So, schönen Tag.

00:02.260 --> 00:04.680
Grüße Sie zur Fortsetzung der Vorlesung effizienter Algorithmen.

00:05.780 --> 00:10.340
Wir haben gerade ganz kurz angesprochen, dass Sie jetzt die Bewertung

00:10.340 --> 00:12.340
machen, die Vorlesungsbewertung.

00:12.800 --> 00:16.140
Das ist etwas, was wir ja am KIT, beziehungsweise insbesondere an der

00:16.140 --> 00:18.260
Fakultät seit vielen, vielen, vielen Jahren machen.

00:18.360 --> 00:21.080
Unsere Fakultät war Vorreiter bei Vorlesungsbewertungen.

00:21.540 --> 00:25.260
Das Dumme ist nur, dass bei der Art, wie ich Vorlesungen halte, mit

00:25.260 --> 00:28.720
Aufzeichnungen, die Zahl der anwesenden Studierenden in der Vorlesung

00:28.720 --> 00:32.920
leider geringer ist als die Zahl der tatsächlichen Hörer.

00:33.040 --> 00:37.800
Deswegen finde ich immer diese Bewertungen anhand derjenigen, die in

00:37.800 --> 00:40.640
der Vorlesung sitzen, etwas schwierig, weil das ein kleiner Ausschnitt

00:40.640 --> 00:40.860
ist.

00:41.300 --> 00:44.520
Natürlich sind das diejenigen, die das größte Interesse haben, das

00:44.520 --> 00:45.340
live zu erleben.

00:45.440 --> 00:46.540
Deswegen ist das auch ganz richtig.

00:47.020 --> 00:50.320
Aber ich lege Wert auf eine sinnvolle Bewertung.

00:50.840 --> 00:53.380
Ich habe das sonst oft auch so gemacht, dass wir dann die Vorlesungen

00:53.380 --> 00:56.820
einfach in Übungen bewertet haben, weil dann, wenn wir schnell da

00:56.820 --> 00:58.920
sind, diesmal läuft es halt so, ist auch in Ordnung.

01:00.100 --> 01:03.180
Ansonsten, wenn Sie Rückmeldungen zur Vorlesung haben, können Sie auch

01:03.180 --> 01:08.180
so gerne uns über Forum oder E-Mails Rückmeldungen schicken.

01:08.500 --> 01:10.500
Das nehmen wir immer gerne entgegen.

01:11.100 --> 01:13.080
Lassen Sie uns jetzt kurz wieder zu dem kommen, was wir in der

01:13.080 --> 01:13.740
Vorlesung machen.

01:13.860 --> 01:20.240
Wir sind dabei, uns jetzt mit Such- und Sortierproblemen zu

01:20.240 --> 01:20.820
beschäftigen.

01:20.820 --> 01:23.960
Nachdem wir ja die algebraischen Probleme hinter uns gelassen haben,

01:24.040 --> 01:26.440
hatte ich letztes Mal nochmal etwas gezeigt zur schnellen

01:26.440 --> 01:30.020
Projekttransformation, zu den Werkzeugen, die wir haben für diese

01:30.020 --> 01:33.800
Verfahren, Verbindungsstrukturen und ähnlichem.

01:34.000 --> 01:39.500
Und jetzt kommen wir also wieder zu den Such- und Sortierverfahren,

01:39.720 --> 01:44.140
eines der Standardprobleme bei effizienten Algorithmen.

01:44.140 --> 01:48.480
Und ich hatte Ihnen dazu meine Bemerkungen gemacht, zu den Grundlagen,

01:48.600 --> 01:51.660
Datenstrukturen, die wir haben, wie wir eigentlich bewerten, wie der

01:51.660 --> 01:52.460
Aufwand ist.

01:52.920 --> 01:57.340
Wir hatten dann gesehen, welche Probleme da eigentlich zu behandeln

01:57.340 --> 02:00.920
sind, nämlich Suchprobleme, Sortierprobleme und ähnliches.

02:00.980 --> 02:03.600
Eine ganze Variante von verschiedenen Problemen, die wir uns angeguckt

02:03.600 --> 02:03.940
haben.

02:04.560 --> 02:06.860
Ich habe Ihnen etwas über Lexikon-Operationen erzählt.

02:07.800 --> 02:10.420
Es war klar, dass wir hier die Anzahl der Vergleiche als wesentliches

02:10.420 --> 02:11.080
Maß haben.

02:11.080 --> 02:14.740
Wir haben uns die Standardverfahren nochmal kurz angeguckt.

02:14.780 --> 02:15.640
Die kennen Sie ja alle.

02:15.820 --> 02:19.720
Also hier das Sortieren durch Auswahl mit quadratischem Verhalten.

02:20.400 --> 02:23.000
Im besten Fall, im mittleren Fall und im schlechtesten Fall natürlich.

02:23.360 --> 02:26.780
Und dann habe ich Ihnen gezeigt, dass das Minimum nicht mit weniger

02:26.780 --> 02:31.180
als n-1 Operationen oder Vergleichen gefunden werden kann.

02:31.260 --> 02:34.780
Wenn ich n Elementen in der Liste habe, wir haben uns ein Verfahren

02:34.780 --> 02:36.660
für die parallele Bestimmung des Minimums angeschaut.

02:36.660 --> 02:39.820
Und das war nicht so offensichtlich, dass man das so machen kann, aber

02:39.820 --> 02:42.500
es geht halt mit drei Schritten, drei parallele Schritte.

02:43.100 --> 02:48.320
Und ich kann damit also in konstanter Zeit das Minimum bestimmen,

02:48.520 --> 02:52.120
allerdings mit einem sehr hohen Aufwand, nämlich mit n² Vergleichen.

02:52.200 --> 02:57.000
Für ein Problem, das sequenziell lineare Zeit braucht, also deutlich

02:57.000 --> 03:01.680
viel zu hoher Aufwand, was die Anzahl der Possessoren angeht.

03:01.740 --> 03:03.300
Aber es geht in konstanter Zeit.

03:03.860 --> 03:05.440
Das war die interessante Erkenntnis.

03:05.440 --> 03:08.140
Wir haben dann das Sortieren durch Einfügen angeschaut.

03:08.440 --> 03:11.300
Interessanter Vergleich mit der Sortieren durch Auswahl, dass hier der

03:11.300 --> 03:14.280
beste Fall linear ist, der mittlere Fall immer noch quadratisch.

03:14.920 --> 03:18.400
Und wir hatten dann Bubble Sort angeschaut als letztes in der letzten

03:18.400 --> 03:19.400
Vorlesungsstunde.

03:20.400 --> 03:23.280
Und da hatte ich Ihnen nochmal, dann gehen wir hier auch wieder in die

03:23.280 --> 03:25.320
Animation, bzw.

03:25.460 --> 03:26.800
in die Darstellung, in die Präsentation.

03:27.040 --> 03:29.540
Und da hatte ich Ihnen nochmal gezeigt, dass was Sie ja alles kennen

03:29.540 --> 03:33.500
aus Grundlagen der Informatik 1, dass wir hier halt ein Verfahren

03:33.500 --> 03:37.720
haben, bei dem wir in der Standardversion immer quadratisches

03:37.720 --> 03:39.740
Verhalten haben, einer leicht optimierten.

03:40.260 --> 03:44.460
Also das ist klar, dass wir hier immer n mal n-1 halbe Vergleiche

03:44.460 --> 03:49.760
haben, weil wir in der Standardversion, wie es hier steht, halt immer

03:49.760 --> 03:53.920
durchlaufen die restliche Liste.

03:53.920 --> 03:57.360
Das heißt, Anfang n-1 Vergleiche, dann n-2 und so weiter.

03:58.120 --> 04:01.460
Und nur wenn man aufpasst und guckt, ob überhaupt noch verglichen

04:01.460 --> 04:05.740
werden muss, dann hat man im besten Fall lineare Zeit.

04:06.800 --> 04:07.820
In jedem Fall also linear.

04:08.140 --> 04:12.660
Wenn nicht mehr vertauscht wird, kann es sein, dass man nach n-1

04:12.660 --> 04:13.720
Vergleichen schon fertig ist.

04:14.300 --> 04:17.200
Wenn man von links nach rechts das macht, hat man auch eine gewisse

04:17.200 --> 04:19.640
Verbesserung, der sogenannte Shaker Sort.

04:20.400 --> 04:24.100
Aber es ist keine prinzipielle Verbesserung, weil wir im schlechtesten

04:24.100 --> 04:28.740
Fall immer noch quadratische Zeit haben und im Mittel ebenfalls.

04:28.960 --> 04:31.960
Und das Interessante ist, wenn wir uns jetzt eine parallele Variante

04:31.960 --> 04:35.700
anschauen, dann ist das auf einmal ein interessantes Verfahren.

04:35.820 --> 04:36.760
Schauen wir uns das genauer an.

04:37.340 --> 04:40.860
Parallele Variante von Bubble Sort heißt nicht Paralleles Bubble Sort,

04:41.040 --> 04:43.720
PBS, sondern es heißt Odd-Even Transposition Sort.

04:43.720 --> 04:47.220
Es ist ein bisschen anders als Bubble Sort, aber nur ein bisschen.

04:47.940 --> 04:50.860
Das, was wir hier machen, ist, dass wir abwechselnd ungerade und

04:50.860 --> 04:52.920
gerade Paare von Daten vergleichen.

04:52.960 --> 04:53.540
Was heißt das?

04:53.600 --> 04:55.200
Was ist ein ungerades und ein gerades Paar?

04:55.660 --> 04:58.540
Also wenn wir hier unsere... meinetwegen, wir haben Elemente eine

04:58.540 --> 05:03.300
Position 1, 2, 3, 4, 5, 6.

05:04.340 --> 05:07.940
Was sind die ungeraden Paare?

05:07.940 --> 05:15.080
Das sind Paare, bei denen die erste Position des Paares ungerade ist.

05:15.240 --> 05:18.960
Also die ungeraden Vergleiche wären diese hier, bei einer Folge mit

05:18.960 --> 05:20.140
sechs Elementen.

05:20.680 --> 05:27.380
Danach, wenn j ungerade ist, j gleich 1 bis n, machen wir n halbe

05:27.380 --> 05:27.940
Vergleiche.

05:28.860 --> 05:32.680
Und zwar vergleichen wir jeweils, wenn es ungerade ist, das erste

05:32.680 --> 05:36.180
Element ist ungerade, das zweite ist gerade, deswegen 2i minus 1 und

05:36.180 --> 05:36.660
2i.

05:37.380 --> 05:41.060
Wenn es gerade ist, dann werden die an den geraden Positionen

05:41.060 --> 05:42.560
verglichen mit ihren Nachbarn.

05:42.940 --> 05:46.080
Hier am Ende natürlich eigentlich auch, also dann nehmen wir mal an,

05:46.180 --> 05:52.100
dass wir hier unendlich stehen haben, dann kann man das auch so, dann

05:52.100 --> 05:53.380
wären das hier auch drei Vergleiche.

05:53.740 --> 05:59.340
Da das hier immer das Ergebnis 6 hat, weil hier wird nichts

05:59.340 --> 06:03.220
vertauscht, ist es klar, dass wir auf den Vergleich auch verzichten

06:03.220 --> 06:03.620
könnten.

06:03.620 --> 06:08.360
Nur für die Korrektheit dieses Algorithmus muss ich annehmen, dass ich

06:08.360 --> 06:10.140
auch ein Element Sn plus 1 habe.

06:10.820 --> 06:16.100
Dieses CompX steht für Compare Exchange, das heißt ich vergleiche und

06:16.100 --> 06:16.720
vertausche.

06:16.820 --> 06:20.180
Das heißt diese Operation, die da steht, macht folgendes, wenn ich

06:20.180 --> 06:27.640
hier a und b habe, dann kommt hier raus das Minimum von a und b und da

06:27.640 --> 06:31.400
kommt raus das Maximum von a und b.

06:32.400 --> 06:37.380
Das heißt ich schreibe immer das Maximum nach rechts, da wo die

06:37.380 --> 06:38.140
Fallspitze ist.

06:38.160 --> 06:41.520
Die Fallspitze deutet immer an, wohin das Maximum geschrieben wird.

06:42.000 --> 06:44.840
Das ist ein Comparison Exchange, Vergleich und Vertauschen.

06:46.360 --> 06:49.840
Und das Ganze steht hier, wird jetzt in mal gemacht, das heißt ich

06:49.840 --> 06:55.060
müsste jetzt hier noch entsprechend weitere Vergleiche hinschreiben.

06:56.980 --> 07:01.100
Und das habe ich hier 1, 2, 3, 4, 5, 6.

07:01.200 --> 07:07.620
Und die Behauptung ist, nach 6 solchen Schritten bin ich mit dem

07:07.620 --> 07:10.060
Algorithmus fertig.

07:10.280 --> 07:12.700
Danach ist die Folge sortiert.

07:13.660 --> 07:17.160
Also dieses 1, 2, 3 bis 6 ist ja hier nur die Position angegeben, da

07:17.160 --> 07:18.360
stehen irgendwelche Elemente.

07:19.000 --> 07:20.360
Die Behauptung ist, danach ist es sortiert.

07:21.500 --> 07:23.340
Also es ist nicht genau Bubble Sort.

07:23.440 --> 07:26.400
Bei Bubble Sort bin ich ja sequenziell durchgelaufen.

07:27.120 --> 07:30.620
Hier sage ich, ich muss ja nicht sequenziell durchlaufen, ich kann ja

07:30.620 --> 07:33.560
die Vergleiche hier auch parallel machen, die unabhängig sind.

07:33.780 --> 07:36.140
Das ist im Prinzip die ganze Idee dahinter.

07:36.140 --> 07:44.240
Ich mache so viele Fahrweisevergleiche wie möglich, gleichzeitig kann

07:44.240 --> 07:50.760
ich halt nur 1 mit 2 und 3 mit 4 vergleichen, aber nicht 2 mit 3.

07:51.500 --> 07:57.480
Weil ich dann ja Konflikt habe beim Zugriff auf die Elemente.

07:57.480 --> 08:01.620
Stellen Sie sich einfach vor, Sie haben hier jeweils Prozessoren, die

08:01.620 --> 08:02.120
das machen.

08:02.580 --> 08:06.380
Nehmen Sie an, Sie haben hier im Prinzip n Prozessoren, die so

08:06.380 --> 08:07.320
durchnummeriert sind.

08:07.440 --> 08:12.460
Die haben jeweils ein Element in ihrem Speicher und kommunizieren mit

08:12.460 --> 08:17.560
ihren Nachbarn und vergleichen und vertauschen ihre Elemente.

08:18.140 --> 08:20.600
Sie können auch annehmen, dass es Prozessoren sind, die irgendwelche

08:20.600 --> 08:21.700
großen Dateien haben.

08:21.700 --> 08:26.420
Und Sie wollen jetzt einfach dafür sorgen, dass insgesamt am Ende Sie

08:26.420 --> 08:28.660
eine aufsteigende Folge von Daten haben.

08:29.360 --> 08:32.660
Und die jeweiligen Dateien in den Prozessoren werden miteinander

08:32.660 --> 08:36.980
verglichen, werden zusammengebaut und dann in der Mitte sortiert und

08:36.980 --> 08:38.500
wieder auseinandergezogen.

08:38.960 --> 08:42.020
Das heißt, ob das jetzt Elemente sind, einzelne Elemente oder

08:42.020 --> 08:44.680
irgendwelche großen Dateien, spielt ja eigentlich keine Rolle.

08:45.280 --> 08:48.880
Und auch die Vergleichs- und Vertauschungsoperationen müssen nicht

08:48.880 --> 08:51.740
unbedingt ein Vergleich von zwei Zahlen sein, kann auch ein Vergleich

08:51.740 --> 08:53.480
von irgendwelchen größeren Objekten sein.

08:54.040 --> 08:56.340
Aber das Verfahren ist hier so im Prinzip dargestellt.

08:57.600 --> 09:04.940
Von der Syntax her ist es die übliche Pseudoprogrammiersprache Syntax,

09:05.100 --> 09:07.520
die eigentlich genau zeigt, was hier gemacht wird.

09:07.520 --> 09:08.780
Die Analyse ist klar.

09:08.880 --> 09:10.760
Wir haben genau N Schritte da drin.

09:12.560 --> 09:14.380
Parallelitätsgrad ist N halbe.

09:14.440 --> 09:19.400
Wir machen N halbe Vergleiche, also N halbe, ob Prozessoren arbeiten

09:19.400 --> 09:21.420
gleichzeitig jeweils.

09:21.920 --> 09:23.760
Nur die Hälfte kann Vergleich ausführen.

09:23.760 --> 09:31.420
Und deswegen ist der Zeitgewinn bei diesem Verfahren in O von Log N,

09:31.540 --> 09:37.560
weil das beste sekretäre Verfahren hat Aufwand N Log N.

09:37.980 --> 09:40.220
Das habe ich Ihnen noch nicht gezeigt, aber das wissen Sie aus

09:40.220 --> 09:41.440
Grundlagen Informatik 1.

09:42.160 --> 09:47.700
Und wir haben hier N Prozessoren, Parallelitätsgrad, Größenordnung N.

09:47.700 --> 09:51.120
Das heißt, der Zeitgewinn ist logarithmisch, Log N.

09:51.280 --> 09:53.900
Nicht Zeitgewinn N, sondern Zeitgewinn logarithmisch.

09:54.220 --> 09:57.600
Ist nicht allzu doll, Effizienz entsprechend, Log N durch N.

09:58.240 --> 09:59.560
Effizienz ist ziemlich gering.

10:02.000 --> 10:06.300
Das Interessante ist, wenn ich ein lineares Feld von Prozessoren habe,

10:06.380 --> 10:10.360
wie ich das so angedeutet habe, etwas schlecht skizziert, dann ist es

10:10.360 --> 10:14.160
natürlich so, wenn ich jetzt sage, ich muss sortieren, dann kann es

10:14.160 --> 10:17.360
sein, dass das kleinste oder das größte Element zu Anfang hier auch

10:17.360 --> 10:18.620
der linkesten Position ist.

10:19.220 --> 10:23.200
Und das größte Element, das muss aber am Ende ganz recht sein in dem

10:23.200 --> 10:25.620
rechtesten Prozessor, wenn ich aufsteigend sortieren will.

10:26.360 --> 10:29.660
Und wenn ich mir anschaue, wie viel Zeit das braucht, um jetzt in

10:29.660 --> 10:34.060
einer solchen Folge von Prozessoren, die linear miteinander verbunden

10:34.060 --> 10:38.980
sind, ein solches Element darüber zu schieben, dann sind das N-1

10:38.980 --> 10:40.180
Operationen.

10:40.560 --> 10:44.520
Ich kann das ja nur in jedem Schritt nur eine Position weiterschieben.

10:45.680 --> 10:48.980
Das heißt, mit weniger als linearer Zeit kann ich in einem linearen

10:48.980 --> 10:51.060
Feld von Prozessoren überhaupt nicht sortieren.

10:52.740 --> 10:56.620
Und auf einmal habe ich ein Verfahren, das tatsächlich auf einem

10:56.620 --> 11:02.020
linearen Feld in der asymptotisch optimalen Zeit sortiert.

11:02.020 --> 11:03.340
Nämlich lineare Zeit.

11:04.100 --> 11:08.160
Auf dieser Rechnerstruktur geht es nicht besser als in linearer Zeit

11:08.160 --> 11:09.400
und dieses Verfahren macht das.

11:10.640 --> 11:13.760
Insofern ist das durchaus interessant und ich werde Ihnen das jetzt

11:13.760 --> 11:15.820
nochmal genauer zeigen, denn da, was ich Ihnen noch gar nicht

11:15.820 --> 11:20.140
begründet habe, ist, warum ich überhaupt nach N-Schritten hier fertig

11:20.140 --> 11:20.480
bin.

11:21.980 --> 11:25.440
Also, unser Bubble Sort brauchte ja N-Quadrat-Schritte.

11:26.820 --> 11:29.900
Da musste ich ja hier N-Quadrat-Vergleiche machen.

11:30.300 --> 11:32.560
Natürlich mache ich hier N-Halbe-Vergleiche gleichzeitig.

11:34.020 --> 11:37.300
Und wenn ich also mit Bubble Sort vergleiche, habe ich natürlich einen

11:37.300 --> 11:38.480
optimalen Zeitgewinn.

11:39.100 --> 11:41.920
Von N-Quadrat auf N mit N Prozessoren.

11:42.240 --> 11:42.620
Perfekt.

11:43.220 --> 11:45.980
Aber das ist nicht der Zeitgewinn, den ich angeben darf, weil der

11:45.980 --> 11:49.280
Zeitgewinn immer im Vergleich zum besten sequenziellen Verfahren

11:49.280 --> 11:50.500
gemacht werden ist.

11:50.500 --> 11:55.800
Also, wenn ich mit Bubble Sort vergleiche, habe ich hier einen tollen

11:55.800 --> 11:56.380
Zeitgewinn.

11:57.360 --> 12:02.140
Aber ob das wirklich so richtig ist, dass ich damit tatsächlich nach N

12:02.140 --> 12:04.380
-Schritten fertig bin, das ist noch gar nicht sicher.

12:06.340 --> 12:09.940
Denn das Muster der Vergleiche bei Bubble Sort sah anders aus.

12:11.100 --> 12:14.860
Da habe ich ja nacheinander die Elemente miteinander verglichen.

12:15.600 --> 12:17.540
Deswegen muss ich jetzt erstmal beweisen, dass das richtig ist.

12:17.540 --> 12:20.980
Und hier habe ich jetzt nochmal für eine Folge mit 8 Elementen einfach

12:20.980 --> 12:21.900
aufgemalt.

12:22.560 --> 12:25.860
Dieses, was man auch ein Vergleichernetz nennt.

12:26.380 --> 12:29.580
Vergleichernetz ist im Prinzip so eine...

12:29.580 --> 12:33.540
Da malt man sich die einzelnen Elemente, also hier S1, S2 und so

12:33.540 --> 12:34.300
weiter, alle auf.

12:35.260 --> 12:36.100
Diese Liste.

12:36.980 --> 12:38.860
Und malt dann einen senkrechten Strich.

12:39.420 --> 12:40.780
Oder horizontal, ist völlig egal.

12:41.220 --> 12:45.380
Das sind im Prinzip die Positionen in meinem Feld von Elementen, die

12:45.380 --> 12:46.240
ich sortieren möchte.

12:46.240 --> 12:49.140
Und jetzt male ich dort einfach die Vergleiche rein.

12:49.900 --> 12:52.840
Das heißt, dass durch diesen Vergleich hier vorne, dieser erste

12:52.840 --> 12:58.940
Vergleich, der vergleicht und vertauscht die beiden Elemente.

12:59.400 --> 13:03.720
Und das heißt, durch diese Vergleiche werden Elemente hier hin und her

13:03.720 --> 13:05.720
geschoben, entsprechend diesen Größenvergleich.

13:06.300 --> 13:09.300
Und das, was ich mir jetzt anschaue, oder was ich beweisen möchte,

13:09.460 --> 13:14.540
ist, dass ich tatsächlich mit N-odd-even-Schritten fertig bin, also

13:14.540 --> 13:15.920
fertig sortiert habe.

13:16.520 --> 13:20.520
Und ich möchte zeigen, dass das egal ist, ob ich mit einem odd-Schritt

13:20.520 --> 13:22.060
anfange oder mit einem even-Schritt.

13:23.340 --> 13:26.220
Also even-Schritt würde bedeuten, ich fange nicht mit diesem Vergleich

13:26.220 --> 13:29.620
an, wo ich S1 mit S2 vergleiche, sondern der erste Schritt ist einer,

13:29.720 --> 13:33.820
wo ich die mit den geraden Positionen, also S2, S3, S4, S5 vergleiche.

13:34.880 --> 13:36.320
Erst davon soll das unabhängig sein.

13:36.940 --> 13:38.000
Das ist die Behauptung.

13:38.060 --> 13:38.960
Die muss ich jetzt beweisen.

13:39.540 --> 13:40.960
Das mache ich wieder durch Infektion.

13:41.100 --> 13:42.240
Der erste Schritt ist trivial.

13:42.840 --> 13:46.840
Wenn die Folgeart nur ein Element hat, dann bin ich mit einem Schritt

13:46.840 --> 13:47.480
natürlich fertig.

13:48.540 --> 13:49.600
Ja, klar.

13:50.360 --> 13:52.680
Ich hatte aber gesagt, die Folgeart, die Länge, ich habe doch ein N

13:52.680 --> 13:53.440
-plus -erstes-Element.

13:53.980 --> 13:57.880
Ich habe hier so zwei Elemente und das heißt, ich bin auf jeden Fall

13:57.880 --> 13:58.180
fertig.

13:59.160 --> 14:02.280
N gleich zwei, ein odd- und ein even-Schritt reichen immer aus.

14:02.280 --> 14:06.600
Wenn ich so zwei Elemente habe, nur diese beiden Elemente, und ich

14:06.600 --> 14:09.780
fange mit einem odd-Schritt an, dann bin ich fertig.

14:10.160 --> 14:13.340
Wenn ich aber zwei Elemente habe und ich fange mit einem even-Schritt

14:13.340 --> 14:16.820
an, dann ist der even-Schritt dieser hier und der odd-Schritt ist der.

14:18.060 --> 14:19.220
Dann brauche ich zwei Schritte.

14:20.500 --> 14:25.200
Ja, das heißt, deswegen, bei N gleich zwei, bin ich mit einem odd- und

14:25.200 --> 14:28.260
einem even-Schritt, oder einem even- und odd-Schritt, immer fertig.

14:29.160 --> 14:34.940
So, und jetzt kommt das Interessante, das heißt die Induktionsbasis,

14:34.980 --> 14:38.480
jetzt kommt die Induktionsannahme, dass es für N bewiesen ist, und wir

14:38.480 --> 14:40.560
gucken uns eine Folge der Länge N plus 1 an.

14:41.280 --> 14:44.000
Das Vergleichernetz ist hier angegeben, wir nehmen also an, dass das

14:44.000 --> 14:48.260
hier die Situation darstellt für N plus 1, in diesem Fall ist also N

14:48.260 --> 14:52.080
plus 1 gleich 8, und jetzt schauen wir uns das Feld ein bisschen

14:52.080 --> 14:52.700
genauer an.

14:52.820 --> 14:56.840
Und das, was wir genauer machen, ist, dass wir den Weg des maximalen

14:56.840 --> 14:57.760
Datums anschauen.

14:57.760 --> 14:59.600
Das maximale Datum steht irgendwo.

15:00.620 --> 15:05.120
Im schlechtesten Fall wird dieses maximale Datum, das größte Element

15:05.120 --> 15:07.460
in dieser Folge, ganz links stehen.

15:07.500 --> 15:10.860
Dann ist hier ganz links bei S1 das maximale Element.

15:11.640 --> 15:15.840
Und jetzt überlege ich mir, schafft dieses Feld von Vergleichen, also

15:15.840 --> 15:20.800
diese Folge von odd-even-Vergleichen, schafft dieses Element das, oder

15:20.800 --> 15:24.640
diese Vergleichsfolge, das ist tatsächlich, dieses Element, das

15:24.640 --> 15:27.120
maximale Element, ganz an die rechte Position zu bewegen.

15:27.800 --> 15:28.920
Natürlich schafft es das.

15:29.480 --> 15:32.780
In diesem Fall, wenn wir mit dem Odd-Schritt anfangen, hier, dann wird

15:32.780 --> 15:36.440
natürlich sofort im ersten Schritt das maximale Element einen Punkt

15:36.440 --> 15:37.320
nach rechts wandern.

15:38.500 --> 15:41.140
Mit dem nächsten Vergleich wandert es wieder einen Schritt nach

15:41.140 --> 15:43.680
rechts, mit dem nächsten Vergleich wieder nach rechts, wieder nach

15:43.680 --> 15:46.240
rechts, wieder nach rechts, wieder nach rechts, wieder nach rechts.

15:46.240 --> 15:49.340
Wir sind also mit nach n-1 Vergleichen schon fertig.

15:50.280 --> 15:55.140
Beziehungsweise, wir haben eine Folge von n-1, also mit n vergleichen

15:55.140 --> 15:55.660
sind wir fertig.

15:56.740 --> 15:59.680
Wir brauchen gar nicht alle Schritte von dem odd-even.

16:00.280 --> 16:03.200
Wenn wir aber mit einem even-Schritt anfangen, würden wir im ersten

16:03.200 --> 16:06.260
Schritt nicht hier schon das Ding rüberschieben.

16:06.420 --> 16:10.140
Dann wäre da ein even-Vergleich, ein gerader Vergleich, dann würde S2

16:10.140 --> 16:11.240
und S3 verglichen werden.

16:11.780 --> 16:15.220
Und das S1 würde erst im ersten odd-Schritt anfangen zu wandern.

16:15.220 --> 16:18.740
Das heißt, wir bräuchten dann tatsächlich alle Schritte, damit das

16:18.740 --> 16:19.440
Ganze rüberkommt.

16:19.520 --> 16:22.260
Aber es kommt auf jeden Fall insgesamt nach rechts.

16:22.520 --> 16:25.440
Also ich beschränke mich im Folgenden darauf, nur das odd-even

16:25.440 --> 16:26.200
wirklich anzugucken.

16:26.500 --> 16:28.320
Mit even-odd kann man sich gleich überlegen, dass es nach rechts

16:28.320 --> 16:28.640
wandert.

16:29.260 --> 16:35.840
Also, ich habe maximal n-plus-1, ich habe sogar für even-odd, für odd

16:35.840 --> 16:39.240
-even, habe ich hier auf jeden Fall sogar nach n-Schritten das

16:39.240 --> 16:41.320
erreicht, nach n-plus-1-Schritten sowieso.

16:41.320 --> 16:47.340
Dann ist das Element an der Position pn-plus-1 und ich weiß also,

16:47.520 --> 16:49.800
dieses Element geht an die richtige Position.

16:50.360 --> 16:51.760
Nur was ist mit den anderen Elementen?

16:53.100 --> 16:56.000
Das Interessante ist, was passiert denn mit den anderen Elementen?

16:57.280 --> 17:01.880
Das andere Element, das S2, das wandert durch diesen Vergleich eine

17:01.880 --> 17:04.380
Position nach links, an die Position S1.

17:06.060 --> 17:14.440
Das Element S3, das läuft natürlich auch an dem maximalen Element

17:14.440 --> 17:16.420
vorbei, schiebt sich um 1 nach links.

17:16.920 --> 17:21.160
Das heißt, alle Elemente, die hier in diesem Bereich liegen, die

17:21.160 --> 17:25.900
rechts von dem maximalen Element jeweils liegen, die werden nur um 1

17:25.900 --> 17:26.740
nach links verschoben.

17:28.000 --> 17:32.820
Und jetzt mache ich aber folgendes, dass ich sage, ich eliminiere den

17:32.820 --> 17:35.100
Weg des maximalen Datums.

17:36.700 --> 17:40.500
Also ich eliminiere einfach diesen Weg aus meinem Vergleichernetz.

17:41.300 --> 17:42.780
Das heißt, ich lösche das einfach raus.

17:44.900 --> 17:46.500
So, was bleibt denn jetzt übrig?

17:46.500 --> 17:55.360
Ich hatte gerade gesagt, diese Elemente, die hier an der Position S2,

17:55.560 --> 18:01.780
S3, S4 und so weiter bis S8 liegen, die werden natürlich alle an dem

18:01.780 --> 18:04.260
maximalen Element vorbei nach links geschoben.

18:05.380 --> 18:08.020
Und danach werden sie natürlich mit den anderen Elementen

18:08.020 --> 18:08.800
weiterverglichen.

18:10.080 --> 18:15.120
Das heißt, das, was übrig bleibt, sind Vergleiche, bei denen nicht das

18:15.120 --> 18:17.300
maximale Element eine Rolle spielt.

18:18.300 --> 18:20.580
Die anderen Vergleiche bleiben alle gleich.

18:21.100 --> 18:23.540
Und wenn ich mir anschaue, was das eigentlich für ein Vergleichernetz

18:23.540 --> 18:28.740
ist, dann sieht das doch genauso aus wie unser Odd-Even-Transposition

18:28.740 --> 18:30.560
-Sort, aber in diesem Fall ist es ein Even-Odd.

18:31.900 --> 18:34.780
Im Prinzip haben wir hier ja eine Diagonale rausgenommen.

18:35.480 --> 18:39.180
Deswegen brauchen wir eben diese Behauptung, dass sowohl Odd-Even als

18:39.180 --> 18:40.320
auch Even-Odd ausreichen.

18:40.740 --> 18:41.920
Jetzt haben wir hier ein Netz.

18:42.580 --> 18:46.660
Das ist jetzt das Netz, was wir im Prinzip jetzt betrachten müssen.

18:46.820 --> 18:49.100
Das ist genau die Vergleiche, die ausgeführt werden.

18:49.900 --> 18:52.960
Und dadurch, dass das nach links verschoben wurde, haben wir im

18:52.960 --> 18:57.280
Prinzip genauso ein Netz, wie wir das für Endelemente haben.

18:57.280 --> 19:00.980
Und wir wissen nach Ignitionsannahme, dass wir mit einem solchen

19:00.980 --> 19:04.440
Vergleichernetz N-Elemente mit N-Schritten sortieren können.

19:05.740 --> 19:12.900
Und das heißt, diese Folge, dieses ganze Sortiernetz reichte aus, um

19:12.900 --> 19:14.920
insgesamt zu sortieren.

19:15.720 --> 19:18.440
Das heißt, wir sind fertig, die ganze Folge wird in N-plus-1-Schritten

19:18.440 --> 19:18.840
sortiert.

19:19.960 --> 19:26.040
Wir brauchen eventuell N-plus-1-Schritte, um das Element, das maximale

19:26.040 --> 19:28.000
Element, an die Position N-plus-1 zu bringen.

19:29.640 --> 19:33.600
Und der Rest reicht aus, um insgesamt das sortiert zu haben.

19:34.440 --> 19:36.620
Also insofern ist das ein ganz einfacher Beweis.

19:37.240 --> 19:40.100
Dies ist übrigens eine Beweistechnik, die...

19:40.100 --> 19:43.260
Das ist kein formaler Beweis, natürlich.

19:43.380 --> 19:46.900
Formal müsste ich argumentieren über Positionen von Elementen, müsste

19:46.900 --> 19:47.900
das formal modellieren.

19:47.900 --> 19:51.180
Aber ein Beweis hat die Aufgabe, Verständnis zu erzeugen.

19:51.240 --> 19:53.160
Zu überzeugen, dass das richtig ist, was ich sage.

19:53.640 --> 19:56.380
Und ich denke, das mache ich auch durch diese Darstellung, dass ich

19:56.380 --> 19:59.160
also hier das Element, diesen Weg, rausgenommen habe.

20:00.020 --> 20:02.320
Früher habe ich das genannten Beweis durch Folie, weil ich da Folien

20:02.320 --> 20:03.040
verschoben habe.

20:03.540 --> 20:04.980
Inzwischen ist es ein Beweis durch Animation.

20:05.860 --> 20:10.460
Ja, dass ich also hier zeige, dass das Feld, das ich dann bekomme,

20:10.580 --> 20:14.460
tatsächlich genauso ein, in dem Fall ein Even-Odd-Feld ist.

20:14.800 --> 20:17.020
Und damit ist die Korrektheit bewiesen.

20:18.440 --> 20:22.840
Also es ist gar nicht so einfach, Beweise über die Korrektheit von

20:22.840 --> 20:24.100
parallelen Algorithmen zu machen.

20:24.500 --> 20:27.640
Hier sieht man aber einfach, dass das Ding so in Ordnung ist.

20:28.380 --> 20:32.320
Und wir werden noch einige weitere Beweistechniken kennenlernen.

20:33.380 --> 20:36.980
So, das ist also jetzt dieses Bubble Sort, bzw.

20:37.220 --> 20:40.640
Optimal Transposition Sort, ein auf linearen Feldern optimales

20:40.640 --> 20:41.040
Verfahren.

20:41.040 --> 20:47.140
Übrigens gibt es noch einen weiteren schönen Aspekt hier drin.

20:48.440 --> 20:51.720
Ich hatte gesagt, wir betrachten ein lineares Feld von Prozessoren,

20:52.340 --> 20:55.020
die also jeweils miteinander hier kommunizieren.

20:56.340 --> 21:00.040
Das, was passiert, ist im Prinzip jetzt hier in der Zeit ausgerollt.

21:00.780 --> 21:01.860
Ich gehe nochmal wieder zurück.

21:03.540 --> 21:08.900
Das, was hier passiert, ist ja das Ausrollen über die Zeit.

21:10.080 --> 21:13.660
Ja, ich gucke mir an, welche Vergleiche nacheinander gemacht werden.

21:14.300 --> 21:19.700
Jetzt kann ich aber auch sagen, ich baue daraus einfach ein Hardware

21:19.700 --> 21:20.300
-Algorithmus.

21:20.780 --> 21:24.260
Ich baue einfach ein Algorithmus, der macht folgendes, dass er jeden

21:24.260 --> 21:30.400
Vergleich in einen Baustein verwandelt, der zwei Elemente als Eingabe

21:30.400 --> 21:36.580
bekommt und jeweils das Minimum links ausgibt, das Maximum rechts, wo

21:36.580 --> 21:37.400
die Fallspitze ist.

21:38.180 --> 21:42.920
Und jetzt, sage ich also, jeder dieser eingeraten Vergleiche ist ein

21:42.920 --> 21:43.840
Hardware -Baustein.

21:44.400 --> 21:48.020
Die kann ich ganz dicht zusammenpacken, weil wir direkt miteinander

21:48.020 --> 21:48.860
kommunizieren.

21:48.960 --> 21:50.220
Rein lokale Verbindungen.

21:51.220 --> 21:53.760
Also der Ausgang von einem ist der Eingang des Nächsten, die kann ich

21:53.760 --> 21:54.760
ganz eng zusammenpacken.

21:54.860 --> 21:55.940
Wenig Aufwand für Leitung.

21:56.040 --> 21:58.280
Sie erinnern sich, Leitungsaufwand war etwas, was wichtig ist für

21:58.280 --> 21:58.980
Hardware -Algorithmen.

22:00.500 --> 22:05.940
Und wenn ich mir jetzt anschaue, wie ich es einem solchen Hardware

22:05.940 --> 22:10.660
-Algorithmus bewerten müsste, da hätte ich natürlich eine Fläche von

22:10.660 --> 22:11.160
N².

22:12.560 --> 22:13.820
Also natürlich viel Fläche.

22:14.460 --> 22:18.360
N²-Elemente, die dort vergleichen, bzw.

22:18.920 --> 22:21.600
N²½-Vergleichsoperationen.

22:22.340 --> 22:27.520
Und dann kann ich hier eine Folge eingeben.

22:28.540 --> 22:31.260
Das wäre also etwas zu einem gewissen Zeitpunkt.

22:31.300 --> 22:33.400
Das dauert dann Endtakte, bis ich fertig bin.

22:34.400 --> 22:39.020
Aber ich kann sofort nach dem ersten Vergleich die nächste Folge

22:39.020 --> 22:40.040
eingeben.

22:40.340 --> 22:41.740
Und die nächste Folge eingeben.

22:41.880 --> 22:42.720
Und die nächste Folge.

22:42.820 --> 22:43.480
Und die nächste Folge.

22:45.300 --> 22:50.760
Das heißt, wenn ich das Ganze als Hardware-Baustein realisiere, habe

22:50.760 --> 22:58.000
ich zwar einen Flächenaufwand von N², aber ich habe einen Abstand

22:58.000 --> 23:02.900
zwischen aufeinanderfolgenden Berechnungen, der gerade bedingt ist

23:02.900 --> 23:05.280
durch den Aufwand für einen Vergleich.

23:05.960 --> 23:10.320
Das heißt, dann habe ich auf einmal ein Verfahren, das eine Periode

23:10.320 --> 23:16.580
von 1 zeigt.

23:16.820 --> 23:18.100
Also konstante Periode.

23:19.020 --> 23:21.320
Und ich habe einen Durchsatz von N.

23:22.860 --> 23:29.160
Das heißt, ich habe hier ein Verfahren, wenn ich jetzt sage, ich mache

23:29.160 --> 23:33.380
jetzt viele Sortiervorgänge nacheinander, wie ist der mittlere

23:33.380 --> 23:38.720
Zeitaufwand, den ich pro Sortierfolge eigentlich spendieren muss?

23:39.360 --> 23:43.340
Wenn ich viele Operationen mache, dann habe ich hier konstanten

23:43.340 --> 23:44.200
Aufwand pro Folge.

23:45.100 --> 23:48.680
Ich habe zwar einen zeitlichen Versatz, aber ich bekomme mit

23:48.680 --> 23:51.500
konstantem Abstand die sortierten Folgen herausgeliefert.

23:52.560 --> 23:55.780
Das heißt, ich muss zwar diese gewisse Latenz hier berücksichtigen,

23:55.860 --> 23:59.620
die ich brauche, um nach der ersten Eingabe Ergebnisse zu liefern,

23:59.620 --> 24:01.680
aber dann kommen die mit einer hohen Frequenz raus.

24:02.820 --> 24:06.420
Das heißt, ich habe hier ein sehr interessantes Verfahren, bei dem ich

24:06.420 --> 24:09.400
kleine Bausteine habe, die ich jeweils im HP realisieren muss.

24:09.500 --> 24:12.480
Ein Vergleichsoperator ist sehr leicht zu realisieren, wenige

24:12.480 --> 24:13.100
Transistoren.

24:13.980 --> 24:17.820
Und ich habe lokale Kommunikation, sehr wenig Leitungsaufwand, kann

24:17.820 --> 24:21.620
ich sehr effizient packen und kann damit einen Sortierer bauen, der

24:21.620 --> 24:22.820
also einen hohen Durchsatz hat.

24:24.060 --> 24:26.680
Ein sehr schönes Verfahren, ist auch von darauf gebaut.

24:26.680 --> 24:31.140
So, das ist also jetzt dieses OITS.

24:31.260 --> 24:33.420
Und jetzt gehen wir zurück auf das, was Sie kennen.

24:34.560 --> 24:36.100
Sortierverfahren mit Divide & Conquer.

24:36.180 --> 24:37.120
Sortieren durch Teile.

24:37.840 --> 24:39.500
Anwendung des Prinzips Divide & Conquer.

24:39.860 --> 24:41.900
Algorithmus QuickSort hatte ich schon mal ganz kurz erwähnt.

24:42.020 --> 24:44.820
Kennen Sie auch noch von Grundlageninformatik 1.

24:45.900 --> 24:47.480
Was ist die Idee bei QuickSort?

24:49.800 --> 24:51.940
Ich mache mir das Leben einfacher.

24:52.060 --> 24:53.680
Ich sage, das Sortieren ist mir zu schwierig.

24:54.580 --> 24:56.220
Ich gucke mir erstmal ein Teilproblem an.

24:56.220 --> 24:58.360
Ich nehme mir ein beliebiges Element raus.

24:58.520 --> 25:00.660
Und ein beliebiges Element kann ja auch das erste sein.

25:00.720 --> 25:02.800
Wenn ich eine beliebige Eingabe habe, das erste Element ist ein

25:02.800 --> 25:04.560
beliebiges Element der sortierenden Folge.

25:06.100 --> 25:08.540
Und das ist jetzt ein sogenanntes Pivot-Element.

25:08.780 --> 25:10.200
So nennt man das bei diesem Verfahren.

25:10.960 --> 25:14.240
Und jetzt gruppiere ich meine Folge um.

25:14.700 --> 25:19.640
Und zwar so, dass ich das Element C an die richtige Position bringe.

25:19.640 --> 25:23.560
Die richtige Position heißt, alle Elemente, die links davon sind, sind

25:23.560 --> 25:24.180
kleiner gleich.

25:24.880 --> 25:28.220
Und alle, die rechts davon sind, sind größer als dieses Element C.

25:29.200 --> 25:30.920
Das ist nur ein Umordnungsproblem.

25:31.020 --> 25:34.160
Das heißt, ich habe das Sortierproblem umgewandelt in ein

25:34.160 --> 25:35.220
Umordnungsproblem.

25:38.000 --> 25:39.960
Das heißt, ich habe jetzt zwei Folgen.

25:40.760 --> 25:42.100
S' und S''.

25:42.100 --> 25:44.940
Das sind hier diese Folgen S' und S'.

25:45.400 --> 25:49.020
Und jetzt muss ich ja nur das gleiche nochmal machen.

25:49.540 --> 25:51.280
Auf den Folgen S' und S'.

25:53.180 --> 25:55.320
Das kann ich ja rekursiv weiter so verfolgen.

25:55.760 --> 25:58.580
Das heißt, ich habe das Sortierproblem umgewandelt in ein Problem.

25:59.340 --> 26:02.940
Folgen umzuordnen, sodass ein Element an die richtige Position kommt.

26:03.480 --> 26:07.020
Wenn ich das immer weitermache, bin ich natürlich am Ende fertig.

26:07.080 --> 26:08.620
Ich habe alle Elemente an der richtigen Position.

26:08.880 --> 26:10.260
Und die Frage ist, wie groß ist der Aufwand?

26:10.660 --> 26:11.500
Auch das kennen Sie.

26:13.620 --> 26:15.260
Natürlich kann ich diese...

26:15.260 --> 26:17.740
Das ist erstmal ein wichtiger Punkt, die Aufteilung hier.

26:18.560 --> 26:20.700
In zwei Folgen S' und S'.

26:20.700 --> 26:23.780
Wie macht man die denn in linearer Zeit?

26:24.820 --> 26:25.880
Würde ich das gerne machen.

26:26.540 --> 26:28.200
In linearer Zeit ist das so einfach.

26:28.280 --> 26:31.420
Ich muss doch dieses Element hier mit allen anderen vergleichen, dass

26:31.420 --> 26:32.820
es an die richtige Position bringt.

26:33.880 --> 26:36.420
Das sieht aber zunächst mal gar nicht so aus, dass das in linearer

26:36.420 --> 26:36.980
Zeit geht.

26:38.060 --> 26:40.900
Mit allen Vergleichen, die an die richtige Position bringen, heißt,

26:41.000 --> 26:43.160
ich muss da irgendwas umordnen, das kann aufwendig sein.

26:43.580 --> 26:46.960
Die interessante Idee ist, dass ich das so mache, dass ich zwei Zeiger

26:46.960 --> 26:47.460
verwende.

26:48.900 --> 26:54.240
Und hier jeweils diese Zeiger nach rechts und nach links laufen lasse.

26:54.700 --> 26:56.640
Und die Elemente, die da jeweils...

26:56.640 --> 26:59.760
Ich lasse das hier rüberlaufen, aber hier irgendwann Elemente an

26:59.760 --> 27:00.780
solchen Positionen.

27:01.760 --> 27:04.060
Und ich vergleiche immer die beiden Elemente.

27:05.300 --> 27:09.840
Und wenn die in der falschen Reihenfolge sind, dann vertausche ich

27:09.840 --> 27:10.040
sie.

27:10.860 --> 27:12.420
Was heißt denn falsche Reihenfolge?

27:13.240 --> 27:18.500
Falsche Reihenfolge heißt, das linke Element ist größer als das rechte

27:18.500 --> 27:19.020
Element.

27:21.040 --> 27:24.200
Ich fange jetzt nicht bei dem c an, sondern an der zweiten Position.

27:24.380 --> 27:25.000
Da fange ich an.

27:26.880 --> 27:28.860
Warum ist das richtig, das so zu machen?

27:29.480 --> 27:34.520
Da ich ja am Ende links von dem c Elemente haben möchte, die kleiner

27:34.520 --> 27:38.560
gleich c sind, und rechts davon Elemente, die größer als c sind, weiß

27:38.560 --> 27:44.660
ich, dass ich am Ende, oder dass ich immer, alle Elemente von der

27:44.660 --> 27:48.340
Strich kleiner gleich habe, als alle Elemente von der Zwei Strich.

27:49.180 --> 27:54.280
Das heißt, wenn ich hier ein Element einer Position L habe, oder ein

27:54.280 --> 27:58.020
Element einer Position R, und das Element L wäre größer als das

27:58.020 --> 28:02.820
Element R, dann muss ich die natürlich vertauschen, weil sie ansonsten

28:02.820 --> 28:05.260
nicht richtig angeordnet wären.

28:06.200 --> 28:10.440
Und das mache ich so lange, bis ich im Prinzip hier L und R in der

28:10.440 --> 28:13.320
gleichen Position habe, und dann bin ich fertig.

28:14.040 --> 28:16.440
Dann habe ich ja dafür gesorgt, dass die immer gerade so vertauscht

28:16.440 --> 28:22.240
werden, und das heißt, ich habe auf die Art und Weise eine

28:22.240 --> 28:23.220
Partitionierung erreicht.

28:23.560 --> 28:28.420
Das geht also gerade mit diesen Hin- und Herschieben der Pointer, und

28:28.420 --> 28:33.620
auf diese Art und Weise erreiche ich also in linearer Zeit, mit genau

28:33.620 --> 28:36.580
N plus 1 vergleichen, kann man sich genau überlegen, will ich jetzt

28:36.580 --> 28:39.920
nicht machen, ist alles in Grundlagen Informatik 1 passiert, in

28:39.920 --> 28:41.260
linearer Zeit leicht machbar.

28:41.380 --> 28:42.540
Das ist also dieses Partitionieren.

28:43.060 --> 28:45.520
Die wesentliche Idee, also wenn Sie dann gefragt werden, nach was ist

28:45.520 --> 28:50.300
Quicksort, die wesentliche Idee ist eben diese Aufteilung, dass man

28:50.300 --> 28:52.980
eben das Sortierproblem reduziert auf ein Partitionierungsproblem.

28:53.660 --> 28:54.800
Und das dann rekursiv weiter.

28:54.800 --> 28:58.020
Und dass das in linearer Zeit geht, ist eigentlich relativ

28:58.020 --> 28:59.500
naheliegend, dass das geht.

29:00.360 --> 29:03.000
Auch wenn ich erst sagte, das wäre zunächst mal ein naiven Ansatz,

29:03.000 --> 29:05.280
vielleicht nicht der Fall, aber man sieht ja sehr schnell, dass man

29:05.280 --> 29:06.460
das in linearer Zeit machen kann.

29:07.520 --> 29:08.720
So, wie ist dann der Aufwand?

29:09.820 --> 29:10.760
Also das ist jetzt schwierig.

29:12.000 --> 29:12.800
Die Zeitkomplexität.

29:13.900 --> 29:16.960
Ich habe den Aufwand von Quicksort für folgende Länge N.

29:17.900 --> 29:23.460
Das ist der Aufwand, um zu partitionieren, das ist Größenordnung N,

29:23.460 --> 29:26.100
das ist unser Aufwand fürs Aufteilen.

29:27.740 --> 29:31.940
Und dann muss ich nach dem Aufteilen das gleiche Verfahren anwenden

29:31.940 --> 29:34.920
auf die Folge, die links steht, auf das S-Strich.

29:35.360 --> 29:37.960
Und auf die Folge, die rechts steht, auf das S2-Strich.

29:39.040 --> 29:41.940
Und da drin steht jeweils das S-Strich mit Betragsstrichen dran, also

29:41.940 --> 29:45.320
die Größe der Folge S-Strich und die Größe der Folge S2-Strich.

29:46.200 --> 29:48.160
Muss die Frage, wie sind denn diese Größen?

29:48.200 --> 29:49.420
Die können also sehr unterschiedlich sein.

29:49.960 --> 29:55.940
Wenn ich Pech habe, ist diese Folge S-Strich hier vorne leer.

29:56.760 --> 29:59.320
Das heißt, das Element C stand an der richtigen Position.

30:00.260 --> 30:02.960
Dann habe ich nichts erreicht, beziehungsweise nur sehr wenig.

30:03.120 --> 30:05.360
Ich weiß, dass das Element C an der richtigen Position war.

30:06.300 --> 30:08.940
Das heißt aber, die nächste Folge, die ich betrachten muss, das S2

30:08.940 --> 30:11.380
-Strich, hat eine Länge N-1.

30:12.480 --> 30:13.920
Da brauche ich auch Lineare zeigen.

30:14.780 --> 30:18.520
Und sofort sieht man, wenn die Folge schon vorsortiert war, dann

30:18.520 --> 30:20.440
braucht dieses Verfahren quadratische Zeilen.

30:21.460 --> 30:22.240
Ganz schlecht.

30:22.660 --> 30:27.820
Ich wollte doch besser werden als diese einfachen Verfahren, Auswahl,

30:28.060 --> 30:31.040
Einfügen und Bubble-Sort.

30:31.700 --> 30:33.660
Schlecht ist der Fall O von N².

30:34.460 --> 30:36.900
Jetzt schaue ich mir an, ob ich nicht im besten Fall besser werden

30:36.900 --> 30:37.040
kann.

30:37.100 --> 30:40.380
Wir mussten bei Sortieren durch Einfügen hatten wir im besten Fall der

30:40.380 --> 30:40.800
Lineare.

30:41.240 --> 30:42.600
Wie sieht das denn hier aus?

30:43.360 --> 30:46.680
Im besten Fall sieht man hier folgendes.

30:47.380 --> 30:52.000
Habe ich eine Aufteilung meiner Folgen gerade in zwei gleich große

30:52.000 --> 30:52.400
Folgen.

30:53.000 --> 30:55.700
Die also beide etwa die Größe N½ haben.

30:58.700 --> 31:03.840
Und ich muss jetzt zweimal folgende Größe N½ weiter partitionieren.

31:04.960 --> 31:07.700
Jetzt haben wir hier eine Rekursionsformel, das kennen wir doch.

31:08.060 --> 31:09.220
Das ist Zeituhr von Nlogn.

31:10.480 --> 31:14.100
Zweimal T von N½ plus Linear macht Nlogn.

31:14.340 --> 31:16.720
Wissen wir aus unserer Rekurrenzleitung zu überlegen.

31:17.660 --> 31:19.540
Also bester Fall Nlogn.

31:20.460 --> 31:22.880
Schlechter als bester Fall bei Sortieren durch Einfügen.

31:23.580 --> 31:26.000
Aber natürlich gar nicht so schlecht.

31:26.980 --> 31:33.340
Und das interessante ist, dass wir im Mittel in diesem Fall auch ein

31:33.340 --> 31:34.760
Verhalten von Nlogn haben.

31:34.980 --> 31:35.700
Das zeige ich gleich.

31:36.640 --> 31:39.240
Das war bei den anderen Verfahren bisher nicht der Fall.

31:39.780 --> 31:42.420
Da waren wir im Mittel immer bei N² geblieben.

31:43.300 --> 31:45.560
Wir konnten zwar im besten Fall bis auf Linearverzeichung, das geht

31:45.560 --> 31:46.120
hier nicht.

31:46.800 --> 31:49.440
Aber der Name Quicksort wäre natürlich völlig unberechtigt.

31:49.760 --> 31:52.180
Wenn wir hier immer noch bei N² bleiben würden.

31:53.060 --> 31:55.620
Also schauen wir uns das mittlere Verhalten an.

31:56.980 --> 32:00.920
Und um das zu analysieren, müssen wir einfach sagen, was schauen wir

32:00.920 --> 32:01.300
eigentlich an.

32:01.360 --> 32:03.440
Wir messen die Anzahl der Vergleiche.

32:03.440 --> 32:08.820
Also das V von J sei die mittlere Zahl von Vergleichen bei Aufruf von

32:08.820 --> 32:12.140
Quicksort auf einer Teilliste der Länge J.

32:13.700 --> 32:14.620
Irgendeine Länge.

32:15.980 --> 32:21.460
Und wir nehmen an, dass alle Listenlängen gleich wahrscheinlich sind.

32:21.540 --> 32:23.440
Also wenn wir hier unsere Folgen anschauen.

32:24.040 --> 32:26.420
Das erste Element ist ein beliebiges Element.

32:26.420 --> 32:29.420
Das heißt, die Endposition nach dem Aufteilen...

32:30.100 --> 32:33.640
Ja, das kann jede Position sein, irgendwo kann das Element landen.

32:34.200 --> 32:35.660
Jede Position ist gleich wahrscheinlich.

32:35.980 --> 32:37.180
Das ist die Annahme, die wir haben.

32:37.760 --> 32:39.640
Das ist die endgültige Position des Pivot-Elements.

32:40.600 --> 32:44.460
Und dann weiß ich doch, Anzahl der Vergleiche für eine Folge der Länge

32:44.460 --> 32:46.320
1 und eine Folge der Länge 0 ist natürlich 0.

32:46.420 --> 32:47.200
Da muss ich gar nichts tun.

32:48.000 --> 32:53.080
Wenn ich eine Folge der Länge N habe, dann wende ich also jetzt mein

32:53.080 --> 32:54.120
Divide -and-Conquer, bzw.

32:54.140 --> 32:55.960
mein Quicksort-Verfahren an.

32:56.580 --> 32:59.160
Und jetzt muss ich zunächst mal partitionieren.

33:01.020 --> 33:03.820
Partitionieren, hatte ich gesagt, sind N plus 1 Vergleiche.

33:06.000 --> 33:12.660
Und dann muss ich die linke und rechte Folge noch weiter bearbeiten.

33:13.480 --> 33:15.740
Die linke Folge...

33:15.740 --> 33:19.140
Nehmen wir mal an, wir sind hier an die Position, wenn das hier die

33:19.140 --> 33:20.260
Position I ist.

33:21.180 --> 33:26.500
Dann hat die linke Folge I-1 Elemente, die Folge S' und die Folge S2',

33:26.500 --> 33:28.180
hat N-I Elemente.

33:29.360 --> 33:34.340
Das heißt, das gilt für jede mögliche Position, deswegen Summe I

33:34.340 --> 33:35.240
gleich 1 bis N.

33:37.260 --> 33:39.980
Und, da jede Position gleich wahrscheinlich ist, habe ich hier also

33:39.980 --> 33:42.420
dann noch da Mittel 1 durch N zu rechnen.

33:42.420 --> 33:46.160
Und wenn ich mir das genauer anschaue, dann habe ich hier N plus 1,

33:46.260 --> 33:48.420
das taucht ja jedes Mal auf, plus...

33:48.420 --> 33:51.640
Und jetzt taucht hier immer auf V I-1 und V N-I.

33:52.940 --> 34:02.780
Das heißt, V 1 taucht zweimal auf als 2-1 und als N-N-1.

34:03.680 --> 34:04.520
Und so weiter.

34:04.660 --> 34:07.080
Es tauchen alle genau zweimal auf, alle Folgenlängen.

34:07.900 --> 34:17.240
Das heißt, das hier ist eine Beschreibung der Anzahl der Vergleiche im

34:17.240 --> 34:20.380
Mittel für eine Folgelänge N.

34:20.680 --> 34:22.640
Jetzt ist das noch relativ aufwendig.

34:23.100 --> 34:24.480
Machen wir jetzt ein paar Tricks.

34:25.300 --> 34:32.720
Ich schaue mir an, dass hier N plus 1 mal V N plus 1 minus N mal V von

34:32.720 --> 34:32.920
N.

34:33.480 --> 34:34.260
Kleiner Trick.

34:34.700 --> 34:37.340
Das ist entsprechend dieser eingerahmten Formel.

34:38.180 --> 34:41.360
Gerade N plus 1 mal N plus 2.

34:41.480 --> 34:44.580
Also V N plus 1 ist ja N plus 2 plus 2 durch N plus 1 und so weiter.

34:45.040 --> 34:48.820
2 durch N plus 1 mal N plus 1 gibt also hier zweimal diese Summe.

34:49.200 --> 34:52.060
Jetzt bis N, nicht bis N minus 1.

34:52.600 --> 34:53.700
Und davon ziehe ich ab.

34:53.900 --> 34:58.620
N mal V von N, also N mal N plus 1 minus zweimal diese Summe.

34:58.620 --> 35:02.240
Wenn ich mir das genauer anschaue, dann bleibt da nicht viel übrig.

35:02.760 --> 35:04.620
Das ist gerade zweimal N plus 1.

35:06.540 --> 35:10.620
Das ist diese zweimal N plus 1 plus...

35:11.420 --> 35:16.860
Und da ich hier diese ganzen V von Is dort nochmal abziehe, bleibt

35:16.860 --> 35:18.520
hier nur übrig zweimal V von N.

35:19.200 --> 35:20.160
Alle anderen sind raus.

35:21.220 --> 35:25.620
Das heißt, diese Differenz hier ist gleich diesem Ausdruck.

35:25.620 --> 35:30.880
Und wenn ich das jetzt umgruppiere, steht hier V von N plus 1 ist

35:30.880 --> 35:35.140
gleich 2 plus N plus 2 durch N plus 1 mal V von N.

35:35.420 --> 35:37.280
Ganz einfache Umgruppierung hier.

35:38.760 --> 35:42.400
Diese Gleichung einfach nach V von N plus 1 aufgelöst.

35:42.980 --> 35:44.140
Und ich habe diesen Ausdruck.

35:45.080 --> 35:52.000
Und jetzt ist die Behauptung, dass dieser Wert V von N damit aus O von

35:52.000 --> 35:52.860
N log N ist.

35:54.000 --> 35:55.220
Wie beweist man das?

35:55.300 --> 36:00.500
Zunächst mal zeigt man durch Induktion Folgendes, dass dieses V von N

36:00.500 --> 36:02.640
gleich diesem Ausdruck ist.

36:02.740 --> 36:07.700
Zweimal N plus 1 mal Summe 1 durch I.

36:07.820 --> 36:10.300
I gleich 3 bis N plus 1.

36:10.420 --> 36:11.820
Harmonische Reihe.

36:13.380 --> 36:16.000
Das ist der erste Schritt, dass ich das zeige.

36:16.100 --> 36:18.600
Kann man leicht durch Induktion zeigen, das ist also ganz einfach.

36:19.420 --> 36:21.940
Das ist Induktion, will ich jetzt gar nicht machen, können Sie einfach

36:21.940 --> 36:22.600
durchprobieren.

36:22.720 --> 36:24.860
Das ist also wirklich eine ganz einfache Induktion.

36:25.000 --> 36:29.480
Müssen Sie einmal nur das hier einsetzen und das verwenden,

36:29.580 --> 36:31.700
Induktionsannahme machen und dann haben Sie es schon gezeichnet.

36:31.860 --> 36:35.620
Ganz einfach, dass diese Summe hier oder dass dieser Ausdruck richtig

36:35.620 --> 36:35.960
ist.

36:36.360 --> 36:43.780
Und jetzt machen wir noch diese Abschätzung, dass diese Summe in N log

36:43.780 --> 36:44.320
N liegt.

36:44.320 --> 36:45.800
Ne Quatsch, in log N.

36:46.360 --> 36:48.820
Summe 1 durch I, I gleich 3 bis N plus 1.

36:49.200 --> 36:54.800
Dann hätten wir nämlich N plus 1 mal log N und das ist also dann

36:54.800 --> 36:56.740
großen Ordnung U von N log N.

36:57.220 --> 36:58.540
Und die Überlegung ist folgendes.

36:58.660 --> 37:01.640
Ich summiere diese 1 durch I auf.

37:02.740 --> 37:04.060
Was ist 1 durch I?

37:04.200 --> 37:04.900
Das ist eine Funktion.

37:05.240 --> 37:07.060
1 durch X, unsere Funktion.

37:08.580 --> 37:11.280
Also 1 durch X, schaue ich mir einfach die Funktion an.

37:11.780 --> 37:12.900
Bisschen idealisiert hier.

37:13.660 --> 37:15.400
Das hier ist der Abstand 1.

37:16.080 --> 37:17.940
1 durch I ist hier oben drüber zu sehen.

37:18.140 --> 37:19.820
Also von der Größenordnung stimmt das nicht so ganz.

37:20.240 --> 37:21.500
Unterschiedlich ist Qualierung.

37:21.680 --> 37:26.640
Aber das Wesentliche ist, dass ich hier den Wert 1 durch I abtrage.

37:26.800 --> 37:28.820
Dieser Wert hier ist 1 durch I.

37:29.400 --> 37:36.760
Das heißt, dieses hier, diese Höhe ist 1 durch I.

37:37.780 --> 37:46.200
Und das heißt, wenn ich mir die Fläche anschaue von I minus 1 bis I

37:46.200 --> 37:57.380
unter der Kurve 1 durch X, dann ist diese Fläche hier, also 1 durch I,

37:57.480 --> 38:00.240
1 durch I mal 1 ist gerade diese Fläche.

38:02.560 --> 38:10.700
Und diese Fläche ist doch offensichtlich kleiner gleich der Fläche,

38:10.800 --> 38:14.760
wenn ich hier von I minus 1 bis I integriere, die Funktion 1 durch X.

38:15.020 --> 38:21.720
Und sie ist größer gleich, weil ich ja dann hier noch was abziehe, von

38:21.720 --> 38:25.620
I bis I plus 1, das wäre das, was hier drunter liegt.

38:25.620 --> 38:31.140
Das heißt, ich habe diese Abschätzung, Integral von I bis I plus 1, 1

38:31.140 --> 38:36.740
durch X dx ist kleiner gleich 1 durch I mal 1, kleiner gleich Integral

38:36.740 --> 38:38.500
von I minus 1 bis I, 1 durch X.

38:39.480 --> 38:41.620
Das ist also die ganz einfache Abschätzung hier.

38:42.700 --> 38:48.800
Und wenn ich jetzt das Ganze aufsummiere, dann betrachte ich die Summe

38:48.800 --> 38:55.880
1 durch I, I gleich 2 bis N, ist dann gerade kleiner gleich der Summe

38:55.880 --> 38:56.700
der Integrale.

38:58.040 --> 39:02.600
Und die Summe der Integrale ist dann aber gerade das Integral von 1

39:02.600 --> 39:08.940
bis N, 1 durch X dx.

39:09.520 --> 39:13.200
Und dieses Integral, wissen wir, welchen Wert das hat, das ist gerade

39:13.200 --> 39:20.880
1 plus ln N, Logarithmus dualis, Quatsch, Logarithmus naturalis von N.

39:22.100 --> 39:23.860
Integral von 1 durch X, das kennen wir.

39:30.010 --> 39:36.290
Da steht I plus 1, weil ich da diesen Bereich mir anschaue, deswegen I

39:36.290 --> 39:36.990
bis I plus 1.

39:37.390 --> 39:41.390
Bei dem anderen steht von I minus 1 bis I, weil ich da diesen Bereich

39:41.390 --> 39:41.810
mir anschaue.

39:42.570 --> 39:45.810
Dann habe ich insgesamt hier, weil ich das nach oben abschätze, das

39:45.810 --> 39:50.270
steht jetzt bis I, das heißt ich habe hier Integral von 1 bis N, da

39:50.270 --> 39:54.450
die Summe war von 2 bis N, also habe ich hier eine Abschätzung

39:54.450 --> 39:55.670
logarithmisch.

39:56.250 --> 39:59.450
Da muss ich jetzt nicht ln N hinschreiben, sondern kann auch log N

39:59.450 --> 40:00.850
hinschreiben, das sind nur konstante Faktoren.

40:01.770 --> 40:06.190
Damit habe ich also die Abschätzung, dass diese Summe in log N liegt,

40:06.650 --> 40:09.750
also genauso wächst, nur nicht stärker wächst als log N.

40:09.750 --> 40:15.390
Und damit ist der Ausdruck insgesamt hier in N log N.

40:16.070 --> 40:21.270
Damit habe ich gezeigt, mittleres Verhalten von Twigsort ist in N log

40:21.270 --> 40:21.490
N.

40:21.950 --> 40:24.770
Und damit habe ich einen deutlichen Fortschritt gegenüber den anderen

40:24.770 --> 40:27.850
Verfahren, die ja im mittleren Fall immer quadratische Zeiten haben.

40:29.150 --> 40:32.770
Hier habe ich also jetzt Gleichheit von besten Fall und mittleren

40:32.770 --> 40:35.790
Fall, natürlich nicht bei der konstanten, aber ich bin da im gleichen

40:35.790 --> 40:36.110
Bereich.

40:36.110 --> 40:38.230
Schlechtester Fall immer noch quadratisch.

40:38.850 --> 40:39.570
Ist schlecht.

40:41.650 --> 40:46.210
Übrigens, das Problem hierbei ist, bei dieser Aufteilung, der

40:46.210 --> 40:53.150
schlechteste Fall ist deswegen schlecht, weil ich hier nur die Länge

40:53.150 --> 40:56.210
der Folge nur konstant verkleinere.

40:57.090 --> 41:03.670
Wenn ich es schaffen würde, dass dieser Teil hier immer irgendein N

41:03.670 --> 41:09.570
durch K ist, mindestens irgendein N durch K, also irgendein konstanter

41:09.570 --> 41:14.490
Anteil, vielleicht ein Zehntel oder Siebzehntel oder irgendetwas.

41:14.790 --> 41:17.570
Wenn ich zeigen könnte, ich habe jeweils einen konstanten Anteil

41:17.570 --> 41:24.270
weniger, das erreichen könnte, dann wäre der schlechteste Fall auch N

41:24.270 --> 41:24.550
log N.

41:25.430 --> 41:30.170
Aber ich habe eben keinen konstanten Anteil, die Folgelänge ist hier

41:30.170 --> 41:36.550
nicht N durch irgendwas, sondern die ist halt im schlechtesten Fall

41:36.550 --> 41:39.150
Länge 1, N log N ist schlecht.

41:41.410 --> 41:45.190
Aber wenn ich da einen konstanten Bruchteil jeweils immer abschneiden

41:45.190 --> 41:47.070
könnte, wäre ich schon viel besser.

41:48.710 --> 41:52.690
Dann wäre ich auch im schlechtesten Fall in einem Verhalten N log N.

41:52.690 --> 41:58.430
Damit sehen Sie jetzt, was man tut, um das Verhalten im Mittel zu

41:58.430 --> 41:59.710
analysieren.

42:00.110 --> 42:03.130
Bei diesem Beispiel habe ich das einmal gemacht, ich werde das an

42:03.130 --> 42:05.350
anderen Beispielen noch ein einziges Mal machen.

42:06.510 --> 42:08.830
Ansonsten werden wir das gar nicht weiter betrachten.

42:09.470 --> 42:12.010
Wir müssen natürlich immer Annahmen machen über Verteilung unserer

42:12.010 --> 42:12.470
Elemente.

42:14.210 --> 42:18.130
Also die Schwachstelle ist, dass wir von der Wahl des Pivot-Elements

42:18.130 --> 42:18.930
abhängig sind.

42:19.490 --> 42:22.670
Verbesserungen sind natürlich so, dass Sie sagen, ich nehme einfach,

42:23.570 --> 42:27.430
wenn ich meine Folge hier habe, warum soll ich das erste Element

42:27.430 --> 42:27.730
nehmen?

42:28.730 --> 42:32.750
Der schlechteste Fall lag ja daran, wenn die Folge schon vorsortiert

42:32.750 --> 42:35.930
ist, dann nehme ich doch einfach das mittlere Element von diesen drei.

42:38.110 --> 42:41.170
Und dann habe ich ja für diesen Fall, dass die Folge schon vorsortiert

42:41.170 --> 42:45.710
ist, immer genau die bestmögliche Aufteilung in der Mitte.

42:46.470 --> 42:46.950
Perfekt.

42:47.710 --> 42:53.110
Für diesen schlechtesten Fall hätte ich dann ein Verhalten von N log N

42:53.110 --> 42:53.650
erreicht.

42:54.310 --> 42:58.290
Aber es kann natürlich sein, dass diese drei Elemente, gerade die

42:58.290 --> 43:01.170
ersten drei Elemente meiner Folge sind, die sortiert werden sollen.

43:01.170 --> 43:05.830
Das heißt, ich kann sofort einen schlechten Fall konstruieren, bei dem

43:05.830 --> 43:09.750
genau diese Aufteilung auch dazu führt, dass ich eben nicht einen

43:09.750 --> 43:13.770
festen Bruchteil abschneiden kann, sondern nur konstant viele.

43:14.610 --> 43:16.550
Und damit bin ich wieder nicht weiter gekommen.

43:16.950 --> 43:19.170
Also im schlechtesten Fall immer noch quadratisch.

43:21.090 --> 43:25.110
Ich bin natürlich im besten Fall, bleibe ich immer bei N log N, im

43:25.110 --> 43:25.870
mittleren Fall auch.

43:25.870 --> 43:28.710
Aber ich mache ein bisschen mehr Aufwand, weil ich noch den Median von

43:28.710 --> 43:29.970
drei Elementen bestimmen muss.

43:32.150 --> 43:34.810
Also insofern ist das schon etwas besser.

43:35.630 --> 43:38.210
Ich kann natürlich sagen, ich nehme ein zufälliges Element der Liste.

43:38.990 --> 43:43.170
Wenn ich ein zufälliges Element der Liste nehme, der Erwartungswert

43:43.170 --> 43:51.990
vor die Position ist natürlich eine Position, irgendwas in der Mitte.

43:52.750 --> 43:55.930
Also ein randomisiertes Quicksort, da ist der Erwartungswert der

43:55.930 --> 43:58.330
Laufzeit in O von N log N.

43:59.350 --> 44:04.130
Aber ich muss dann, wenn ich das jeweils zufällig auswähle, kann ich

44:04.130 --> 44:07.110
immer noch Pech haben, dass ich eine quadratische Laufzeit kriege,

44:07.810 --> 44:15.270
aber ich habe dann einen Erwartungswert von N log N, das heißt im

44:15.270 --> 44:17.310
Schnitt werde ich in N log N sortieren können.

44:17.310 --> 44:21.110
Ich muss aber immer zufällig die Position auswählen.

44:21.710 --> 44:22.550
Extra Aufwand.

44:24.070 --> 44:27.670
Jetzt machen wir noch ein, das ist also ein randomisiertes Quicksort,

44:27.850 --> 44:31.750
aber wir könnten natürlich noch eine weitere Verbesserung machen.

44:32.310 --> 44:36.830
Wir könnten einfach sagen, naja, ich bestimme einfach erstmal das

44:36.830 --> 44:38.190
mittlere Element meiner Folge.

44:38.370 --> 44:45.390
Ich sorge dafür, dass ich auf jeden Fall immer am Ende hier lande, in

44:45.390 --> 44:45.690
der Mitte.

44:46.670 --> 44:49.850
Das geht aber nur, wenn ich weiß, welches das mittlere Element ist, so

44:49.850 --> 44:50.950
müsste ich das noch bestimmen.

44:51.330 --> 44:52.370
Den Median bestimmen.

44:53.150 --> 44:56.210
Und wenn Sie das naiv machen, haben Sie leider den gleichen Aufwand

44:56.210 --> 44:56.930
wie beim Sortieren.

44:57.150 --> 44:57.450
Das ist schlecht.

44:57.910 --> 45:00.070
Da kommen wir später noch zu und werden sehen, dass das in linearer

45:00.070 --> 45:05.410
Zeit geht, aber dann hätten Sie in linearer Zeit Median bestimmt, in

45:05.410 --> 45:09.410
linearer Zeit Partitioniert, und sind dann insgesamt, hätten Sie dann

45:09.410 --> 45:14.790
auch im schlechtesten Fall, Quadratische Zeit NlogN, aber der Aufwand

45:14.790 --> 45:16.410
für den Median ist dann relativ hoch.

45:17.090 --> 45:20.170
Also, die erste Idee ist, randomisiertes Quicksort zu nehmen.

45:20.470 --> 45:21.330
Das ist schon nicht schlecht.

45:21.510 --> 45:26.910
Sie bekommen dann schon mal ein ganz gutes Ergebnis.

45:28.010 --> 45:31.930
So, jetzt kann ich aber sagen, ich mach das einfach anders.

45:31.930 --> 45:35.390
Ich wähle mir ein Verfahren, bei dem ich garantieren kann, dass ich

45:35.390 --> 45:36.990
ein richtiges Divide-and-Conquer mache.

45:37.270 --> 45:40.070
Dieses war ja so ein Versuchen, Divide-and-Conquer zu machen, aber es

45:40.070 --> 45:41.010
ist nicht wirklich eins.

45:41.250 --> 45:45.430
Ich möchte ja gerne ein Problem, das groß ist, aufteilen in zwei

45:45.430 --> 45:47.610
Teilprobleme, die kleiner sind.

45:48.370 --> 45:51.750
Und dieses Quicksort ist halt so, dass ich das versuche, und wenn ich

45:51.750 --> 45:54.090
Pech habe, habe ich halt kein richtiges Divide-and-Conquer gemacht,

45:54.530 --> 45:56.350
sondern ich habe nur ein Element rausgebracht.

45:57.670 --> 46:03.070
Wenn ich sage, es muss aber streng aufgeteilt werden, dann mache ich

46:03.070 --> 46:03.690
das so einfach.

46:04.750 --> 46:08.290
Ich teile einfach meine Folge auf, in zwei Folgen.

46:08.430 --> 46:09.670
Das ist also meine Folge S.

46:10.810 --> 46:13.570
Zwei Folgen S' und S''.

46:14.930 --> 46:18.950
Und jetzt sortiere ich die, rekursiv nach diesem Verfahren.

46:21.350 --> 46:23.730
Und anschließend muss ich ja nur die beiden sortierten Listen

46:23.730 --> 46:24.870
verschmelzen.

46:27.890 --> 46:30.310
Dieses Aufteilen in zwei Folgen ist ja ganz einfach.

46:30.830 --> 46:33.090
Da muss ich ja nur sagen, okay, das ist die Aufteilung.

46:34.550 --> 46:36.110
Dann wieder eine Aufteilung.

46:36.190 --> 46:40.030
Das sind ja nur logische Operationen, keine realen Operationen.

46:41.430 --> 46:45.910
Das heißt, das, was ich mache, hier ist ein Beispiel, eine Folge der

46:45.910 --> 46:46.450
Länge 8.

46:47.340 --> 46:51.070
Dieses Aufteilen in Teillisten, das ist ja trivial.

46:51.350 --> 46:54.090
Das heißt nur, ich muss mit diesem Schritt hier anfangen.

46:55.050 --> 46:59.910
Das ist mein erster Schritt, dass ich nebeneinander liegende Elemente

46:59.910 --> 47:02.230
vergleichen muss und sortieren muss.

47:03.410 --> 47:06.450
Also ich mache hier im Prinzip solche...

47:08.170 --> 47:08.830
Ups...

47:08.830 --> 47:11.510
...diese Complex-Change-Operation.

47:13.810 --> 47:14.410
So.

47:15.290 --> 47:18.270
Die muss ich nur vergleichen, also zusammenfügen zu einer sortierten

47:18.270 --> 47:18.630
Liste.

47:19.070 --> 47:20.050
Das habe ich hier gemacht.

47:20.650 --> 47:21.670
Das ist der Aufwand.

47:22.830 --> 47:25.370
Also praktisch der erste Schritt beim Merge Sort besteht darin, dass

47:25.370 --> 47:26.330
ich im Prinzip...

47:26.330 --> 47:28.010
...kann ich also iterativ machen und nicht rekursiv.

47:28.370 --> 47:30.850
Iterativ werden einfach solche Elemente verglichen.

47:31.790 --> 47:36.510
Und danach muss ich das Gleiche im Prinzip mit diesen Benachbarten

47:36.510 --> 47:36.770
machen.

47:37.210 --> 47:38.910
Die beiden, die beiden.

47:41.230 --> 47:43.390
Complex-Change auf Folgen der Länge 2.

47:45.270 --> 47:46.170
Merge ist das.

47:46.370 --> 47:48.550
Das heißt, jetzt habe ich diese beiden Folgen.

47:50.230 --> 47:53.770
Und anschließend mache ich Complex-Change auf diesen beiden Elementen.

47:53.830 --> 47:55.910
Das sind jetzt Folgen der Länge 4.

47:58.470 --> 48:01.830
Also wieder ein Merge-Mischen von zwei sortierten Folgen.

48:02.210 --> 48:02.690
Und ich bin fertig.

48:04.210 --> 48:07.270
Das Ganze geht dann also in 1.

48:08.630 --> 48:11.830
Das ist der erste Schritt, der zweite Schritt, der dritte Schritt.

48:12.310 --> 48:15.470
Bei Folgen der Länge 8, natürlich in logarithmisch vielen Schritten,

48:16.570 --> 48:19.550
muss ich Vergleiche machen bzw.

48:19.670 --> 48:20.810
Merge-Operationen machen.

48:21.390 --> 48:23.050
Logarithmisch viele Schritte.

48:23.630 --> 48:24.790
Und ich muss natürlich hier...

48:25.750 --> 48:29.950
Im ersten Schritt habe ich vier solche Vergleichs-Operationen.

48:29.950 --> 48:32.890
Hier habe ich zwei, da habe ich eine.

48:34.790 --> 48:39.030
Und der Aufwand für jede Vergleichs-Operation wächst jeweils.

48:39.670 --> 48:42.310
Das Mischen, das wissen wir, wie das geht.

48:42.430 --> 48:43.650
Das Verschmelzen.

48:44.350 --> 48:48.790
Also sequenziell geht das in linearer Zeit.

48:50.010 --> 48:53.290
Da habe ich hier viermal konstante Zeit.

48:53.570 --> 48:55.930
Zweimal Aufwand 2.

48:56.730 --> 48:58.430
Einmal Aufwand 4.

48:59.930 --> 49:03.490
Das heißt, der Aufwand insgesamt war immer 4.

49:04.170 --> 49:05.810
In jeder Stufe habe ich Aufwand n.

49:06.510 --> 49:07.490
Und ich bin schon fertig.

49:07.610 --> 49:11.890
Beziehungsweise, wenn ich das anders argumentiere, ich habe log n

49:11.890 --> 49:12.570
Merge -Stufen.

49:13.430 --> 49:18.250
Und der Aufwand besteht also gerade daran, dass ich zweimal Merge-Sort

49:18.250 --> 49:19.790
mache auf folgende Länge in halbe.

49:20.310 --> 49:24.210
Plus den Aufwand für das Verschmelzen.

49:25.350 --> 49:29.030
Und das wissen wir, nach unserer Kursionsgleichung, ist das ein n log

49:29.030 --> 49:29.970
n zu machen.

49:30.190 --> 49:31.550
Also ist das genau n log n.

49:31.990 --> 49:34.190
Das heißt, hier habe ich im schlechtesten Fall n log n.

49:34.970 --> 49:36.270
Ich habe das erreicht, was ich wollte.

49:36.490 --> 49:37.630
n Quadrat ist schlecht.

49:37.890 --> 49:39.670
In schlechtester Fall n log n ist möglich.

49:40.230 --> 49:42.210
Wir wissen, Quicksort hatte n log n im Mittel.

49:42.430 --> 49:44.030
Aber in schlechtester Fall quadratisch.

49:44.090 --> 49:46.770
Jetzt kann ich also auch noch in schlechtestem Fall runterdrücken auf

49:46.770 --> 49:47.330
n log n.

49:48.710 --> 49:49.110
Parallel.

49:50.610 --> 49:51.570
Wie mache ich das?

49:51.570 --> 49:53.750
Das ist doch die Vorlage für ein paralleles Verfahren.

49:55.010 --> 49:58.610
Jede Ebene in diesem Baum, in diesem Verschmelzungsbaum, mache ich

49:58.610 --> 49:59.130
parallel.

50:00.730 --> 50:04.430
Das heißt, ich mache ein parallel Merge-Sort auf Folgen der Länge in

50:04.430 --> 50:04.890
halbe.

50:06.270 --> 50:06.790
Parallel.

50:07.650 --> 50:10.070
Und anschließend mache ich ein paralleles Merge.

50:11.890 --> 50:15.270
Von n heißt, zwei Folgen der Länge in halbe werden verschmolzen.

50:16.650 --> 50:19.270
Und jetzt muss ich mir anschauen, wie ist denn der Aufwand, um

50:19.270 --> 50:20.850
parallel zu verschmelzen.

50:20.850 --> 50:26.190
Sequenziell brauchen wir dafür n Operationen, n-1 Operationen.

50:26.670 --> 50:29.090
Parallel ist die Frage, wie das geht.

50:29.810 --> 50:36.770
Wenn das Ganze, dieses P-Merge von n, logarithmisch geht, dann hätten

50:36.770 --> 50:40.830
wir insgesamt log²n.

50:42.790 --> 50:45.730
Ja, dann wäre dieser Term hier logarithmisch.

50:46.130 --> 50:49.410
Nach unserer Rekursionsformel wissen wir, dann ist das, was rauskommt,

50:49.550 --> 50:50.530
log² von n.

50:51.370 --> 50:54.650
Wenn das Ganze, nehmen wir mal an, wir könnten in konstanter Zeit

50:54.650 --> 50:55.890
verschmelzen.

50:56.270 --> 50:58.790
Zwei sortierte Folgen in konstanter Zeit verschmelzen, klingt

50:58.790 --> 50:59.470
unwahrscheinlich.

51:00.690 --> 51:08.050
Dann hätten wir aber insgesamt einen Aufwand von log n Schichten.

51:09.090 --> 51:10.410
Das wäre also Aufwand log n.

51:10.970 --> 51:13.810
Mit im Prinzip n Prozessoren.

51:14.690 --> 51:15.410
Das wäre optimal.

51:16.610 --> 51:17.750
Tatsächlich geht das.

51:18.830 --> 51:21.630
Aber es ist ein sehr kompliziertes Verfahren, das so hinzukriegen,

51:21.710 --> 51:28.350
dass Sie auf Zeit log n kommen, mit linear vielen Prozessoren.

51:28.470 --> 51:30.650
Oder linear mit der Parallelitätsgrad von n.

51:31.470 --> 51:33.990
Ist aber ein bisschen aufwendig, ist nicht so direkt dieses parallele

51:33.990 --> 51:35.410
Merge Sort, das ist ein bisschen was anderes.

51:36.450 --> 51:37.510
Das zeige ich Ihnen auch nicht.

51:37.670 --> 51:40.630
Ich werde Ihnen jetzt Verfahren zeigen, bei denen wir tatsächlich das

51:40.630 --> 51:43.210
parallele Merge in logarithmischer Zeit hinbekommen.

51:43.210 --> 51:44.410
Also mit logarithmisch vielen Schritten.

51:45.890 --> 51:49.130
Das sind so die klassischen Verfahren für paralleles Sortieren.

51:49.910 --> 51:54.210
Sie machen dieses parallele Merge Sort und kommen dann auf eine Zahl,

51:54.890 --> 51:55.930
Logarithmus zum Quadrat.

51:57.370 --> 51:58.390
Wie kann das gehen?

51:58.530 --> 51:59.650
Also dieses Merge Sort kennen Sie.

52:00.670 --> 52:03.530
Dass es n log n geht, wissen Sie.

52:03.770 --> 52:05.590
Sie wissen auch, dass...

52:05.590 --> 52:06.970
Also nochmal kurz zurück.

52:07.570 --> 52:11.790
Merge Sort ist zwar gut, aber Sie wissen, was ist nach Ihrer

52:11.790 --> 52:15.430
Auffassung das beste sequenzielle Sortierverfahren in der Praxis?

52:16.350 --> 52:17.090
Was würden Sie nehmen?

52:17.810 --> 52:20.030
Eines von denen, die ich Ihnen gezeigt habe, dabei.

52:20.830 --> 52:21.810
Oder würden Sie ein anderes nehmen?

52:24.430 --> 52:25.570
Hat noch einer eine Idee?

52:27.670 --> 52:28.050
Ja.

52:29.550 --> 52:34.310
Aber es ist so, dass das beste ist Deep Sort.

52:35.150 --> 52:37.770
Aber nicht in der Variante, wie Sie das kennengelernt haben, sondern

52:37.770 --> 52:43.430
ein sogenanntes Bottom-up Deep Sort.

52:44.150 --> 52:47.890
Bottom-up Deep Sort ist also eine gewisse Variation von dem

52:47.890 --> 52:52.570
klassischen Deep Sort und ist tatsächlich besser als Quick Sort auch

52:52.570 --> 52:52.890
im Mittel.

52:53.970 --> 52:55.230
Im schlechtesten Fall sowieso.

52:55.750 --> 52:58.870
Aber auch im Mittel besser als Quick Sort.

52:58.990 --> 53:01.650
Deswegen ist Bottom-up Deep Sort das Verfahren der Wahl, wenn Sie das

53:01.650 --> 53:02.570
sequenziell machen müssen.

53:03.150 --> 53:05.110
Um mal zu zeigen, dass das tatsächlich der Fall ist.

53:06.730 --> 53:10.310
Und das ist also sequenziell das beste Verfahren.

53:12.190 --> 53:14.810
Aber jetzt schauen wir uns die Parallelen-Variante an.

53:14.910 --> 53:15.730
Paralleles Sortieren.

53:17.710 --> 53:20.990
Und das erste, was ich Ihnen zeige, ist wieder etwas Odd-Even.

53:21.710 --> 53:24.450
In diesem Fall ein Odd-Even Merge Sort.

53:25.950 --> 53:28.090
Also das Odd-Even haben wir hier schon mehrfach gezeigt.

53:28.170 --> 53:29.810
Wir hatten das auch bei der schnellen Fourier-Transformation.

53:30.030 --> 53:31.110
Da war auch ein Odd-Even gemacht.

53:31.110 --> 53:36.030
Nämlich die Elemente von Ungeraden und Geradenpositionen getrennt

53:36.030 --> 53:36.450
behandelt.

53:36.550 --> 53:37.850
Genau das macht man hier jetzt auch.

53:39.150 --> 53:41.810
Das ist jetzt unser Odd-Even Merge Sort.

53:42.430 --> 53:44.710
Auf Folgen der Länge N.

53:50.110 --> 53:52.010
Ich mache das Ganze.

53:52.630 --> 53:54.110
Machen die beiden Konker-Verfahren.

53:54.930 --> 53:57.410
Also zweimal nebeneinander.

53:57.410 --> 54:01.890
Das sind die beiden rekursiven Aufrufe von Odd-Even Merge Sort für

54:01.890 --> 54:02.610
Folgen der Länge N.

54:03.970 --> 54:08.510
Daraus kommen jetzt zwei Folgen, die sind jeweils aufsteigend

54:08.510 --> 54:09.010
sortiert.

54:10.630 --> 54:13.530
Zunächst mal hatten wir hier eine völlig ungeordnete Liste.

54:14.070 --> 54:16.910
S1 in diesem Fall bis S16.

54:20.830 --> 54:24.310
Und jetzt haben wir also zwei Teilfolgen, die sind aufsteigend

54:24.310 --> 54:24.690
sortiert.

54:24.690 --> 54:27.570
Und jetzt kommt unser Odd-Even Merge.

54:28.030 --> 54:29.270
Paralleles Mischen.

54:30.350 --> 54:31.410
Und wie machen wir das?

54:32.890 --> 54:34.950
Gleiche Idee wie bei schneller Fourier-Transformation.

54:35.770 --> 54:40.570
Wir machen eine Aufteilung nach den geraden und ungeraden Positionen.

54:41.310 --> 54:45.530
Also alle Elemente an den ungeraden Positionen kommen hier rein.

54:45.610 --> 54:47.490
Das Odd-Even Merge, das hier links steht.

54:48.210 --> 54:50.470
Und hier kommen die an die geraden Positionen.

54:51.630 --> 54:53.390
Was ist hier der Vorteil?

54:53.390 --> 54:55.010
Also...

54:55.010 --> 55:00.670
Ich habe zunächst mal zwei Folgen, die sind bereits aufsteigend

55:00.670 --> 55:01.230
sortiert.

55:02.470 --> 55:08.830
Und jetzt mache ich daraus zwei Folgen der ungeraden, der geraden

55:08.830 --> 55:09.530
Elemente.

55:11.530 --> 55:13.010
Naja, was habe ich denn hier?

55:13.150 --> 55:15.170
Da steht ein OEM N halbe.

55:16.190 --> 55:20.750
Wenn ich die Hälfte der Elemente hier rausnehme aus dieser linken

55:20.750 --> 55:27.390
Liste, das sind natürlich gerade hier eine halbe sortierte Folge.

55:28.570 --> 55:33.910
Und die an den ungeraden Positionen hier bei der rechten Liste, das

55:33.910 --> 55:35.170
ist auch eine sortierte Folge.

55:37.530 --> 55:40.250
Und genauso an den geraden Positionen.

55:40.310 --> 55:46.030
Zwei bereits aufsteigend sortierte Folgen, der jeweils halben Größe.

55:47.170 --> 55:48.690
Und jetzt mache ich das einfach rekursiv.

55:49.790 --> 55:53.030
So lange, bis es nicht mehr weiter rekursiv geht.

55:53.110 --> 55:55.650
Das heißt, ich ziehe im Prinzip hier alle raus.

55:56.410 --> 56:00.050
Und dann habe ich irgendwo zwei Elemente, die übrig bleiben.

56:00.930 --> 56:04.410
Diese zwei Elemente, die übrig bleiben, die muss ich einmal mit einem

56:04.410 --> 56:06.950
Vergleich und Vertauschen in die richtige Reihenfolge bringen.

56:07.550 --> 56:09.610
Und dann läuft das Ganze weiter.

56:10.030 --> 56:11.350
Dann kommt das Zusammenbasteln.

56:13.270 --> 56:15.570
Also das erste ist nur so ein Anschaffel, mehrfach gemacht.

56:16.130 --> 56:16.830
Und dann basteln.

56:16.930 --> 56:17.730
Und dann schiebe ich zusammen.

56:18.890 --> 56:25.830
Und einmal weiß ich, hier kommt jetzt eine sortierte Folge raus.

56:26.350 --> 56:31.610
Das Odd-Even-Merge verschmilzt jetzt zwei Folgen der Länge in Viertel

56:31.610 --> 56:34.190
auf eine Folge der Länge in Halbe, die sortiert ist.

56:35.290 --> 56:37.610
Das ist das gleiche Problem, was ich hier schon hatte.

56:38.250 --> 56:42.090
Zwei Folgen der Länge in Halbe, die verschmolzen werden müssen.

56:42.690 --> 56:43.630
Was ist denn der Vorteil?

56:43.630 --> 56:47.970
Das Interessante ist, wenn ich zwei solche Folgen habe, die auf diese

56:47.970 --> 56:52.510
Art und Weise miteinander oder umgruppiert wurden und in eine

56:52.510 --> 56:56.950
sortierte Reihenfolge gebracht wurden, dann reicht dieser eine Schritt

56:56.950 --> 57:02.410
hier unten aus, bei dem ich Elemente an bestimmten Positionen

57:02.410 --> 57:03.450
miteinander vergleiche.

57:05.450 --> 57:09.630
Und diese Position bekomme ich gerade dadurch, dass ich meine beiden

57:09.630 --> 57:12.630
sortierten Teilfolgen perfekt mische.

57:13.370 --> 57:17.330
Und die dann nebeneinander stehenden Elemente vergleiche.

57:19.230 --> 57:23.790
Das heißt, ich habe erstmal immer wieder auseinandergezogen, einmal

57:23.790 --> 57:28.270
einen Sortierschritt gemacht und dann schiebe ich die immer sukzessive

57:28.270 --> 57:28.790
zusammen.

57:29.590 --> 57:33.730
Beziehungsweise, ich mache jeweils einen Schritt mit parallelen

57:33.730 --> 57:34.310
Vergleichen.

57:34.630 --> 57:37.530
Das linkeste und das rechteste Element, die sind auf jeden Fall schon

57:37.530 --> 57:38.510
richtig an der Position.

57:39.210 --> 57:40.750
Was ist denn das linkeste Element?

57:40.750 --> 57:45.390
Das ist das kleinste Element von links.

57:46.730 --> 57:49.910
Ja, das kleinste Element von links ist ja hier zusammengekommen mit

57:49.910 --> 57:51.430
dem kleinsten Element von rechts.

57:52.470 --> 57:56.610
Das heißt, auf jeden Fall, das kleinste Element der gesamten Folge ist

57:56.610 --> 57:59.690
auf jeden Fall das kleinste Element der linken Folge, die da

57:59.690 --> 58:00.210
rauskommt.

58:00.510 --> 58:03.310
Und genauso symmetrisch wie das größte, die brauche ich gar nicht zu

58:03.310 --> 58:03.750
vergleichen.

58:03.750 --> 58:09.030
Und dann habe ich hier, behaupte ich einfach, durch Vergleiche der

58:09.030 --> 58:12.450
Elemente an diesen ganzen Positionen dort, so wie das hier aufgeteilt

58:12.450 --> 58:17.110
ist, liefert mir gerade eine sortierte Reihenfolge.

58:17.790 --> 58:20.960
Behauptung ist, anschließend ist das Ganze insgesamt sortiert.

58:22.330 --> 58:23.570
Ein Vergleichschritt.

58:25.690 --> 58:27.610
Ja, innerhalb der Vergleiche mache ich parallel.

58:28.630 --> 58:30.230
Und das muss man sich überlegen.

58:30.350 --> 58:32.210
Den Beweis, dass das richtig ist, machen wir gerade.

58:33.810 --> 58:36.570
Nehmen wir das mal als gegeben an, dass das so geht.

58:37.210 --> 58:39.410
Dann haben wir also jetzt welchen Zeitaufwand.

58:40.330 --> 58:45.770
Wir haben für, erstmal, Odd-Even-Merge auf Folgen der Länge 2, ist ein

58:45.770 --> 58:47.890
Comparison -Exchange, das ist ein Schritt.

58:49.770 --> 58:53.490
Und dann haben wir den Aufwand für Folgen der Länge N, also zwei

58:53.490 --> 58:55.730
Verschmelzen von zwei Folgen der Länge in halbe.

58:55.730 --> 59:01.050
Das ist der Aufwand, um zwei Folgen der Länge in viertel zu

59:01.050 --> 59:01.830
verschmelzen.

59:02.970 --> 59:04.350
Und ein weiterer Schritt.

59:06.590 --> 59:09.050
Na gut, dieser Aufwand ist sofort abzuschätzen.

59:09.470 --> 59:11.130
Das ist das logarithmische Aufwand.

59:12.850 --> 59:18.050
Und dann weise ich insgesamt das Odd-Even-Merge-Sort von N, weil jetzt

59:18.050 --> 59:21.750
gerade Odd-Even-Merge-Sort hier oben für Folgen der Länge in halbe,

59:21.750 --> 59:24.650
plus der Aufwand für das Odd-Even-Merge.

59:27.190 --> 59:32.090
Und der Aufwand ist log N, also ist insgesamt, das war die Formel, die

59:32.090 --> 59:35.690
wir auf der vorigen Folie hatten, ist das gerade quadratisch in log N.

59:38.230 --> 59:41.050
Was ich Ihnen noch nicht gezeigt habe, ist, dass das hier tatsächlich

59:41.050 --> 59:41.770
richtig ist.

59:42.310 --> 59:43.490
Das ist ja keineswegs offensichtlich.

59:44.270 --> 59:48.210
Warum soll das, also durch den Perfect-Shuffle, die

59:48.210 --> 59:52.250
nebeneinandergestellten Elemente, warum soll das geradezu einer

59:52.250 --> 59:53.350
sortierten Liste folgen?

59:54.210 --> 59:58.150
Nur dieser eine Schritt, diese ausgewählten Operationen, ich mache

59:58.150 --> 01:00:02.590
also einmal, wenn ich kleine Folgen habe, mache ich diesen

01:00:02.590 --> 01:00:06.130
Anfangsschritt und dann, können wir uns das mal anführen, ganz wenige

01:00:06.130 --> 01:00:06.650
Elemente.

01:00:07.150 --> 01:00:12.070
Ich habe eins, zwei, drei, vier.

01:00:12.070 --> 01:00:16.250
Die sind bereits, die wurden also bereits verglichen, die wurden auch

01:00:16.250 --> 01:00:17.870
verglichen, die richtigen Reihenfolge gebracht.

01:00:18.950 --> 01:00:21.930
Und ich weiß, das sind die beiden kleinsten Elemente meiner Folge,

01:00:22.470 --> 01:00:24.910
meinen beiden Folgen, und das sind die beiden größten Elemente.

01:00:25.690 --> 01:00:33.390
Das heißt, anschließend muss ich ja nur noch diese beiden Elemente

01:00:33.390 --> 01:00:33.930
vergleichen.

01:00:36.010 --> 01:00:39.130
Und diese beiden Elemente, das ist genau ein solcher Vergleich.

01:00:39.250 --> 01:00:42.290
Das linke und das rechte Element, die sind schon richtig, in der Mitte

01:00:42.290 --> 01:00:43.130
steht noch ein Vergleich.

01:00:44.090 --> 01:00:48.450
Das ist das zweite Element der Folge links, verglichen mit dem ersten

01:00:48.450 --> 01:00:49.750
Element der Folge rechts.

01:00:50.330 --> 01:00:54.190
Das zweite Element der Folge links, verglichen mit dem ersten Element

01:00:54.190 --> 01:00:55.050
der Folge rechts.

01:00:55.970 --> 01:00:56.810
Das ist der Vergleich.

01:00:57.810 --> 01:00:59.230
Und entsprechend zieht sich das jetzt so durch.

01:01:01.330 --> 01:01:02.450
Wie kann man das beweisen?

01:01:02.570 --> 01:01:06.670
Also hier, das ist klar, Zeitgewinn ist dann gerade in n durch log n,

01:01:06.830 --> 01:01:08.230
das ist schon mal nicht schlecht.

01:01:09.110 --> 01:01:11.530
n durch log n, deutlich besser als log n wie vorher.

01:01:12.310 --> 01:01:18.610
Und die Effizienz ist mit 1 durch log n noch immer nicht optimal.

01:01:18.990 --> 01:01:22.270
Wir haben also nicht konstante Effizienz, nur log n ausgelastet.

01:01:23.410 --> 01:01:26.690
Das ist halt immer noch ein Problem, aber immerhin.

01:01:28.410 --> 01:01:31.830
So, wir sind halt nur auf log²n gekommen und nicht auf log n.

01:01:32.730 --> 01:01:37.030
Und jetzt müssen wir uns mit der Korrektheit beschäftigen.

01:01:37.110 --> 01:01:38.550
Jetzt mache ich einfach eine Vereinfachung.

01:01:40.110 --> 01:01:42.990
Wir haben zunächst mal angenommen, immer bei den Sortierproblemen,

01:01:43.070 --> 01:01:44.310
dass alle Elemente verschieden sind.

01:01:45.470 --> 01:01:46.510
Jetzt mache ich das Gegenteil.

01:01:46.590 --> 01:01:48.370
Nicht, dass alle gleich sind, brauche ich nicht zu sortieren.

01:01:49.070 --> 01:01:52.630
Aber ich sage, ich habe nur zwei verschiedene Elemente.

01:01:52.730 --> 01:01:53.370
0 und 1.

01:01:55.350 --> 01:01:58.510
Und wenn ich die sortiere, habe ich also irgendeine Folge.

01:01:59.490 --> 01:02:02.430
Also irgendeine beliebige Folge mit irgendwelchen Elementen.

01:02:02.930 --> 01:02:07.350
Und anschließend habe ich eine Folge, ab irgendeiner Position stehen

01:02:07.350 --> 01:02:09.110
nur noch Einsen und links davon stehen Nullen.

01:02:09.230 --> 01:02:11.750
Also hier stehen die Nullen, da stehen die Einsen.

01:02:13.190 --> 01:02:14.590
Das ist ja viel einfacher.

01:02:15.610 --> 01:02:17.370
Ich habe ja nur Elemente 0 und 1.

01:02:17.370 --> 01:02:21.650
Ich muss sie nur so umordnen, dass dann hier die Nullen alle links

01:02:21.650 --> 01:02:22.910
sind und die Einsen alle rechts.

01:02:24.250 --> 01:02:26.110
Das ist schon mal ein viel einfacheres Problem.

01:02:27.350 --> 01:02:33.190
Und für dieses Problem, 0-1-Folgen zu sortieren, schauen wir uns jetzt

01:02:33.190 --> 01:02:34.810
unser odd-even-merge an.

01:02:35.930 --> 01:02:37.890
Also, das ist unser odd-even-merge.

01:02:38.710 --> 01:02:40.770
Jetzt haben wir hier die linke und die rechte Folge.

01:02:41.950 --> 01:02:42.990
Was passiert hier?

01:02:42.990 --> 01:02:49.330
Hier zunächst mal, das sagte ich ja, sind unsere bereits sortierten,

01:02:49.550 --> 01:02:55.670
das ist das, was rauskommt, aus den Schritten davor.

01:02:56.630 --> 01:02:59.550
Ich habe hier eine aufsteigend sortierte Folge, da auch eine

01:02:59.550 --> 01:03:00.570
aufsteigend sortierte Folge.

01:03:00.670 --> 01:03:01.510
Gleiches Bild wie vorher.

01:03:02.070 --> 01:03:06.490
Aufsteigend sortiert heißt hier, ab einer gewissen Position stehen nur

01:03:06.490 --> 01:03:08.550
noch Einsen und da auch ab einer gewissen Position.

01:03:09.590 --> 01:03:14.210
Und jetzt zähle ich einfach die Anzahl der Einsen auf der linken Seite

01:03:14.210 --> 01:03:15.230
und auf der rechten Seite.

01:03:15.770 --> 01:03:19.310
Nun ist die Anzahl der Einsen links oder rechts entweder gerade oder

01:03:19.310 --> 01:03:19.850
ungerade.

01:03:22.260 --> 01:03:25.800
Das ist wichtig, weil wir ja dieses odd-even aufteilen.

01:03:26.640 --> 01:03:27.720
Gerade oder ungerade.

01:03:27.760 --> 01:03:33.200
Gerade oder ungerade heißt, das ist irgendein 2a oder 2b, eventuell

01:03:33.200 --> 01:03:33.980
noch plus 1.

01:03:35.240 --> 01:03:40.100
Eine gerade Zahl wäre ein 2a oder eine 2b, ungerade wäre ein 2a plus 1

01:03:40.100 --> 01:03:41.140
oder 2b plus 1.

01:03:42.460 --> 01:03:48.200
Wenn ich jetzt dieses Perfect-on-Shuffle mache, dann nehme ich die

01:03:48.200 --> 01:03:54.540
Hälfte von diesen 2a, eventuell plus 1 Elementen raus und die Hälfte

01:03:54.540 --> 01:03:57.880
von diesen 2b, eventuell plus 1.

01:04:00.580 --> 01:04:09.680
So, das heißt, ich fange mit dem Element an und nehme dann jeweils das

01:04:09.680 --> 01:04:11.600
erste, dritte und so weiter hier nach links.

01:04:12.640 --> 01:04:16.940
Ich habe hier drin links genau a plus b Einsen.

01:04:19.040 --> 01:04:22.240
Die Hälfte der Einsen aus der linken und die Hälfte der Einsen aus der

01:04:22.240 --> 01:04:22.840
rechten Folge.

01:04:23.690 --> 01:04:29.120
Und die zusätzlichen Einsen, die landen beide rechts.

01:04:31.660 --> 01:04:34.320
Ja, weil nämlich die zusätzlichen Einsen, wenn das eine ungerade

01:04:34.320 --> 01:04:36.120
Anzahl ist...

01:04:36.120 --> 01:04:38.960
Wenn das eine gerade Anzahl wäre, ich fange hier mit 1 an.

01:04:40.380 --> 01:04:42.600
1, 2 und so weiter, hier habe ich gerade.

01:04:43.120 --> 01:04:46.820
Eine ungerade Zahl heißt, das zweite Element ist ein gerades Element.

01:04:46.820 --> 01:04:50.680
Das heißt, wenn ich eine ungerade Anzahl von Einsen habe, ist diese

01:04:50.680 --> 01:04:54.100
extra 1, die dazukommt, an einer geraden Position.

01:04:56.140 --> 01:04:58.140
Und dieses gilt hier natürlich genauso.

01:04:58.700 --> 01:05:01.280
Das heißt, die zusätzlichen Einsen liegen an einer geraden Position.

01:05:01.500 --> 01:05:06.760
Das heißt, wenn ich eine ungerade Anzahl von Einsen habe, dann landen

01:05:06.760 --> 01:05:09.600
diese beiden zusätzlichen Einsen auf der rechten Seite.

01:05:11.540 --> 01:05:12.220
So.

01:05:13.000 --> 01:05:15.420
Und jetzt mache ich ein Perfect Shuffle.

01:05:17.800 --> 01:05:22.020
Und vergleiche die entsprechend benachbarten Elemente so auf dieses

01:05:22.020 --> 01:05:22.660
Perfect Shuffle.

01:05:24.260 --> 01:05:27.800
Und jetzt habe ich also zunächst mal hier Elemente aus der linken

01:05:27.800 --> 01:05:28.340
Hälfte.

01:05:29.500 --> 01:05:32.100
Ja, also aus den Anfangsstücken, das sind nur Nullen, die verglichen

01:05:32.100 --> 01:05:32.340
werden.

01:05:32.340 --> 01:05:38.360
Und dann kommt das erste Mal ein Element von der linken Seite, das

01:05:38.360 --> 01:05:39.300
eine Eins ist.

01:05:40.080 --> 01:05:42.820
Und ein Element, äh, Quatsch, hier kommt eine Eins.

01:05:43.020 --> 01:05:46.620
Da habe ich es so dargestellt, dass hier von links eine Eins kommt und

01:05:46.620 --> 01:05:47.440
von rechts eine Null.

01:05:49.420 --> 01:05:52.540
Die müssten jetzt vertauscht werden, damit das sortiert ist.

01:05:55.470 --> 01:05:59.050
Und es ist so, dass hier, ja, muss man sich anschauen, wann kann denn

01:05:59.050 --> 01:06:00.310
sowas auftauchen überhaupt?

01:06:00.910 --> 01:06:02.330
Dass ich wirklich vertauschen muss.

01:06:02.450 --> 01:06:05.730
Wenn von rechts eine Eins kommt und von links eine Null, brauche ich

01:06:05.730 --> 01:06:06.550
gar nichts zu vertauschen.

01:06:07.630 --> 01:06:13.290
Und das interessante ist, so eine Situation tritt nur an einer Stelle

01:06:13.290 --> 01:06:13.530
auf.

01:06:14.710 --> 01:06:16.250
Das schauen wir uns jetzt gleich nochmal an.

01:06:18.170 --> 01:06:22.290
Rechts daneben, ich weiß nicht, ich habe hier A plus B Elemente

01:06:22.290 --> 01:06:23.730
gehabt, A plus B Einsen.

01:06:23.730 --> 01:06:26.810
Diese beiden zusätzlichen Einsen sind dort.

01:06:27.210 --> 01:06:31.190
Also, wenn ich eine gleiche Anzahl von, wenn ich also diese

01:06:31.190 --> 01:06:36.190
zusätzlichen Einsen gar nicht habe, und ich vergleiche hier immer das

01:06:36.190 --> 01:06:41.170
Element I plus Eins an dieser Position mit I an der Position, dann

01:06:41.170 --> 01:06:45.050
könnte es passieren, wenn ich gleich viele Einsen habe in beiden

01:06:45.050 --> 01:06:51.590
Folgen, dass das Element hier, das Element I ist das erste

01:06:51.590 --> 01:06:56.110
Einselement, wird hier verglichen mit dem I minus Eins, das wäre dann

01:06:56.110 --> 01:06:56.470
auch eine Null.

01:06:56.590 --> 01:06:57.870
Das ist genau diese Situation.

01:07:01.250 --> 01:07:04.510
Und dann hätte ich die Vertauschung zu machen.

01:07:04.590 --> 01:07:09.170
Wenn aber hier jetzt mehr Einsen sind, auf der rechten Seite, dann

01:07:09.170 --> 01:07:11.310
taucht das ja eventuell gar nicht auf.

01:07:11.570 --> 01:07:12.630
Das schauen wir uns gleich genauer an.

01:07:13.530 --> 01:07:17.830
Also jeder Vergleicher vergleicht LI und RI minus Eins.

01:07:18.050 --> 01:07:22.410
Linke Seite Position I, mit rechter Seite Position I minus Eins.

01:07:22.930 --> 01:07:24.570
Das sind genau diese Perfect Shuffle.

01:07:25.410 --> 01:07:29.010
Oder die Vergleich der benachbarten Elemente bei so einem Perfect

01:07:29.010 --> 01:07:29.290
Shuffle.

01:07:30.470 --> 01:07:34.110
Und in möglichen Fällen sehen jetzt so aus, ich habe also einmal hier

01:07:34.110 --> 01:07:38.210
LI verglichen mit RI minus Eins, das ist ein Vergleich.

01:07:38.550 --> 01:07:40.330
LI mit RI minus Eins.

01:07:40.790 --> 01:07:42.210
LI plus Eins mit RI.

01:07:44.290 --> 01:07:44.530
So.

01:07:45.850 --> 01:07:51.930
Jetzt kann es sein, dass ich hier gleich viele Einsen habe in beiden

01:07:51.930 --> 01:07:52.330
Fällen.

01:07:53.610 --> 01:07:58.690
Dann wird also irgendwo, das ist also das LI die erste Eins.

01:07:59.890 --> 01:08:02.410
Und das RI Eins taucht dort auf.

01:08:02.410 --> 01:08:04.330
Und das RI minus Eins ist hier.

01:08:06.190 --> 01:08:09.470
Beziehungsweise LI und RI minus Eins sind an der Position, die beiden

01:08:09.470 --> 01:08:11.950
werden verglichen und müssen vertauscht werden.

01:08:12.210 --> 01:08:14.190
Das ist die Situation, die ich hier angedeutet habe.

01:08:15.090 --> 01:08:20.930
Wenn ich jetzt eine weitere Eins habe auf der rechten Seite, bei einer

01:08:20.930 --> 01:08:24.790
der beiden Folgen hatte ich eine ungerade Anzahl von Einsen, dann ist

01:08:24.790 --> 01:08:28.710
das RI minus Eins Eins und das LI war Eins.

01:08:30.530 --> 01:08:32.610
Das LI minus Eins war Null.

01:08:33.550 --> 01:08:36.010
Aber das wurde ja mit RI minus Zwei verglichen, auch eine Null.

01:08:36.610 --> 01:08:41.490
Das heißt, hier werden Elemente verglichen, die gleich sind, da muss

01:08:41.490 --> 01:08:42.470
ich gar nichts vertauschen.

01:08:42.530 --> 01:08:48.790
Wenn ich zwei Elemente habe, rechts mehr, dann habe ich hier die

01:08:48.790 --> 01:08:50.790
Situation, dass zwei Elemente verglichen werden.

01:08:51.250 --> 01:08:54.870
Und da ist das rechte Element, die Eins, und links ist eine Null.

01:08:54.870 --> 01:08:59.150
Das heißt, der einzige Fall, der eine Rolle spielt, ist für den Fall,

01:08:59.210 --> 01:09:04.070
dass wir gleich viele, also eine gerade Anzahl von Elementen haben, in

01:09:04.070 --> 01:09:06.950
der linken und in der rechten Folge, die verschmolzen werden müssen.

01:09:08.210 --> 01:09:11.430
Dann tritt der Fall auf, dass wir tatsächlich etwas vertauschen

01:09:11.430 --> 01:09:11.650
müssen.

01:09:12.090 --> 01:09:13.690
Ansonsten ist schon immer alles richtig sortiert.

01:09:14.290 --> 01:09:17.950
Nur für diesen einen Fall müssen wir hier einmal die Sortierung

01:09:17.950 --> 01:09:18.290
machen.

01:09:18.890 --> 01:09:21.550
Und da wir nicht wissen, an welcher Position das der Fall ist, kann ja

01:09:21.550 --> 01:09:25.470
irgendeine Position sein, müssen wir eben an jeder möglichen Position

01:09:25.470 --> 01:09:27.090
einen solchen Vergleich machen.

01:09:27.710 --> 01:09:32.690
Damit wir alle möglichen Null-Eins-Folgen richtig sortieren können.

01:09:33.690 --> 01:09:37.210
Jetzt werden Sie sagen, das ist ja vielleicht richtig für Null-Eins

01:09:37.210 --> 01:09:39.630
-Folgen, aber die sind ja auch viel einfacher.

01:09:40.130 --> 01:09:43.350
Also wenn ich da beliebige Elemente habe, von Eins bis N, Eins bis

01:09:43.350 --> 01:09:47.830
Sechzehn, da kann ich ja an zig verschiedenen Positionen falsche

01:09:47.830 --> 01:09:51.490
Reihenfolgen haben, und wieso reicht das, dass ich gerade die an

01:09:51.490 --> 01:09:53.950
diesen Positionen vergleiche, müsste ich nicht auch nochmal

01:09:53.950 --> 01:09:55.690
anschließend da einen Vergleich machen.

01:09:57.930 --> 01:10:02.010
Das Interessante ist, dass es ausreicht, Null-Eins-Folgen zu

01:10:02.010 --> 01:10:02.310
betreiben.

01:10:05.260 --> 01:10:08.480
Also hier sage ich, für Null-Eins-Folgen ist die Ausgabe sortiert.

01:10:09.120 --> 01:10:13.440
Das ist also für die beliebige Null-Eins-Folge zu Anfang, ist das

01:10:13.440 --> 01:10:14.180
Verfahren korrekt.

01:10:14.900 --> 01:10:19.600
Und jetzt sage ich, nach dem Null-Eins-Prinzip ist jede Folge damit

01:10:19.600 --> 01:10:20.320
korrekt sortiert.

01:10:20.420 --> 01:10:26.160
Das Null-Eins-Prinzip sagt folgendes, wenn irgendein nur auf

01:10:26.160 --> 01:10:29.160
Vergleichen basierender Algorithmus, das ist also die wichtige

01:10:29.160 --> 01:10:33.360
Bedingung, nur auf Vergleichen basierend, ich darf keine weiteren

01:10:33.360 --> 01:10:35.980
Informationen über die Elemente ausnutzen.

01:10:36.540 --> 01:10:41.320
Ich darf nicht ausnutzen, dass das Null und Eins sind, oder Sechs und

01:10:41.320 --> 01:10:41.740
Fünf sind.

01:10:42.860 --> 01:10:48.020
Wenn also ein solcher Algorithmus A alle Folgen aus Nullen und Einsen

01:10:48.020 --> 01:10:54.860
sortiert, oder verschmilzt, dafür geht es genauso, dann sortiert oder

01:10:54.860 --> 01:10:58.040
verschmilzt er auch jede beliebige Folge von Elementen einer

01:10:58.040 --> 01:10:58.740
geordneten Menge.

01:11:01.700 --> 01:11:05.300
Und das heißt, ich muss nur argumentieren für Null-Eins-Folgen, und

01:11:05.300 --> 01:11:07.700
habe damit etwas gezeigt für die beliebige Folge.

01:11:10.040 --> 01:11:12.700
Dahinter steckt einfach die Überlegung, was ich Ihnen gerade sagte.

01:11:13.000 --> 01:11:16.320
Ich weiß ja nicht, an welcher Position diese Ungleichheit, also diese

01:11:16.320 --> 01:11:18.580
falsche Reihenfolge ist.

01:11:19.200 --> 01:11:22.900
Was ich mit Argumentationen über alle Null-Eins-Folgen hinbekomme ist,

01:11:23.400 --> 01:11:28.940
dass ich für jede Position, an der eine falsche Reihenfolge ist, mit

01:11:28.940 --> 01:11:32.100
diesem Verfahren, das nur Vergleichen basiert, diese falsche

01:11:32.100 --> 01:11:33.660
Reihenfolge korrigieren kann.

01:11:36.090 --> 01:11:42.230
Das reicht aus, um zu zeigen, für beliebige Folgen ist das Ganze

01:11:42.230 --> 01:11:43.270
tatsächlich richtig.

01:11:45.250 --> 01:11:50.610
Und Beweis ist natürlich so, dass man das aufwendig beweisen müsste.

01:11:50.730 --> 01:11:54.770
Ich mache das ein bisschen wieder durch anschauliche Sachen.

01:11:55.170 --> 01:11:57.450
Der formale Beweis geht über mehrere Seiten.

01:11:57.930 --> 01:11:59.090
Ich mache das hier auf einer Folie.

01:12:00.170 --> 01:12:02.110
Die Annahme ist, dass das falsch ist.

01:12:02.930 --> 01:12:07.570
Das heißt, ich nehme an, es gibt eine Folge.

01:12:07.710 --> 01:12:14.090
Ich habe also hier eine Folge S, S1 irgendwie bis Sn.

01:12:15.150 --> 01:12:22.570
Die wird durch unseren Algorithmus A transformiert in eine Folge A von

01:12:22.570 --> 01:12:23.030
S.

01:12:26.110 --> 01:12:32.790
Die nenne ich jetzt mal einfach T1 bis Tn.

01:12:33.090 --> 01:12:35.630
Also A von S.

01:12:36.090 --> 01:12:38.150
Die sortierte Folge wäre jetzt T1 bis Tn.

01:12:39.070 --> 01:12:43.690
Und ich behaupte, es gibt eine solche Folge S1 bis Sn, die durch ein

01:12:43.690 --> 01:12:46.330
Verfahren A nicht sortiert wird.

01:12:47.570 --> 01:12:49.710
Was heißt das, sie wird nicht sortiert?

01:12:50.370 --> 01:12:52.710
Das heißt, ich finde...

01:12:53.870 --> 01:12:56.410
Kommen wir gleich drauf, was das heißt.

01:12:56.770 --> 01:13:01.990
Ganz kurz, die Idee ist, wenn es eine Folge gibt, die durch A nicht

01:13:01.990 --> 01:13:07.510
sortiert wird, kann ich eine 0-1-Folge konstruieren, die dann

01:13:07.510 --> 01:13:09.830
ebenfalls nicht von A sortiert werden kann.

01:13:09.830 --> 01:13:17.750
Wenn ich also zeige, dass ein nur vergleichen basierender Algorithmus

01:13:17.750 --> 01:13:20.450
nicht in der Lage ist, alle Folgen zu sortieren aus beliebigen

01:13:20.450 --> 01:13:24.190
Elementen, folgt, dass dann dieser Algorithmus auch nicht in der Lage

01:13:24.190 --> 01:13:30.970
ist, jede Folge aus 0 und 1 zu sortieren, dann heißt das doch, wenn

01:13:30.970 --> 01:13:34.030
ich in der Lage bin, also die Kontraposition, wenn ich in der Lage

01:13:34.030 --> 01:13:37.870
bin, jede Folge aus 0 und 1 zu sortieren, kann ich auch jede andere

01:13:37.870 --> 01:13:38.370
Folge sortieren.

01:13:39.650 --> 01:13:40.850
Das ist einfach Kontraposition.

01:13:41.630 --> 01:13:42.790
So, und wie mache ich das jetzt?

01:13:44.730 --> 01:13:49.170
Wenn die Folge nicht sortiert wird, dann heißt das, ich habe irgendein

01:13:49.170 --> 01:13:56.390
kleinstes Element meiner Folge, S, das in der Ausgabe A von S, also in

01:13:56.390 --> 01:13:59.450
der Folge T1 bis Tn, an einer falschen Position steht.

01:14:00.910 --> 01:14:07.490
Irgendein Si, das ist das kleinste Element, das steht hier irgendwo,

01:14:07.630 --> 01:14:13.970
ein Si, an der falschen Position heißt, das Element davor ist

01:14:13.970 --> 01:14:22.490
irgendein Sj, das größer ist, aber in dieser sortierten Reihenfolge

01:14:22.490 --> 01:14:23.990
vor dem Si kommt.

01:14:25.030 --> 01:14:27.330
Also eine Position, was ist das denn für Quatsch?

01:14:29.750 --> 01:14:33.430
Da habe ich also eine solche Unsortiertheit drin.

01:14:34.830 --> 01:14:41.470
So, die trat auf, an mindestens einer Stelle, ich nehme das kleinste

01:14:41.470 --> 01:14:44.250
Element, bei dem so etwas auftritt, das kleinste Element, das an der

01:14:44.250 --> 01:14:48.010
falschen Stelle steht, das heißt, das Element davor, in der Folge, die

01:14:48.010 --> 01:14:52.210
A produziert hat, muss größer sein, ist also irgendein Sj, das größer

01:14:52.210 --> 01:14:52.470
ist.

01:14:53.250 --> 01:15:00.890
Und das in dieser Folge A von S vor Si auftaucht.

01:15:01.690 --> 01:15:06.010
So, jetzt definiere ich eine Folge von 0 und 1.

01:15:08.750 --> 01:15:13.770
Wenn ich hier mir anschaue, Si und Sj, dann habe ich hier irgendwo

01:15:13.770 --> 01:15:17.790
meine Position I, da habe ich irgendwo meine Position J, kann

01:15:17.790 --> 01:15:19.030
irgendwie so aussehen.

01:15:21.030 --> 01:15:23.910
Oder auch irgendwie anders, ist ja völlig egal, wie das aussieht.

01:15:24.050 --> 01:15:33.590
Ich mache das einfach so, dass ich in meiner Folge S' eine 0,1-Folge,

01:15:35.250 --> 01:15:41.290
jedes Element, das kleiner gleich meinem Si ist, auf 0 setze.

01:15:42.190 --> 01:15:48.170
Und jedes Element, das größer als Si ist, auf 1 setze.

01:15:51.100 --> 01:15:58.000
Damit ist also das Element Sj zu einem Element Sj' geworden, das 1

01:15:58.000 --> 01:16:03.180
ist, und das Element Si zu einem Element Si' das 0 ist.

01:16:04.760 --> 01:16:08.440
Das heißt, ich schreibe hier, ich schreibe da auf jeden Fall für das

01:16:08.440 --> 01:16:10.920
Si eine 0 hin, für das Si eine 1.

01:16:10.920 --> 01:16:16.780
Und ich weiß, in der sortierten Reihenfolge, bei dem A, war hier eine

01:16:16.780 --> 01:16:17.020
Unsortiertheit.

01:16:17.800 --> 01:16:22.600
Ich möchte also zeigen, wenn ich jetzt diese so definierte 0,1-Folge

01:16:22.600 --> 01:16:29.260
S' mit A sortiere, A weiß ja nichts darüber, dass das 0 und 1 sind,

01:16:29.400 --> 01:16:34.580
sondern vergleicht nur die Größen, dann steht anschließend hier die 1

01:16:34.580 --> 01:16:35.160
und da die 0.

01:16:35.760 --> 01:16:37.600
Das heißt, dann ist auch diese Folge nicht sortiert.

01:16:37.600 --> 01:16:39.600
Das heißt, es werden...

01:16:40.960 --> 01:16:45.480
Die Argumentation ist einfach, weil ja alle Operationen unabhängig

01:16:45.480 --> 01:16:47.980
sind von den konkreten Werten, und es nur auf die Größenvergleiche

01:16:47.980 --> 01:16:52.920
ankommt, und ich alle Elemente, die kleiner gleich als Si sind, auf 0

01:16:52.920 --> 01:16:59.320
gesetzt habe, und alle, die größer sind, auf 1, habe ich, ja, nichts

01:16:59.320 --> 01:16:59.720
falsch gemacht.

01:16:59.780 --> 01:17:01.080
Das kann ich argumentieren.

01:17:01.080 --> 01:17:06.860
Wenn ich also jetzt mir anschaue, A auf S', dann werden irgendwelche

01:17:06.860 --> 01:17:10.020
Elemente, irgendwelche Vergleiche gemacht, von irgendwelchen folgenden

01:17:10.020 --> 01:17:11.220
Elementen K und L.

01:17:12.640 --> 01:17:16.920
Wenn das Sk kleiner gleich Si ist, ist es 0.

01:17:19.060 --> 01:17:24.760
Wenn das Sl größer gleich SJ ist, ist es auf jeden Fall 1.

01:17:26.360 --> 01:17:29.520
SJ ist ja auch auf 1 gesetzt worden, auf jeden Fall größer als 1.

01:17:29.520 --> 01:17:35.580
Das heißt, die Wirkung dieses Vergleichs ist auf jeden Fall die

01:17:35.580 --> 01:17:42.400
gleiche wie vorher bei dem Größenvergleich, weil das eine ist kleiner

01:17:42.400 --> 01:17:48.520
als auf jeden Fall in der Folge S, weil das Sk auf jeden Fall kleiner

01:17:48.520 --> 01:17:56.340
als das L, weil das Sk ja kleiner gleich Si ist, und das Sl größer

01:17:56.340 --> 01:17:59.100
gleich SJ, und Si ist kleiner als SJ.

01:18:00.060 --> 01:18:01.180
Also das ist schon mal klar.

01:18:02.040 --> 01:18:03.460
Das heißt, sie haben die gleiche Wirkung.

01:18:04.520 --> 01:18:09.240
Entweder wurden Sk und Sl in der Anordnung verglichen, dann bleiben

01:18:09.240 --> 01:18:12.900
sie stehen, oder sie wurden vertauscht, wenn sie andersrum verglichen

01:18:12.900 --> 01:18:13.180
wurden.

01:18:14.140 --> 01:18:20.140
Alle anderen Vergleiche haben aber keine Relevanz für die

01:18:20.140 --> 01:18:22.920
Ordnungsrelation bezüglich Si und SJ.

01:18:24.780 --> 01:18:27.800
Da werden ja nur Elemente, die kleiner als Si sind, miteinander

01:18:27.800 --> 01:18:28.010
verglichen.

01:18:28.860 --> 01:18:29.940
Das sind jetzt alles Nullen.

01:18:30.620 --> 01:18:33.780
Oder Elemente, die größer als SJ sind, das sind jetzt alles Einzelnen.

01:18:33.900 --> 01:18:35.240
Oder Elemente dazwischen.

01:18:36.560 --> 01:18:38.060
Naja, aber das hat auch keine Relevanz.

01:18:38.700 --> 01:18:43.000
Also die Vergleiche, bei denen Si und SJ tangiert sind, wobei es auf

01:18:43.000 --> 01:18:46.900
deren Reihenfolge ankommt, die sind alle abgedeckt.

01:18:47.920 --> 01:18:56.760
Und das heißt, dass in As', also in der durch A umgeordneten Folge S',

01:18:57.420 --> 01:19:02.520
Si' und SJ' an den gleichen Positionen stehen müssen, wie in A von S.

01:19:03.900 --> 01:19:05.240
Also so wie hier angedeutet.

01:19:05.360 --> 01:19:08.720
Und das heißt, dass ich hier auch eine nicht sortierte Folge habe.

01:19:10.160 --> 01:19:15.160
Damit habe ich eine Folge definiert, S', eine 0-1-Folge, die durch

01:19:15.160 --> 01:19:19.300
dieses Verfahren A ebenfalls nicht sortiert werden kann, weil diese

01:19:19.300 --> 01:19:27.900
Unsortiertheit in der so konstruierten Folge S' bei Anwendung des

01:19:27.900 --> 01:19:30.380
Algorithmus A an der gleichen Position vorkommt.

01:19:32.420 --> 01:19:34.960
Und damit habe ich genau das gezeigt.

01:19:36.080 --> 01:19:41.200
0-1-Prinzip, es reicht zu argumentieren für 0-1-Folgen, um etwas über

01:19:41.200 --> 01:19:43.240
beliebige Folgen sagen zu können.

01:19:43.240 --> 01:19:47.460
Das ist ein tolles Beweisprinzip, weil es nämlich den Aufwand deutlich

01:19:47.460 --> 01:19:47.980
reduziert.

01:19:48.920 --> 01:19:53.780
Ich habe zwei hoch N verschiedene 0-1-Folgen, aber ich habe in

01:19:53.780 --> 01:19:59.400
Fakultät verschiedene Terminationen von Elementen, über die ich sonst

01:19:59.400 --> 01:20:00.160
etwas sagen müsste.

01:20:00.760 --> 01:20:02.300
Der Aufwand ist deutlich höher.

01:20:02.780 --> 01:20:07.560
In Fakultät ist er deutlich größer als die Anzahl dieser 0-1-Folgen.

01:20:08.260 --> 01:20:13.920
Zwei hoch N ist immer noch groß, aber die Argumentation mit 0-1-Folgen

01:20:13.920 --> 01:20:19.060
ist deutlich einfacher, weil ich mich nur über die Grenzen zwischen 0

01:20:19.060 --> 01:20:23.620
und 1 argumentieren muss, als für die anderen Verfahren.

01:20:24.880 --> 01:20:27.620
Und jetzt haben wir noch 5 Minuten, das reicht noch, um Ihnen noch ein

01:20:27.620 --> 01:20:28.520
bisschen mehr zu zeigen.

01:20:29.280 --> 01:20:31.520
Also, das, was ich vorhin schon angedeutet habe.

01:20:33.040 --> 01:20:37.920
Ich habe einen Parallelalgorithmus formuliert als irgendein Programm

01:20:37.920 --> 01:20:42.880
auf Parallelrechnern und da werden jetzt diese Verfahren ausgeführt.

01:20:43.000 --> 01:20:46.220
Logische Ausführung von Operationen auf diesen verschiedenen

01:20:46.220 --> 01:20:46.880
Elementen.

01:20:47.200 --> 01:20:50.000
Das Ganze kann ich aber auch als ein Vergleichernetz darstellen.

01:20:50.540 --> 01:20:54.600
Vergleichernetz bedeutet, ich habe meine Position, in dem Fall also 1

01:20:54.600 --> 01:20:56.140
-16.

01:20:57.660 --> 01:21:01.620
Jetzt schaue ich mir an, welches sind denn die Vergleiche, die durch

01:21:01.620 --> 01:21:04.320
dieses Schema hier ausgeführt werden.

01:21:05.560 --> 01:21:05.820
Naja.

01:21:07.520 --> 01:21:15.340
Für OEM von 2 werden 2 Elemente jeweils verglichen, die ich durch so

01:21:15.340 --> 01:21:19.840
ein sukzessives immer wieder Perfect Unshuffle auseinandergezogen

01:21:19.840 --> 01:21:20.160
habe.

01:21:20.760 --> 01:21:24.900
Und das sind gerade Elemente, die gerade den Abstand in halbe haben.

01:21:28.760 --> 01:21:33.760
1 und in halbe plus 1 werden verglichen, die beiden Positionen.

01:21:33.840 --> 01:21:36.100
Entsprechend 2 und in halbe plus 2 und so weiter.

01:21:37.340 --> 01:21:45.080
Das ist genau dieser eine Vergleich, dieses OEM von 2, das ist unser

01:21:45.080 --> 01:21:48.780
Komplex auf folgende Länge.

01:21:49.700 --> 01:21:53.200
Also, das verschmelzt von 2 folgende Länge 1.

01:21:53.520 --> 01:21:54.280
Das ist gerade ein Vergleich.

01:21:54.280 --> 01:21:56.900
Das ist dieses hier.

01:21:57.280 --> 01:22:01.500
Das ist also unser OEM von 2.

01:22:03.060 --> 01:22:06.100
Der erste Schritt, der erste Vergleich, der ausgeführt wird.

01:22:06.200 --> 01:22:08.040
Das andere ist alles ein logisches Umkopieren.

01:22:09.020 --> 01:22:13.020
Und danach habe ich genau diese weiteren Operationen auszuführen.

01:22:13.620 --> 01:22:14.840
Das sind diese Schritte hier.

01:22:16.080 --> 01:22:18.700
Das ist der erste solche Schritt.

01:22:20.220 --> 01:22:23.200
Es werden 4 Vergleiche ausgeführt in diesem Fall.

01:22:24.780 --> 01:22:29.700
Ich habe nämlich 4 Folgen der Länge 2.

01:22:30.820 --> 01:22:34.960
Also 4 Folgenpaare der Länge 2, die verschmolzen werden müssen.

01:22:35.200 --> 01:22:38.500
4 mal müssen 2 Folgen der Länge 2 verschmolzen werden.

01:22:39.040 --> 01:22:48.600
Wenn ich 2 Folgen der Länge 2 verschmelzen möchte, dann muss ich genau

01:22:48.600 --> 01:22:51.220
diese Situation...

01:22:52.180 --> 01:22:56.200
Ich habe jetzt 1, 2, 3, 4.

01:22:56.720 --> 01:22:58.940
Das muss ich die beiden vergleichen.

01:22:59.880 --> 01:23:02.220
Das ist jetzt am Ende meine sortierte Folge.

01:23:03.380 --> 01:23:04.380
Das ist genau dieser Punkt.

01:23:04.560 --> 01:23:06.460
Und die liegen jetzt hier so in der Mitte.

01:23:06.680 --> 01:23:10.880
Das liegt halt gerade an den Indizes dieser Elemente.

01:23:11.900 --> 01:23:16.800
Die werden gerade jetzt so miteinander verglichen.

01:23:17.240 --> 01:23:20.640
Und anschließend habe ich diesen Schritt.

01:23:22.120 --> 01:23:29.220
Da sind jeweils 2 Folgen der Länge 4, die verschmolzen werden müssen.

01:23:29.560 --> 01:23:34.980
Bei 2 Folgen der Länge 4 habe ich 3 Vergleiche, die ausgeführt werden.

01:23:35.080 --> 01:23:38.140
Ich weiß nicht, was das hier jetzt sein soll.

01:23:41.340 --> 01:23:43.280
Das sind diese Vergleiche.

01:23:43.300 --> 01:23:45.240
Und dann kommt am Ende nochmal ein Schritt.

01:23:46.240 --> 01:23:48.780
Das ist praktisch der letzte, der hier oben angedeutet ist.

01:23:49.820 --> 01:23:52.640
Das sind diese Vergleiche, die nacheinander ausgeführt werden.

01:23:52.720 --> 01:23:57.100
Also iterativ, von unten, mache ich einmal den Vergleich für...

01:23:57.100 --> 01:23:57.580
Ups.

01:24:00.160 --> 01:24:01.660
Das ist ja echt witzig.

01:24:07.620 --> 01:24:10.220
Da sehen Sie, dass man auch manchmal etwas anderes tut.

01:24:12.500 --> 01:24:13.780
Ich muss hier mal entspannen.

01:24:14.940 --> 01:24:17.940
Also, ich habe hier am Ende noch einmal diesen einen Vergleich.

01:24:18.140 --> 01:24:21.810
Und das heißt, ich habe insgesamt diese verschmelzten durchgeführt.

01:24:22.520 --> 01:24:24.140
In genau diesen Lockend-Schritten.

01:24:24.880 --> 01:24:25.740
Und das ist das Vergleichende.

01:24:27.180 --> 01:24:27.700
So.

01:24:28.600 --> 01:24:32.700
Und wir hatten jetzt gesehen, dass das eben ausreicht für unser

01:24:32.700 --> 01:24:33.620
Sortieren.

01:24:34.240 --> 01:24:36.440
Die Korrektheit, also das nervt wirklich.

01:24:36.980 --> 01:24:40.120
Jetzt haben wir also hier ein gleiches Netz.

01:24:40.440 --> 01:24:42.280
Und jetzt nur noch ganz kurz.

01:24:43.380 --> 01:24:48.540
Ich kann noch ein anderes Verfahren angehen, das sogenannte Bitonic

01:24:48.540 --> 01:24:48.900
Sort.

01:24:49.880 --> 01:24:52.380
Da schaue ich mein Verfahren ein bisschen anders an.

01:24:52.480 --> 01:24:53.800
Ich sehe aber, die Zeit ist eigentlich um.

01:24:53.800 --> 01:24:53.800
Okay.

01:24:54.400 --> 01:24:55.840
Nächstes Mal schauen wir uns Bitonic Sort an.

01:24:55.900 --> 01:24:56.580
Sie haben noch eine Frage.

01:25:05.640 --> 01:25:06.000
Nochmal?

01:25:11.450 --> 01:25:16.210
Nächste Woche hatte ich das angekündigt, dass das der Fall ist.

01:25:16.390 --> 01:25:19.950
Warum mache ich nächste Woche am 4., das ist bereits morgens.

01:25:20.670 --> 01:25:21.730
Da können Sie sich mal kurz gucken.

01:25:22.390 --> 01:25:24.150
Das muss ja irgendeinen besonderen Grund haben.

01:25:25.430 --> 01:25:26.430
Das ist am 4.

01:25:27.810 --> 01:25:28.730
Am 4.

01:25:28.730 --> 01:25:28.970
Am 4.

01:25:29.870 --> 01:25:33.830
Da, da, da, da, da, da, ich weiß es gar nicht.

01:25:36.330 --> 01:25:39.030
Das hatte irgendeinen Grund gehabt, dass ich das ursprünglich mal

01:25:39.030 --> 01:25:39.910
gesagt habe.

01:25:40.550 --> 01:25:42.970
Aber ich sehe den Grund im Augenblick gar nicht.

01:25:45.250 --> 01:25:48.110
Also, ich kann das genauso gut wie Sie.

01:25:48.590 --> 01:25:50.730
Der Grund ist...

01:25:51.310 --> 01:25:52.430
Das hat sich erledigt.

01:25:53.610 --> 01:25:54.710
Hat sich erledigt.

01:25:55.030 --> 01:25:56.510
Die Vorlesung ist ganz normal.

01:25:57.890 --> 01:26:01.650
Nehmen Sie die Meldung aus dem Forum raus oder aus der Ankündigung

01:26:01.650 --> 01:26:02.090
raus.

01:26:03.170 --> 01:26:05.830
Die Vorlesung ist also nächste Woche auch ganz normal.

01:26:07.890 --> 01:26:09.950
Um 9.45 Uhr.

01:26:10.870 --> 01:26:11.630
Hier in diesem Raum.

01:26:12.910 --> 01:26:13.050
Ja?

01:26:14.370 --> 01:26:14.930
Okay.

01:26:15.830 --> 01:26:16.090
Gut.

01:26:16.550 --> 01:26:17.630
Und dann machen wir nächstes Mal hiermit weiter.