So, schönen Tag.
Grüße Sie zur Fortsetzung der Vorlesung effizienter Algorithmen.
Wir haben gerade ganz kurz angesprochen, dass Sie jetzt die Bewertung
machen, die Vorlesungsbewertung.
Das ist etwas, was wir ja am KIT, beziehungsweise insbesondere an der
Fakultät seit vielen, vielen, vielen Jahren machen.
Unsere Fakultät war Vorreiter bei Vorlesungsbewertungen.
Das Dumme ist nur, dass bei der Art, wie ich Vorlesungen halte, mit
Aufzeichnungen, die Zahl der anwesenden Studierenden in der Vorlesung
leider geringer ist als die Zahl der tatsächlichen Hörer.
Deswegen finde ich immer diese Bewertungen anhand derjenigen, die in
der Vorlesung sitzen, etwas schwierig, weil das ein kleiner Ausschnitt
ist.
Natürlich sind das diejenigen, die das größte Interesse haben, das
live zu erleben.
Deswegen ist das auch ganz richtig.
Aber ich lege Wert auf eine sinnvolle Bewertung.
Ich habe das sonst oft auch so gemacht, dass wir dann die Vorlesungen
einfach in Übungen bewertet haben, weil dann, wenn wir schnell da
sind, diesmal läuft es halt so, ist auch in Ordnung.
Ansonsten, wenn Sie Rückmeldungen zur Vorlesung haben, können Sie auch
so gerne uns über Forum oder E-Mails Rückmeldungen schicken.
Das nehmen wir immer gerne entgegen.
Lassen Sie uns jetzt kurz wieder zu dem kommen, was wir in der
Vorlesung machen.
Wir sind dabei, uns jetzt mit Such- und Sortierproblemen zu
beschäftigen.
Nachdem wir ja die algebraischen Probleme hinter uns gelassen haben,
hatte ich letztes Mal nochmal etwas gezeigt zur schnellen
Projekttransformation, zu den Werkzeugen, die wir haben für diese
Verfahren, Verbindungsstrukturen und ähnlichem.
Und jetzt kommen wir also wieder zu den Such- und Sortierverfahren,
eines der Standardprobleme bei effizienten Algorithmen.
Und ich hatte Ihnen dazu meine Bemerkungen gemacht, zu den Grundlagen,
Datenstrukturen, die wir haben, wie wir eigentlich bewerten, wie der
Aufwand ist.
Wir hatten dann gesehen, welche Probleme da eigentlich zu behandeln
sind, nämlich Suchprobleme, Sortierprobleme und ähnliches.
Eine ganze Variante von verschiedenen Problemen, die wir uns angeguckt
haben.
Ich habe Ihnen etwas über Lexikon-Operationen erzählt.
Es war klar, dass wir hier die Anzahl der Vergleiche als wesentliches
Maß haben.
Wir haben uns die Standardverfahren nochmal kurz angeguckt.
Die kennen Sie ja alle.
Also hier das Sortieren durch Auswahl mit quadratischem Verhalten.
Im besten Fall, im mittleren Fall und im schlechtesten Fall natürlich.
Und dann habe ich Ihnen gezeigt, dass das Minimum nicht mit weniger
als n-1 Operationen oder Vergleichen gefunden werden kann.
Wenn ich n Elementen in der Liste habe, wir haben uns ein Verfahren
für die parallele Bestimmung des Minimums angeschaut.
Und das war nicht so offensichtlich, dass man das so machen kann, aber
es geht halt mit drei Schritten, drei parallele Schritte.
Und ich kann damit also in konstanter Zeit das Minimum bestimmen,
allerdings mit einem sehr hohen Aufwand, nämlich mit n² Vergleichen.
Für ein Problem, das sequenziell lineare Zeit braucht, also deutlich
viel zu hoher Aufwand, was die Anzahl der Possessoren angeht.
Aber es geht in konstanter Zeit.
Das war die interessante Erkenntnis.
Wir haben dann das Sortieren durch Einfügen angeschaut.
Interessanter Vergleich mit der Sortieren durch Auswahl, dass hier der
beste Fall linear ist, der mittlere Fall immer noch quadratisch.
Und wir hatten dann Bubble Sort angeschaut als letztes in der letzten
Vorlesungsstunde.
Und da hatte ich Ihnen nochmal, dann gehen wir hier auch wieder in die
Animation, bzw.
in die Darstellung, in die Präsentation.
Und da hatte ich Ihnen nochmal gezeigt, dass was Sie ja alles kennen
aus Grundlagen der Informatik 1, dass wir hier halt ein Verfahren
haben, bei dem wir in der Standardversion immer quadratisches
Verhalten haben, einer leicht optimierten.
Also das ist klar, dass wir hier immer n mal n-1 halbe Vergleiche
haben, weil wir in der Standardversion, wie es hier steht, halt immer
durchlaufen die restliche Liste.
Das heißt, Anfang n-1 Vergleiche, dann n-2 und so weiter.
Und nur wenn man aufpasst und guckt, ob überhaupt noch verglichen
werden muss, dann hat man im besten Fall lineare Zeit.
In jedem Fall also linear.
Wenn nicht mehr vertauscht wird, kann es sein, dass man nach n-1
Vergleichen schon fertig ist.
Wenn man von links nach rechts das macht, hat man auch eine gewisse
Verbesserung, der sogenannte Shaker Sort.
Aber es ist keine prinzipielle Verbesserung, weil wir im schlechtesten
Fall immer noch quadratische Zeit haben und im Mittel ebenfalls.
Und das Interessante ist, wenn wir uns jetzt eine parallele Variante
anschauen, dann ist das auf einmal ein interessantes Verfahren.
Schauen wir uns das genauer an.
Parallele Variante von Bubble Sort heißt nicht Paralleles Bubble Sort,
PBS, sondern es heißt Odd-Even Transposition Sort.
Es ist ein bisschen anders als Bubble Sort, aber nur ein bisschen.
Das, was wir hier machen, ist, dass wir abwechselnd ungerade und
gerade Paare von Daten vergleichen.
Was heißt das?
Was ist ein ungerades und ein gerades Paar?
Also wenn wir hier unsere... meinetwegen, wir haben Elemente eine
Position 1, 2, 3, 4, 5, 6.
Was sind die ungeraden Paare?
Das sind Paare, bei denen die erste Position des Paares ungerade ist.
Also die ungeraden Vergleiche wären diese hier, bei einer Folge mit
sechs Elementen.
Danach, wenn j ungerade ist, j gleich 1 bis n, machen wir n halbe
Vergleiche.
Und zwar vergleichen wir jeweils, wenn es ungerade ist, das erste
Element ist ungerade, das zweite ist gerade, deswegen 2i minus 1 und
2i.
Wenn es gerade ist, dann werden die an den geraden Positionen
verglichen mit ihren Nachbarn.
Hier am Ende natürlich eigentlich auch, also dann nehmen wir mal an,
dass wir hier unendlich stehen haben, dann kann man das auch so, dann
wären das hier auch drei Vergleiche.
Da das hier immer das Ergebnis 6 hat, weil hier wird nichts
vertauscht, ist es klar, dass wir auf den Vergleich auch verzichten
könnten.
Nur für die Korrektheit dieses Algorithmus muss ich annehmen, dass ich
auch ein Element Sn plus 1 habe.
Dieses CompX steht für Compare Exchange, das heißt ich vergleiche und
vertausche.
Das heißt diese Operation, die da steht, macht folgendes, wenn ich
hier a und b habe, dann kommt hier raus das Minimum von a und b und da
kommt raus das Maximum von a und b.
Das heißt ich schreibe immer das Maximum nach rechts, da wo die
Fallspitze ist.
Die Fallspitze deutet immer an, wohin das Maximum geschrieben wird.
Das ist ein Comparison Exchange, Vergleich und Vertauschen.
Und das Ganze steht hier, wird jetzt in mal gemacht, das heißt ich
müsste jetzt hier noch entsprechend weitere Vergleiche hinschreiben.
Und das habe ich hier 1, 2, 3, 4, 5, 6.
Und die Behauptung ist, nach 6 solchen Schritten bin ich mit dem
Algorithmus fertig.
Danach ist die Folge sortiert.
Also dieses 1, 2, 3 bis 6 ist ja hier nur die Position angegeben, da
stehen irgendwelche Elemente.
Die Behauptung ist, danach ist es sortiert.
Also es ist nicht genau Bubble Sort.
Bei Bubble Sort bin ich ja sequenziell durchgelaufen.
Hier sage ich, ich muss ja nicht sequenziell durchlaufen, ich kann ja
die Vergleiche hier auch parallel machen, die unabhängig sind.
Das ist im Prinzip die ganze Idee dahinter.
Ich mache so viele Fahrweisevergleiche wie möglich, gleichzeitig kann
ich halt nur 1 mit 2 und 3 mit 4 vergleichen, aber nicht 2 mit 3.
Weil ich dann ja Konflikt habe beim Zugriff auf die Elemente.
Stellen Sie sich einfach vor, Sie haben hier jeweils Prozessoren, die
das machen.
Nehmen Sie an, Sie haben hier im Prinzip n Prozessoren, die so
durchnummeriert sind.
Die haben jeweils ein Element in ihrem Speicher und kommunizieren mit
ihren Nachbarn und vergleichen und vertauschen ihre Elemente.
Sie können auch annehmen, dass es Prozessoren sind, die irgendwelche
großen Dateien haben.
Und Sie wollen jetzt einfach dafür sorgen, dass insgesamt am Ende Sie
eine aufsteigende Folge von Daten haben.
Und die jeweiligen Dateien in den Prozessoren werden miteinander
verglichen, werden zusammengebaut und dann in der Mitte sortiert und
wieder auseinandergezogen.
Das heißt, ob das jetzt Elemente sind, einzelne Elemente oder
irgendwelche großen Dateien, spielt ja eigentlich keine Rolle.
Und auch die Vergleichs- und Vertauschungsoperationen müssen nicht
unbedingt ein Vergleich von zwei Zahlen sein, kann auch ein Vergleich
von irgendwelchen größeren Objekten sein.
Aber das Verfahren ist hier so im Prinzip dargestellt.
Von der Syntax her ist es die übliche Pseudoprogrammiersprache Syntax,
die eigentlich genau zeigt, was hier gemacht wird.
Die Analyse ist klar.
Wir haben genau N Schritte da drin.
Parallelitätsgrad ist N halbe.
Wir machen N halbe Vergleiche, also N halbe, ob Prozessoren arbeiten
gleichzeitig jeweils.
Nur die Hälfte kann Vergleich ausführen.
Und deswegen ist der Zeitgewinn bei diesem Verfahren in O von Log N,
weil das beste sekretäre Verfahren hat Aufwand N Log N.
Das habe ich Ihnen noch nicht gezeigt, aber das wissen Sie aus
Grundlagen Informatik 1.
Und wir haben hier N Prozessoren, Parallelitätsgrad, Größenordnung N.
Das heißt, der Zeitgewinn ist logarithmisch, Log N.
Nicht Zeitgewinn N, sondern Zeitgewinn logarithmisch.
Ist nicht allzu doll, Effizienz entsprechend, Log N durch N.
Effizienz ist ziemlich gering.
Das Interessante ist, wenn ich ein lineares Feld von Prozessoren habe,
wie ich das so angedeutet habe, etwas schlecht skizziert, dann ist es
natürlich so, wenn ich jetzt sage, ich muss sortieren, dann kann es
sein, dass das kleinste oder das größte Element zu Anfang hier auch
der linkesten Position ist.
Und das größte Element, das muss aber am Ende ganz recht sein in dem
rechtesten Prozessor, wenn ich aufsteigend sortieren will.
Und wenn ich mir anschaue, wie viel Zeit das braucht, um jetzt in
einer solchen Folge von Prozessoren, die linear miteinander verbunden
sind, ein solches Element darüber zu schieben, dann sind das N-1
Operationen.
Ich kann das ja nur in jedem Schritt nur eine Position weiterschieben.
Das heißt, mit weniger als linearer Zeit kann ich in einem linearen
Feld von Prozessoren überhaupt nicht sortieren.
Und auf einmal habe ich ein Verfahren, das tatsächlich auf einem
linearen Feld in der asymptotisch optimalen Zeit sortiert.
Nämlich lineare Zeit.
Auf dieser Rechnerstruktur geht es nicht besser als in linearer Zeit
und dieses Verfahren macht das.
Insofern ist das durchaus interessant und ich werde Ihnen das jetzt
nochmal genauer zeigen, denn da, was ich Ihnen noch gar nicht
begründet habe, ist, warum ich überhaupt nach N-Schritten hier fertig
bin.
Also, unser Bubble Sort brauchte ja N-Quadrat-Schritte.
Da musste ich ja hier N-Quadrat-Vergleiche machen.
Natürlich mache ich hier N-Halbe-Vergleiche gleichzeitig.
Und wenn ich also mit Bubble Sort vergleiche, habe ich natürlich einen
optimalen Zeitgewinn.
Von N-Quadrat auf N mit N Prozessoren.
Perfekt.
Aber das ist nicht der Zeitgewinn, den ich angeben darf, weil der
Zeitgewinn immer im Vergleich zum besten sequenziellen Verfahren
gemacht werden ist.
Also, wenn ich mit Bubble Sort vergleiche, habe ich hier einen tollen
Zeitgewinn.
Aber ob das wirklich so richtig ist, dass ich damit tatsächlich nach N
-Schritten fertig bin, das ist noch gar nicht sicher.
Denn das Muster der Vergleiche bei Bubble Sort sah anders aus.
Da habe ich ja nacheinander die Elemente miteinander verglichen.
Deswegen muss ich jetzt erstmal beweisen, dass das richtig ist.
Und hier habe ich jetzt nochmal für eine Folge mit 8 Elementen einfach
aufgemalt.
Dieses, was man auch ein Vergleichernetz nennt.
Vergleichernetz ist im Prinzip so eine...
Da malt man sich die einzelnen Elemente, also hier S1, S2 und so
weiter, alle auf.
Diese Liste.
Und malt dann einen senkrechten Strich.
Oder horizontal, ist völlig egal.
Das sind im Prinzip die Positionen in meinem Feld von Elementen, die
ich sortieren möchte.
Und jetzt male ich dort einfach die Vergleiche rein.
Das heißt, dass durch diesen Vergleich hier vorne, dieser erste
Vergleich, der vergleicht und vertauscht die beiden Elemente.
Und das heißt, durch diese Vergleiche werden Elemente hier hin und her
geschoben, entsprechend diesen Größenvergleich.
Und das, was ich mir jetzt anschaue, oder was ich beweisen möchte,
ist, dass ich tatsächlich mit N-odd-even-Schritten fertig bin, also
fertig sortiert habe.
Und ich möchte zeigen, dass das egal ist, ob ich mit einem odd-Schritt
anfange oder mit einem even-Schritt.
Also even-Schritt würde bedeuten, ich fange nicht mit diesem Vergleich
an, wo ich S1 mit S2 vergleiche, sondern der erste Schritt ist einer,
wo ich die mit den geraden Positionen, also S2, S3, S4, S5 vergleiche.
Erst davon soll das unabhängig sein.
Das ist die Behauptung.
Die muss ich jetzt beweisen.
Das mache ich wieder durch Infektion.
Der erste Schritt ist trivial.
Wenn die Folgeart nur ein Element hat, dann bin ich mit einem Schritt
natürlich fertig.
Ja, klar.
Ich hatte aber gesagt, die Folgeart, die Länge, ich habe doch ein N
-plus -erstes-Element.
Ich habe hier so zwei Elemente und das heißt, ich bin auf jeden Fall
fertig.
N gleich zwei, ein odd- und ein even-Schritt reichen immer aus.
Wenn ich so zwei Elemente habe, nur diese beiden Elemente, und ich
fange mit einem odd-Schritt an, dann bin ich fertig.
Wenn ich aber zwei Elemente habe und ich fange mit einem even-Schritt
an, dann ist der even-Schritt dieser hier und der odd-Schritt ist der.
Dann brauche ich zwei Schritte.
Ja, das heißt, deswegen, bei N gleich zwei, bin ich mit einem odd- und
einem even-Schritt, oder einem even- und odd-Schritt, immer fertig.
So, und jetzt kommt das Interessante, das heißt die Induktionsbasis,
jetzt kommt die Induktionsannahme, dass es für N bewiesen ist, und wir
gucken uns eine Folge der Länge N plus 1 an.
Das Vergleichernetz ist hier angegeben, wir nehmen also an, dass das
hier die Situation darstellt für N plus 1, in diesem Fall ist also N
plus 1 gleich 8, und jetzt schauen wir uns das Feld ein bisschen
genauer an.
Und das, was wir genauer machen, ist, dass wir den Weg des maximalen
Datums anschauen.
Das maximale Datum steht irgendwo.
Im schlechtesten Fall wird dieses maximale Datum, das größte Element
in dieser Folge, ganz links stehen.
Dann ist hier ganz links bei S1 das maximale Element.
Und jetzt überlege ich mir, schafft dieses Feld von Vergleichen, also
diese Folge von odd-even-Vergleichen, schafft dieses Element das, oder
diese Vergleichsfolge, das ist tatsächlich, dieses Element, das
maximale Element, ganz an die rechte Position zu bewegen.
Natürlich schafft es das.
In diesem Fall, wenn wir mit dem Odd-Schritt anfangen, hier, dann wird
natürlich sofort im ersten Schritt das maximale Element einen Punkt
nach rechts wandern.
Mit dem nächsten Vergleich wandert es wieder einen Schritt nach
rechts, mit dem nächsten Vergleich wieder nach rechts, wieder nach
rechts, wieder nach rechts, wieder nach rechts, wieder nach rechts.
Wir sind also mit nach n-1 Vergleichen schon fertig.
Beziehungsweise, wir haben eine Folge von n-1, also mit n vergleichen
sind wir fertig.
Wir brauchen gar nicht alle Schritte von dem odd-even.
Wenn wir aber mit einem even-Schritt anfangen, würden wir im ersten
Schritt nicht hier schon das Ding rüberschieben.
Dann wäre da ein even-Vergleich, ein gerader Vergleich, dann würde S2
und S3 verglichen werden.
Und das S1 würde erst im ersten odd-Schritt anfangen zu wandern.
Das heißt, wir bräuchten dann tatsächlich alle Schritte, damit das
Ganze rüberkommt.
Aber es kommt auf jeden Fall insgesamt nach rechts.
Also ich beschränke mich im Folgenden darauf, nur das odd-even
wirklich anzugucken.
Mit even-odd kann man sich gleich überlegen, dass es nach rechts
wandert.
Also, ich habe maximal n-plus-1, ich habe sogar für even-odd, für odd
-even, habe ich hier auf jeden Fall sogar nach n-Schritten das
erreicht, nach n-plus-1-Schritten sowieso.
Dann ist das Element an der Position pn-plus-1 und ich weiß also,
dieses Element geht an die richtige Position.
Nur was ist mit den anderen Elementen?
Das Interessante ist, was passiert denn mit den anderen Elementen?
Das andere Element, das S2, das wandert durch diesen Vergleich eine
Position nach links, an die Position S1.
Das Element S3, das läuft natürlich auch an dem maximalen Element
vorbei, schiebt sich um 1 nach links.
Das heißt, alle Elemente, die hier in diesem Bereich liegen, die
rechts von dem maximalen Element jeweils liegen, die werden nur um 1
nach links verschoben.
Und jetzt mache ich aber folgendes, dass ich sage, ich eliminiere den
Weg des maximalen Datums.
Also ich eliminiere einfach diesen Weg aus meinem Vergleichernetz.
Das heißt, ich lösche das einfach raus.
So, was bleibt denn jetzt übrig?
Ich hatte gerade gesagt, diese Elemente, die hier an der Position S2,
S3, S4 und so weiter bis S8 liegen, die werden natürlich alle an dem
maximalen Element vorbei nach links geschoben.
Und danach werden sie natürlich mit den anderen Elementen
weiterverglichen.
Das heißt, das, was übrig bleibt, sind Vergleiche, bei denen nicht das
maximale Element eine Rolle spielt.
Die anderen Vergleiche bleiben alle gleich.
Und wenn ich mir anschaue, was das eigentlich für ein Vergleichernetz
ist, dann sieht das doch genauso aus wie unser Odd-Even-Transposition
-Sort, aber in diesem Fall ist es ein Even-Odd.
Im Prinzip haben wir hier ja eine Diagonale rausgenommen.
Deswegen brauchen wir eben diese Behauptung, dass sowohl Odd-Even als
auch Even-Odd ausreichen.
Jetzt haben wir hier ein Netz.
Das ist jetzt das Netz, was wir im Prinzip jetzt betrachten müssen.
Das ist genau die Vergleiche, die ausgeführt werden.
Und dadurch, dass das nach links verschoben wurde, haben wir im
Prinzip genauso ein Netz, wie wir das für Endelemente haben.
Und wir wissen nach Ignitionsannahme, dass wir mit einem solchen
Vergleichernetz N-Elemente mit N-Schritten sortieren können.
Und das heißt, diese Folge, dieses ganze Sortiernetz reichte aus, um
insgesamt zu sortieren.
Das heißt, wir sind fertig, die ganze Folge wird in N-plus-1-Schritten
sortiert.
Wir brauchen eventuell N-plus-1-Schritte, um das Element, das maximale
Element, an die Position N-plus-1 zu bringen.
Und der Rest reicht aus, um insgesamt das sortiert zu haben.
Also insofern ist das ein ganz einfacher Beweis.
Dies ist übrigens eine Beweistechnik, die...
Das ist kein formaler Beweis, natürlich.
Formal müsste ich argumentieren über Positionen von Elementen, müsste
das formal modellieren.
Aber ein Beweis hat die Aufgabe, Verständnis zu erzeugen.
Zu überzeugen, dass das richtig ist, was ich sage.
Und ich denke, das mache ich auch durch diese Darstellung, dass ich
also hier das Element, diesen Weg, rausgenommen habe.
Früher habe ich das genannten Beweis durch Folie, weil ich da Folien
verschoben habe.
Inzwischen ist es ein Beweis durch Animation.
Ja, dass ich also hier zeige, dass das Feld, das ich dann bekomme,
tatsächlich genauso ein, in dem Fall ein Even-Odd-Feld ist.
Und damit ist die Korrektheit bewiesen.
Also es ist gar nicht so einfach, Beweise über die Korrektheit von
parallelen Algorithmen zu machen.
Hier sieht man aber einfach, dass das Ding so in Ordnung ist.
Und wir werden noch einige weitere Beweistechniken kennenlernen.
So, das ist also jetzt dieses Bubble Sort, bzw.
Optimal Transposition Sort, ein auf linearen Feldern optimales
Verfahren.
Übrigens gibt es noch einen weiteren schönen Aspekt hier drin.
Ich hatte gesagt, wir betrachten ein lineares Feld von Prozessoren,
die also jeweils miteinander hier kommunizieren.
Das, was passiert, ist im Prinzip jetzt hier in der Zeit ausgerollt.
Ich gehe nochmal wieder zurück.
Das, was hier passiert, ist ja das Ausrollen über die Zeit.
Ja, ich gucke mir an, welche Vergleiche nacheinander gemacht werden.
Jetzt kann ich aber auch sagen, ich baue daraus einfach ein Hardware
-Algorithmus.
Ich baue einfach ein Algorithmus, der macht folgendes, dass er jeden
Vergleich in einen Baustein verwandelt, der zwei Elemente als Eingabe
bekommt und jeweils das Minimum links ausgibt, das Maximum rechts, wo
die Fallspitze ist.
Und jetzt, sage ich also, jeder dieser eingeraten Vergleiche ist ein
Hardware -Baustein.
Die kann ich ganz dicht zusammenpacken, weil wir direkt miteinander
kommunizieren.
Rein lokale Verbindungen.
Also der Ausgang von einem ist der Eingang des Nächsten, die kann ich
ganz eng zusammenpacken.
Wenig Aufwand für Leitung.
Sie erinnern sich, Leitungsaufwand war etwas, was wichtig ist für
Hardware -Algorithmen.
Und wenn ich mir jetzt anschaue, wie ich es einem solchen Hardware
-Algorithmus bewerten müsste, da hätte ich natürlich eine Fläche von
N².
Also natürlich viel Fläche.
N²-Elemente, die dort vergleichen, bzw.
N²½-Vergleichsoperationen.
Und dann kann ich hier eine Folge eingeben.
Das wäre also etwas zu einem gewissen Zeitpunkt.
Das dauert dann Endtakte, bis ich fertig bin.
Aber ich kann sofort nach dem ersten Vergleich die nächste Folge
eingeben.
Und die nächste Folge eingeben.
Und die nächste Folge.
Das heißt, wenn ich das Ganze als Hardware-Baustein realisiere, habe
ich zwar einen Flächenaufwand von N², aber ich habe einen Abstand
zwischen aufeinanderfolgenden Berechnungen, der gerade bedingt ist
durch den Aufwand für einen Vergleich.
Das heißt, dann habe ich auf einmal ein Verfahren, das eine Periode
von 1 zeigt.
Also konstante Periode.
Und ich habe einen Durchsatz von N.
Das heißt, ich habe hier ein Verfahren, wenn ich jetzt sage, ich mache
jetzt viele Sortiervorgänge nacheinander, wie ist der mittlere
Zeitaufwand, den ich pro Sortierfolge eigentlich spendieren muss?
Wenn ich viele Operationen mache, dann habe ich hier konstanten
Aufwand pro Folge.
Ich habe zwar einen zeitlichen Versatz, aber ich bekomme mit
konstantem Abstand die sortierten Folgen herausgeliefert.
Das heißt, ich muss zwar diese gewisse Latenz hier berücksichtigen,
die ich brauche, um nach der ersten Eingabe Ergebnisse zu liefern,
aber dann kommen die mit einer hohen Frequenz raus.
Das heißt, ich habe hier ein sehr interessantes Verfahren, bei dem ich
kleine Bausteine habe, die ich jeweils im HP realisieren muss.
Ein Vergleichsoperator ist sehr leicht zu realisieren, wenige
Transistoren.
Und ich habe lokale Kommunikation, sehr wenig Leitungsaufwand, kann
ich sehr effizient packen und kann damit einen Sortierer bauen, der
also einen hohen Durchsatz hat.
Ein sehr schönes Verfahren, ist auch von darauf gebaut.
So, das ist also jetzt dieses OITS.
Und jetzt gehen wir zurück auf das, was Sie kennen.
Sortierverfahren mit Divide & Conquer.
Sortieren durch Teile.
Anwendung des Prinzips Divide & Conquer.
Algorithmus QuickSort hatte ich schon mal ganz kurz erwähnt.
Kennen Sie auch noch von Grundlageninformatik 1.
Was ist die Idee bei QuickSort?
Ich mache mir das Leben einfacher.
Ich sage, das Sortieren ist mir zu schwierig.
Ich gucke mir erstmal ein Teilproblem an.
Ich nehme mir ein beliebiges Element raus.
Und ein beliebiges Element kann ja auch das erste sein.
Wenn ich eine beliebige Eingabe habe, das erste Element ist ein
beliebiges Element der sortierenden Folge.
Und das ist jetzt ein sogenanntes Pivot-Element.
So nennt man das bei diesem Verfahren.
Und jetzt gruppiere ich meine Folge um.
Und zwar so, dass ich das Element C an die richtige Position bringe.
Die richtige Position heißt, alle Elemente, die links davon sind, sind
kleiner gleich.
Und alle, die rechts davon sind, sind größer als dieses Element C.
Das ist nur ein Umordnungsproblem.
Das heißt, ich habe das Sortierproblem umgewandelt in ein
Umordnungsproblem.
Das heißt, ich habe jetzt zwei Folgen.
S' und S''.
Das sind hier diese Folgen S' und S'.
Und jetzt muss ich ja nur das gleiche nochmal machen.
Auf den Folgen S' und S'.
Das kann ich ja rekursiv weiter so verfolgen.
Das heißt, ich habe das Sortierproblem umgewandelt in ein Problem.
Folgen umzuordnen, sodass ein Element an die richtige Position kommt.
Wenn ich das immer weitermache, bin ich natürlich am Ende fertig.
Ich habe alle Elemente an der richtigen Position.
Und die Frage ist, wie groß ist der Aufwand?
Auch das kennen Sie.
Natürlich kann ich diese...
Das ist erstmal ein wichtiger Punkt, die Aufteilung hier.
In zwei Folgen S' und S'.
Wie macht man die denn in linearer Zeit?
Würde ich das gerne machen.
In linearer Zeit ist das so einfach.
Ich muss doch dieses Element hier mit allen anderen vergleichen, dass
es an die richtige Position bringt.
Das sieht aber zunächst mal gar nicht so aus, dass das in linearer
Zeit geht.
Mit allen Vergleichen, die an die richtige Position bringen, heißt,
ich muss da irgendwas umordnen, das kann aufwendig sein.
Die interessante Idee ist, dass ich das so mache, dass ich zwei Zeiger
verwende.
Und hier jeweils diese Zeiger nach rechts und nach links laufen lasse.
Und die Elemente, die da jeweils...
Ich lasse das hier rüberlaufen, aber hier irgendwann Elemente an
solchen Positionen.
Und ich vergleiche immer die beiden Elemente.
Und wenn die in der falschen Reihenfolge sind, dann vertausche ich
sie.
Was heißt denn falsche Reihenfolge?
Falsche Reihenfolge heißt, das linke Element ist größer als das rechte
Element.
Ich fange jetzt nicht bei dem c an, sondern an der zweiten Position.
Da fange ich an.
Warum ist das richtig, das so zu machen?
Da ich ja am Ende links von dem c Elemente haben möchte, die kleiner
gleich c sind, und rechts davon Elemente, die größer als c sind, weiß
ich, dass ich am Ende, oder dass ich immer, alle Elemente von der
Strich kleiner gleich habe, als alle Elemente von der Zwei Strich.
Das heißt, wenn ich hier ein Element einer Position L habe, oder ein
Element einer Position R, und das Element L wäre größer als das
Element R, dann muss ich die natürlich vertauschen, weil sie ansonsten
nicht richtig angeordnet wären.
Und das mache ich so lange, bis ich im Prinzip hier L und R in der
gleichen Position habe, und dann bin ich fertig.
Dann habe ich ja dafür gesorgt, dass die immer gerade so vertauscht
werden, und das heißt, ich habe auf die Art und Weise eine
Partitionierung erreicht.
Das geht also gerade mit diesen Hin- und Herschieben der Pointer, und
auf diese Art und Weise erreiche ich also in linearer Zeit, mit genau
N plus 1 vergleichen, kann man sich genau überlegen, will ich jetzt
nicht machen, ist alles in Grundlagen Informatik 1 passiert, in
linearer Zeit leicht machbar.
Das ist also dieses Partitionieren.
Die wesentliche Idee, also wenn Sie dann gefragt werden, nach was ist
Quicksort, die wesentliche Idee ist eben diese Aufteilung, dass man
eben das Sortierproblem reduziert auf ein Partitionierungsproblem.
Und das dann rekursiv weiter.
Und dass das in linearer Zeit geht, ist eigentlich relativ
naheliegend, dass das geht.
Auch wenn ich erst sagte, das wäre zunächst mal ein naiven Ansatz,
vielleicht nicht der Fall, aber man sieht ja sehr schnell, dass man
das in linearer Zeit machen kann.
So, wie ist dann der Aufwand?
Also das ist jetzt schwierig.
Die Zeitkomplexität.
Ich habe den Aufwand von Quicksort für folgende Länge N.
Das ist der Aufwand, um zu partitionieren, das ist Größenordnung N,
das ist unser Aufwand fürs Aufteilen.
Und dann muss ich nach dem Aufteilen das gleiche Verfahren anwenden
auf die Folge, die links steht, auf das S-Strich.
Und auf die Folge, die rechts steht, auf das S2-Strich.
Und da drin steht jeweils das S-Strich mit Betragsstrichen dran, also
die Größe der Folge S-Strich und die Größe der Folge S2-Strich.
Muss die Frage, wie sind denn diese Größen?
Die können also sehr unterschiedlich sein.
Wenn ich Pech habe, ist diese Folge S-Strich hier vorne leer.
Das heißt, das Element C stand an der richtigen Position.
Dann habe ich nichts erreicht, beziehungsweise nur sehr wenig.
Ich weiß, dass das Element C an der richtigen Position war.
Das heißt aber, die nächste Folge, die ich betrachten muss, das S2
-Strich, hat eine Länge N-1.
Da brauche ich auch Lineare zeigen.
Und sofort sieht man, wenn die Folge schon vorsortiert war, dann
braucht dieses Verfahren quadratische Zeilen.
Ganz schlecht.
Ich wollte doch besser werden als diese einfachen Verfahren, Auswahl,
Einfügen und Bubble-Sort.
Schlecht ist der Fall O von N².
Jetzt schaue ich mir an, ob ich nicht im besten Fall besser werden
kann.
Wir mussten bei Sortieren durch Einfügen hatten wir im besten Fall der
Lineare.
Wie sieht das denn hier aus?
Im besten Fall sieht man hier folgendes.
Habe ich eine Aufteilung meiner Folgen gerade in zwei gleich große
Folgen.
Die also beide etwa die Größe N½ haben.
Und ich muss jetzt zweimal folgende Größe N½ weiter partitionieren.
Jetzt haben wir hier eine Rekursionsformel, das kennen wir doch.
Das ist Zeituhr von Nlogn.
Zweimal T von N½ plus Linear macht Nlogn.
Wissen wir aus unserer Rekurrenzleitung zu überlegen.
Also bester Fall Nlogn.
Schlechter als bester Fall bei Sortieren durch Einfügen.
Aber natürlich gar nicht so schlecht.
Und das interessante ist, dass wir im Mittel in diesem Fall auch ein
Verhalten von Nlogn haben.
Das zeige ich gleich.
Das war bei den anderen Verfahren bisher nicht der Fall.
Da waren wir im Mittel immer bei N² geblieben.
Wir konnten zwar im besten Fall bis auf Linearverzeichung, das geht
hier nicht.
Aber der Name Quicksort wäre natürlich völlig unberechtigt.
Wenn wir hier immer noch bei N² bleiben würden.
Also schauen wir uns das mittlere Verhalten an.
Und um das zu analysieren, müssen wir einfach sagen, was schauen wir
eigentlich an.
Wir messen die Anzahl der Vergleiche.
Also das V von J sei die mittlere Zahl von Vergleichen bei Aufruf von
Quicksort auf einer Teilliste der Länge J.
Irgendeine Länge.
Und wir nehmen an, dass alle Listenlängen gleich wahrscheinlich sind.
Also wenn wir hier unsere Folgen anschauen.
Das erste Element ist ein beliebiges Element.
Das heißt, die Endposition nach dem Aufteilen...
Ja, das kann jede Position sein, irgendwo kann das Element landen.
Jede Position ist gleich wahrscheinlich.
Das ist die Annahme, die wir haben.
Das ist die endgültige Position des Pivot-Elements.
Und dann weiß ich doch, Anzahl der Vergleiche für eine Folge der Länge
1 und eine Folge der Länge 0 ist natürlich 0.
Da muss ich gar nichts tun.
Wenn ich eine Folge der Länge N habe, dann wende ich also jetzt mein
Divide -and-Conquer, bzw.
mein Quicksort-Verfahren an.
Und jetzt muss ich zunächst mal partitionieren.
Partitionieren, hatte ich gesagt, sind N plus 1 Vergleiche.
Und dann muss ich die linke und rechte Folge noch weiter bearbeiten.
Die linke Folge...
Nehmen wir mal an, wir sind hier an die Position, wenn das hier die
Position I ist.
Dann hat die linke Folge I-1 Elemente, die Folge S' und die Folge S2',
hat N-I Elemente.
Das heißt, das gilt für jede mögliche Position, deswegen Summe I
gleich 1 bis N.
Und, da jede Position gleich wahrscheinlich ist, habe ich hier also
dann noch da Mittel 1 durch N zu rechnen.
Und wenn ich mir das genauer anschaue, dann habe ich hier N plus 1,
das taucht ja jedes Mal auf, plus...
Und jetzt taucht hier immer auf V I-1 und V N-I.
Das heißt, V 1 taucht zweimal auf als 2-1 und als N-N-1.
Und so weiter.
Es tauchen alle genau zweimal auf, alle Folgenlängen.
Das heißt, das hier ist eine Beschreibung der Anzahl der Vergleiche im
Mittel für eine Folgelänge N.
Jetzt ist das noch relativ aufwendig.
Machen wir jetzt ein paar Tricks.
Ich schaue mir an, dass hier N plus 1 mal V N plus 1 minus N mal V von
N.
Kleiner Trick.
Das ist entsprechend dieser eingerahmten Formel.
Gerade N plus 1 mal N plus 2.
Also V N plus 1 ist ja N plus 2 plus 2 durch N plus 1 und so weiter.
2 durch N plus 1 mal N plus 1 gibt also hier zweimal diese Summe.
Jetzt bis N, nicht bis N minus 1.
Und davon ziehe ich ab.
N mal V von N, also N mal N plus 1 minus zweimal diese Summe.
Wenn ich mir das genauer anschaue, dann bleibt da nicht viel übrig.
Das ist gerade zweimal N plus 1.
Das ist diese zweimal N plus 1 plus...
Und da ich hier diese ganzen V von Is dort nochmal abziehe, bleibt
hier nur übrig zweimal V von N.
Alle anderen sind raus.
Das heißt, diese Differenz hier ist gleich diesem Ausdruck.
Und wenn ich das jetzt umgruppiere, steht hier V von N plus 1 ist
gleich 2 plus N plus 2 durch N plus 1 mal V von N.
Ganz einfache Umgruppierung hier.
Diese Gleichung einfach nach V von N plus 1 aufgelöst.
Und ich habe diesen Ausdruck.
Und jetzt ist die Behauptung, dass dieser Wert V von N damit aus O von
N log N ist.
Wie beweist man das?
Zunächst mal zeigt man durch Induktion Folgendes, dass dieses V von N
gleich diesem Ausdruck ist.
Zweimal N plus 1 mal Summe 1 durch I.
I gleich 3 bis N plus 1.
Harmonische Reihe.
Das ist der erste Schritt, dass ich das zeige.
Kann man leicht durch Induktion zeigen, das ist also ganz einfach.
Das ist Induktion, will ich jetzt gar nicht machen, können Sie einfach
durchprobieren.
Das ist also wirklich eine ganz einfache Induktion.
Müssen Sie einmal nur das hier einsetzen und das verwenden,
Induktionsannahme machen und dann haben Sie es schon gezeichnet.
Ganz einfach, dass diese Summe hier oder dass dieser Ausdruck richtig
ist.
Und jetzt machen wir noch diese Abschätzung, dass diese Summe in N log
N liegt.
Ne Quatsch, in log N.
Summe 1 durch I, I gleich 3 bis N plus 1.
Dann hätten wir nämlich N plus 1 mal log N und das ist also dann
großen Ordnung U von N log N.
Und die Überlegung ist folgendes.
Ich summiere diese 1 durch I auf.
Was ist 1 durch I?
Das ist eine Funktion.
1 durch X, unsere Funktion.
Also 1 durch X, schaue ich mir einfach die Funktion an.
Bisschen idealisiert hier.
Das hier ist der Abstand 1.
1 durch I ist hier oben drüber zu sehen.
Also von der Größenordnung stimmt das nicht so ganz.
Unterschiedlich ist Qualierung.
Aber das Wesentliche ist, dass ich hier den Wert 1 durch I abtrage.
Dieser Wert hier ist 1 durch I.
Das heißt, dieses hier, diese Höhe ist 1 durch I.
Und das heißt, wenn ich mir die Fläche anschaue von I minus 1 bis I
unter der Kurve 1 durch X, dann ist diese Fläche hier, also 1 durch I,
1 durch I mal 1 ist gerade diese Fläche.
Und diese Fläche ist doch offensichtlich kleiner gleich der Fläche,
wenn ich hier von I minus 1 bis I integriere, die Funktion 1 durch X.
Und sie ist größer gleich, weil ich ja dann hier noch was abziehe, von
I bis I plus 1, das wäre das, was hier drunter liegt.
Das heißt, ich habe diese Abschätzung, Integral von I bis I plus 1, 1
durch X dx ist kleiner gleich 1 durch I mal 1, kleiner gleich Integral
von I minus 1 bis I, 1 durch X.
Das ist also die ganz einfache Abschätzung hier.
Und wenn ich jetzt das Ganze aufsummiere, dann betrachte ich die Summe
1 durch I, I gleich 2 bis N, ist dann gerade kleiner gleich der Summe
der Integrale.
Und die Summe der Integrale ist dann aber gerade das Integral von 1
bis N, 1 durch X dx.
Und dieses Integral, wissen wir, welchen Wert das hat, das ist gerade
1 plus ln N, Logarithmus dualis, Quatsch, Logarithmus naturalis von N.
Integral von 1 durch X, das kennen wir.
Da steht I plus 1, weil ich da diesen Bereich mir anschaue, deswegen I
bis I plus 1.
Bei dem anderen steht von I minus 1 bis I, weil ich da diesen Bereich
mir anschaue.
Dann habe ich insgesamt hier, weil ich das nach oben abschätze, das
steht jetzt bis I, das heißt ich habe hier Integral von 1 bis N, da
die Summe war von 2 bis N, also habe ich hier eine Abschätzung
logarithmisch.
Da muss ich jetzt nicht ln N hinschreiben, sondern kann auch log N
hinschreiben, das sind nur konstante Faktoren.
Damit habe ich also die Abschätzung, dass diese Summe in log N liegt,
also genauso wächst, nur nicht stärker wächst als log N.
Und damit ist der Ausdruck insgesamt hier in N log N.
Damit habe ich gezeigt, mittleres Verhalten von Twigsort ist in N log
N.
Und damit habe ich einen deutlichen Fortschritt gegenüber den anderen
Verfahren, die ja im mittleren Fall immer quadratische Zeiten haben.
Hier habe ich also jetzt Gleichheit von besten Fall und mittleren
Fall, natürlich nicht bei der konstanten, aber ich bin da im gleichen
Bereich.
Schlechtester Fall immer noch quadratisch.
Ist schlecht.
Übrigens, das Problem hierbei ist, bei dieser Aufteilung, der
schlechteste Fall ist deswegen schlecht, weil ich hier nur die Länge
der Folge nur konstant verkleinere.
Wenn ich es schaffen würde, dass dieser Teil hier immer irgendein N
durch K ist, mindestens irgendein N durch K, also irgendein konstanter
Anteil, vielleicht ein Zehntel oder Siebzehntel oder irgendetwas.
Wenn ich zeigen könnte, ich habe jeweils einen konstanten Anteil
weniger, das erreichen könnte, dann wäre der schlechteste Fall auch N
log N.
Aber ich habe eben keinen konstanten Anteil, die Folgelänge ist hier
nicht N durch irgendwas, sondern die ist halt im schlechtesten Fall
Länge 1, N log N ist schlecht.
Aber wenn ich da einen konstanten Bruchteil jeweils immer abschneiden
könnte, wäre ich schon viel besser.
Dann wäre ich auch im schlechtesten Fall in einem Verhalten N log N.
Damit sehen Sie jetzt, was man tut, um das Verhalten im Mittel zu
analysieren.
Bei diesem Beispiel habe ich das einmal gemacht, ich werde das an
anderen Beispielen noch ein einziges Mal machen.
Ansonsten werden wir das gar nicht weiter betrachten.
Wir müssen natürlich immer Annahmen machen über Verteilung unserer
Elemente.
Also die Schwachstelle ist, dass wir von der Wahl des Pivot-Elements
abhängig sind.
Verbesserungen sind natürlich so, dass Sie sagen, ich nehme einfach,
wenn ich meine Folge hier habe, warum soll ich das erste Element
nehmen?
Der schlechteste Fall lag ja daran, wenn die Folge schon vorsortiert
ist, dann nehme ich doch einfach das mittlere Element von diesen drei.
Und dann habe ich ja für diesen Fall, dass die Folge schon vorsortiert
ist, immer genau die bestmögliche Aufteilung in der Mitte.
Perfekt.
Für diesen schlechtesten Fall hätte ich dann ein Verhalten von N log N
erreicht.
Aber es kann natürlich sein, dass diese drei Elemente, gerade die
ersten drei Elemente meiner Folge sind, die sortiert werden sollen.
Das heißt, ich kann sofort einen schlechten Fall konstruieren, bei dem
genau diese Aufteilung auch dazu führt, dass ich eben nicht einen
festen Bruchteil abschneiden kann, sondern nur konstant viele.
Und damit bin ich wieder nicht weiter gekommen.
Also im schlechtesten Fall immer noch quadratisch.
Ich bin natürlich im besten Fall, bleibe ich immer bei N log N, im
mittleren Fall auch.
Aber ich mache ein bisschen mehr Aufwand, weil ich noch den Median von
drei Elementen bestimmen muss.
Also insofern ist das schon etwas besser.
Ich kann natürlich sagen, ich nehme ein zufälliges Element der Liste.
Wenn ich ein zufälliges Element der Liste nehme, der Erwartungswert
vor die Position ist natürlich eine Position, irgendwas in der Mitte.
Also ein randomisiertes Quicksort, da ist der Erwartungswert der
Laufzeit in O von N log N.
Aber ich muss dann, wenn ich das jeweils zufällig auswähle, kann ich
immer noch Pech haben, dass ich eine quadratische Laufzeit kriege,
aber ich habe dann einen Erwartungswert von N log N, das heißt im
Schnitt werde ich in N log N sortieren können.
Ich muss aber immer zufällig die Position auswählen.
Extra Aufwand.
Jetzt machen wir noch ein, das ist also ein randomisiertes Quicksort,
aber wir könnten natürlich noch eine weitere Verbesserung machen.
Wir könnten einfach sagen, naja, ich bestimme einfach erstmal das
mittlere Element meiner Folge.
Ich sorge dafür, dass ich auf jeden Fall immer am Ende hier lande, in
der Mitte.
Das geht aber nur, wenn ich weiß, welches das mittlere Element ist, so
müsste ich das noch bestimmen.
Den Median bestimmen.
Und wenn Sie das naiv machen, haben Sie leider den gleichen Aufwand
wie beim Sortieren.
Das ist schlecht.
Da kommen wir später noch zu und werden sehen, dass das in linearer
Zeit geht, aber dann hätten Sie in linearer Zeit Median bestimmt, in
linearer Zeit Partitioniert, und sind dann insgesamt, hätten Sie dann
auch im schlechtesten Fall, Quadratische Zeit NlogN, aber der Aufwand
für den Median ist dann relativ hoch.
Also, die erste Idee ist, randomisiertes Quicksort zu nehmen.
Das ist schon nicht schlecht.
Sie bekommen dann schon mal ein ganz gutes Ergebnis.
So, jetzt kann ich aber sagen, ich mach das einfach anders.
Ich wähle mir ein Verfahren, bei dem ich garantieren kann, dass ich
ein richtiges Divide-and-Conquer mache.
Dieses war ja so ein Versuchen, Divide-and-Conquer zu machen, aber es
ist nicht wirklich eins.
Ich möchte ja gerne ein Problem, das groß ist, aufteilen in zwei
Teilprobleme, die kleiner sind.
Und dieses Quicksort ist halt so, dass ich das versuche, und wenn ich
Pech habe, habe ich halt kein richtiges Divide-and-Conquer gemacht,
sondern ich habe nur ein Element rausgebracht.
Wenn ich sage, es muss aber streng aufgeteilt werden, dann mache ich
das so einfach.
Ich teile einfach meine Folge auf, in zwei Folgen.
Das ist also meine Folge S.
Zwei Folgen S' und S''.
Und jetzt sortiere ich die, rekursiv nach diesem Verfahren.
Und anschließend muss ich ja nur die beiden sortierten Listen
verschmelzen.
Dieses Aufteilen in zwei Folgen ist ja ganz einfach.
Da muss ich ja nur sagen, okay, das ist die Aufteilung.
Dann wieder eine Aufteilung.
Das sind ja nur logische Operationen, keine realen Operationen.
Das heißt, das, was ich mache, hier ist ein Beispiel, eine Folge der
Länge 8.
Dieses Aufteilen in Teillisten, das ist ja trivial.
Das heißt nur, ich muss mit diesem Schritt hier anfangen.
Das ist mein erster Schritt, dass ich nebeneinander liegende Elemente
vergleichen muss und sortieren muss.
Also ich mache hier im Prinzip solche...
Ups...
...diese Complex-Change-Operation.
So.
Die muss ich nur vergleichen, also zusammenfügen zu einer sortierten
Liste.
Das habe ich hier gemacht.
Das ist der Aufwand.
Also praktisch der erste Schritt beim Merge Sort besteht darin, dass
ich im Prinzip...
...kann ich also iterativ machen und nicht rekursiv.
Iterativ werden einfach solche Elemente verglichen.
Und danach muss ich das Gleiche im Prinzip mit diesen Benachbarten
machen.
Die beiden, die beiden.
Complex-Change auf Folgen der Länge 2.
Merge ist das.
Das heißt, jetzt habe ich diese beiden Folgen.
Und anschließend mache ich Complex-Change auf diesen beiden Elementen.
Das sind jetzt Folgen der Länge 4.
Also wieder ein Merge-Mischen von zwei sortierten Folgen.
Und ich bin fertig.
Das Ganze geht dann also in 1.
Das ist der erste Schritt, der zweite Schritt, der dritte Schritt.
Bei Folgen der Länge 8, natürlich in logarithmisch vielen Schritten,
muss ich Vergleiche machen bzw.
Merge-Operationen machen.
Logarithmisch viele Schritte.
Und ich muss natürlich hier...
Im ersten Schritt habe ich vier solche Vergleichs-Operationen.
Hier habe ich zwei, da habe ich eine.
Und der Aufwand für jede Vergleichs-Operation wächst jeweils.
Das Mischen, das wissen wir, wie das geht.
Das Verschmelzen.
Also sequenziell geht das in linearer Zeit.
Da habe ich hier viermal konstante Zeit.
Zweimal Aufwand 2.
Einmal Aufwand 4.
Das heißt, der Aufwand insgesamt war immer 4.
In jeder Stufe habe ich Aufwand n.
Und ich bin schon fertig.
Beziehungsweise, wenn ich das anders argumentiere, ich habe log n
Merge -Stufen.
Und der Aufwand besteht also gerade daran, dass ich zweimal Merge-Sort
mache auf folgende Länge in halbe.
Plus den Aufwand für das Verschmelzen.
Und das wissen wir, nach unserer Kursionsgleichung, ist das ein n log
n zu machen.
Also ist das genau n log n.
Das heißt, hier habe ich im schlechtesten Fall n log n.
Ich habe das erreicht, was ich wollte.
n Quadrat ist schlecht.
In schlechtester Fall n log n ist möglich.
Wir wissen, Quicksort hatte n log n im Mittel.
Aber in schlechtester Fall quadratisch.
Jetzt kann ich also auch noch in schlechtestem Fall runterdrücken auf
n log n.
Parallel.
Wie mache ich das?
Das ist doch die Vorlage für ein paralleles Verfahren.
Jede Ebene in diesem Baum, in diesem Verschmelzungsbaum, mache ich
parallel.
Das heißt, ich mache ein parallel Merge-Sort auf Folgen der Länge in
halbe.
Parallel.
Und anschließend mache ich ein paralleles Merge.
Von n heißt, zwei Folgen der Länge in halbe werden verschmolzen.
Und jetzt muss ich mir anschauen, wie ist denn der Aufwand, um
parallel zu verschmelzen.
Sequenziell brauchen wir dafür n Operationen, n-1 Operationen.
Parallel ist die Frage, wie das geht.
Wenn das Ganze, dieses P-Merge von n, logarithmisch geht, dann hätten
wir insgesamt log²n.
Ja, dann wäre dieser Term hier logarithmisch.
Nach unserer Rekursionsformel wissen wir, dann ist das, was rauskommt,
log² von n.
Wenn das Ganze, nehmen wir mal an, wir könnten in konstanter Zeit
verschmelzen.
Zwei sortierte Folgen in konstanter Zeit verschmelzen, klingt
unwahrscheinlich.
Dann hätten wir aber insgesamt einen Aufwand von log n Schichten.
Das wäre also Aufwand log n.
Mit im Prinzip n Prozessoren.
Das wäre optimal.
Tatsächlich geht das.
Aber es ist ein sehr kompliziertes Verfahren, das so hinzukriegen,
dass Sie auf Zeit log n kommen, mit linear vielen Prozessoren.
Oder linear mit der Parallelitätsgrad von n.
Ist aber ein bisschen aufwendig, ist nicht so direkt dieses parallele
Merge Sort, das ist ein bisschen was anderes.
Das zeige ich Ihnen auch nicht.
Ich werde Ihnen jetzt Verfahren zeigen, bei denen wir tatsächlich das
parallele Merge in logarithmischer Zeit hinbekommen.
Also mit logarithmisch vielen Schritten.
Das sind so die klassischen Verfahren für paralleles Sortieren.
Sie machen dieses parallele Merge Sort und kommen dann auf eine Zahl,
Logarithmus zum Quadrat.
Wie kann das gehen?
Also dieses Merge Sort kennen Sie.
Dass es n log n geht, wissen Sie.
Sie wissen auch, dass...
Also nochmal kurz zurück.
Merge Sort ist zwar gut, aber Sie wissen, was ist nach Ihrer
Auffassung das beste sequenzielle Sortierverfahren in der Praxis?
Was würden Sie nehmen?
Eines von denen, die ich Ihnen gezeigt habe, dabei.
Oder würden Sie ein anderes nehmen?
Hat noch einer eine Idee?
Ja.
Aber es ist so, dass das beste ist Deep Sort.
Aber nicht in der Variante, wie Sie das kennengelernt haben, sondern
ein sogenanntes Bottom-up Deep Sort.
Bottom-up Deep Sort ist also eine gewisse Variation von dem
klassischen Deep Sort und ist tatsächlich besser als Quick Sort auch
im Mittel.
Im schlechtesten Fall sowieso.
Aber auch im Mittel besser als Quick Sort.
Deswegen ist Bottom-up Deep Sort das Verfahren der Wahl, wenn Sie das
sequenziell machen müssen.
Um mal zu zeigen, dass das tatsächlich der Fall ist.
Und das ist also sequenziell das beste Verfahren.
Aber jetzt schauen wir uns die Parallelen-Variante an.
Paralleles Sortieren.
Und das erste, was ich Ihnen zeige, ist wieder etwas Odd-Even.
In diesem Fall ein Odd-Even Merge Sort.
Also das Odd-Even haben wir hier schon mehrfach gezeigt.
Wir hatten das auch bei der schnellen Fourier-Transformation.
Da war auch ein Odd-Even gemacht.
Nämlich die Elemente von Ungeraden und Geradenpositionen getrennt
behandelt.
Genau das macht man hier jetzt auch.
Das ist jetzt unser Odd-Even Merge Sort.
Auf Folgen der Länge N.
Ich mache das Ganze.
Machen die beiden Konker-Verfahren.
Also zweimal nebeneinander.
Das sind die beiden rekursiven Aufrufe von Odd-Even Merge Sort für
Folgen der Länge N.
Daraus kommen jetzt zwei Folgen, die sind jeweils aufsteigend
sortiert.
Zunächst mal hatten wir hier eine völlig ungeordnete Liste.
S1 in diesem Fall bis S16.
Und jetzt haben wir also zwei Teilfolgen, die sind aufsteigend
sortiert.
Und jetzt kommt unser Odd-Even Merge.
Paralleles Mischen.
Und wie machen wir das?
Gleiche Idee wie bei schneller Fourier-Transformation.
Wir machen eine Aufteilung nach den geraden und ungeraden Positionen.
Also alle Elemente an den ungeraden Positionen kommen hier rein.
Das Odd-Even Merge, das hier links steht.
Und hier kommen die an die geraden Positionen.
Was ist hier der Vorteil?
Also...
Ich habe zunächst mal zwei Folgen, die sind bereits aufsteigend
sortiert.
Und jetzt mache ich daraus zwei Folgen der ungeraden, der geraden
Elemente.
Naja, was habe ich denn hier?
Da steht ein OEM N halbe.
Wenn ich die Hälfte der Elemente hier rausnehme aus dieser linken
Liste, das sind natürlich gerade hier eine halbe sortierte Folge.
Und die an den ungeraden Positionen hier bei der rechten Liste, das
ist auch eine sortierte Folge.
Und genauso an den geraden Positionen.
Zwei bereits aufsteigend sortierte Folgen, der jeweils halben Größe.
Und jetzt mache ich das einfach rekursiv.
So lange, bis es nicht mehr weiter rekursiv geht.
Das heißt, ich ziehe im Prinzip hier alle raus.
Und dann habe ich irgendwo zwei Elemente, die übrig bleiben.
Diese zwei Elemente, die übrig bleiben, die muss ich einmal mit einem
Vergleich und Vertauschen in die richtige Reihenfolge bringen.
Und dann läuft das Ganze weiter.
Dann kommt das Zusammenbasteln.
Also das erste ist nur so ein Anschaffel, mehrfach gemacht.
Und dann basteln.
Und dann schiebe ich zusammen.
Und einmal weiß ich, hier kommt jetzt eine sortierte Folge raus.
Das Odd-Even-Merge verschmilzt jetzt zwei Folgen der Länge in Viertel
auf eine Folge der Länge in Halbe, die sortiert ist.
Das ist das gleiche Problem, was ich hier schon hatte.
Zwei Folgen der Länge in Halbe, die verschmolzen werden müssen.
Was ist denn der Vorteil?
Das Interessante ist, wenn ich zwei solche Folgen habe, die auf diese
Art und Weise miteinander oder umgruppiert wurden und in eine
sortierte Reihenfolge gebracht wurden, dann reicht dieser eine Schritt
hier unten aus, bei dem ich Elemente an bestimmten Positionen
miteinander vergleiche.
Und diese Position bekomme ich gerade dadurch, dass ich meine beiden
sortierten Teilfolgen perfekt mische.
Und die dann nebeneinander stehenden Elemente vergleiche.
Das heißt, ich habe erstmal immer wieder auseinandergezogen, einmal
einen Sortierschritt gemacht und dann schiebe ich die immer sukzessive
zusammen.
Beziehungsweise, ich mache jeweils einen Schritt mit parallelen
Vergleichen.
Das linkeste und das rechteste Element, die sind auf jeden Fall schon
richtig an der Position.
Was ist denn das linkeste Element?
Das ist das kleinste Element von links.
Ja, das kleinste Element von links ist ja hier zusammengekommen mit
dem kleinsten Element von rechts.
Das heißt, auf jeden Fall, das kleinste Element der gesamten Folge ist
auf jeden Fall das kleinste Element der linken Folge, die da
rauskommt.
Und genauso symmetrisch wie das größte, die brauche ich gar nicht zu
vergleichen.
Und dann habe ich hier, behaupte ich einfach, durch Vergleiche der
Elemente an diesen ganzen Positionen dort, so wie das hier aufgeteilt
ist, liefert mir gerade eine sortierte Reihenfolge.
Behauptung ist, anschließend ist das Ganze insgesamt sortiert.
Ein Vergleichschritt.
Ja, innerhalb der Vergleiche mache ich parallel.
Und das muss man sich überlegen.
Den Beweis, dass das richtig ist, machen wir gerade.
Nehmen wir das mal als gegeben an, dass das so geht.
Dann haben wir also jetzt welchen Zeitaufwand.
Wir haben für, erstmal, Odd-Even-Merge auf Folgen der Länge 2, ist ein
Comparison -Exchange, das ist ein Schritt.
Und dann haben wir den Aufwand für Folgen der Länge N, also zwei
Verschmelzen von zwei Folgen der Länge in halbe.
Das ist der Aufwand, um zwei Folgen der Länge in viertel zu
verschmelzen.
Und ein weiterer Schritt.
Na gut, dieser Aufwand ist sofort abzuschätzen.
Das ist das logarithmische Aufwand.
Und dann weise ich insgesamt das Odd-Even-Merge-Sort von N, weil jetzt
gerade Odd-Even-Merge-Sort hier oben für Folgen der Länge in halbe,
plus der Aufwand für das Odd-Even-Merge.
Und der Aufwand ist log N, also ist insgesamt, das war die Formel, die
wir auf der vorigen Folie hatten, ist das gerade quadratisch in log N.
Was ich Ihnen noch nicht gezeigt habe, ist, dass das hier tatsächlich
richtig ist.
Das ist ja keineswegs offensichtlich.
Warum soll das, also durch den Perfect-Shuffle, die
nebeneinandergestellten Elemente, warum soll das geradezu einer
sortierten Liste folgen?
Nur dieser eine Schritt, diese ausgewählten Operationen, ich mache
also einmal, wenn ich kleine Folgen habe, mache ich diesen
Anfangsschritt und dann, können wir uns das mal anführen, ganz wenige
Elemente.
Ich habe eins, zwei, drei, vier.
Die sind bereits, die wurden also bereits verglichen, die wurden auch
verglichen, die richtigen Reihenfolge gebracht.
Und ich weiß, das sind die beiden kleinsten Elemente meiner Folge,
meinen beiden Folgen, und das sind die beiden größten Elemente.
Das heißt, anschließend muss ich ja nur noch diese beiden Elemente
vergleichen.
Und diese beiden Elemente, das ist genau ein solcher Vergleich.
Das linke und das rechte Element, die sind schon richtig, in der Mitte
steht noch ein Vergleich.
Das ist das zweite Element der Folge links, verglichen mit dem ersten
Element der Folge rechts.
Das zweite Element der Folge links, verglichen mit dem ersten Element
der Folge rechts.
Das ist der Vergleich.
Und entsprechend zieht sich das jetzt so durch.
Wie kann man das beweisen?
Also hier, das ist klar, Zeitgewinn ist dann gerade in n durch log n,
das ist schon mal nicht schlecht.
n durch log n, deutlich besser als log n wie vorher.
Und die Effizienz ist mit 1 durch log n noch immer nicht optimal.
Wir haben also nicht konstante Effizienz, nur log n ausgelastet.
Das ist halt immer noch ein Problem, aber immerhin.
So, wir sind halt nur auf log²n gekommen und nicht auf log n.
Und jetzt müssen wir uns mit der Korrektheit beschäftigen.
Jetzt mache ich einfach eine Vereinfachung.
Wir haben zunächst mal angenommen, immer bei den Sortierproblemen,
dass alle Elemente verschieden sind.
Jetzt mache ich das Gegenteil.
Nicht, dass alle gleich sind, brauche ich nicht zu sortieren.
Aber ich sage, ich habe nur zwei verschiedene Elemente.
0 und 1.
Und wenn ich die sortiere, habe ich also irgendeine Folge.
Also irgendeine beliebige Folge mit irgendwelchen Elementen.
Und anschließend habe ich eine Folge, ab irgendeiner Position stehen
nur noch Einsen und links davon stehen Nullen.
Also hier stehen die Nullen, da stehen die Einsen.
Das ist ja viel einfacher.
Ich habe ja nur Elemente 0 und 1.
Ich muss sie nur so umordnen, dass dann hier die Nullen alle links
sind und die Einsen alle rechts.
Das ist schon mal ein viel einfacheres Problem.
Und für dieses Problem, 0-1-Folgen zu sortieren, schauen wir uns jetzt
unser odd-even-merge an.
Also, das ist unser odd-even-merge.
Jetzt haben wir hier die linke und die rechte Folge.
Was passiert hier?
Hier zunächst mal, das sagte ich ja, sind unsere bereits sortierten,
das ist das, was rauskommt, aus den Schritten davor.
Ich habe hier eine aufsteigend sortierte Folge, da auch eine
aufsteigend sortierte Folge.
Gleiches Bild wie vorher.
Aufsteigend sortiert heißt hier, ab einer gewissen Position stehen nur
noch Einsen und da auch ab einer gewissen Position.
Und jetzt zähle ich einfach die Anzahl der Einsen auf der linken Seite
und auf der rechten Seite.
Nun ist die Anzahl der Einsen links oder rechts entweder gerade oder
ungerade.
Das ist wichtig, weil wir ja dieses odd-even aufteilen.
Gerade oder ungerade.
Gerade oder ungerade heißt, das ist irgendein 2a oder 2b, eventuell
noch plus 1.
Eine gerade Zahl wäre ein 2a oder eine 2b, ungerade wäre ein 2a plus 1
oder 2b plus 1.
Wenn ich jetzt dieses Perfect-on-Shuffle mache, dann nehme ich die
Hälfte von diesen 2a, eventuell plus 1 Elementen raus und die Hälfte
von diesen 2b, eventuell plus 1.
So, das heißt, ich fange mit dem Element an und nehme dann jeweils das
erste, dritte und so weiter hier nach links.
Ich habe hier drin links genau a plus b Einsen.
Die Hälfte der Einsen aus der linken und die Hälfte der Einsen aus der
rechten Folge.
Und die zusätzlichen Einsen, die landen beide rechts.
Ja, weil nämlich die zusätzlichen Einsen, wenn das eine ungerade
Anzahl ist...
Wenn das eine gerade Anzahl wäre, ich fange hier mit 1 an.
1, 2 und so weiter, hier habe ich gerade.
Eine ungerade Zahl heißt, das zweite Element ist ein gerades Element.
Das heißt, wenn ich eine ungerade Anzahl von Einsen habe, ist diese
extra 1, die dazukommt, an einer geraden Position.
Und dieses gilt hier natürlich genauso.
Das heißt, die zusätzlichen Einsen liegen an einer geraden Position.
Das heißt, wenn ich eine ungerade Anzahl von Einsen habe, dann landen
diese beiden zusätzlichen Einsen auf der rechten Seite.
So.
Und jetzt mache ich ein Perfect Shuffle.
Und vergleiche die entsprechend benachbarten Elemente so auf dieses
Perfect Shuffle.
Und jetzt habe ich also zunächst mal hier Elemente aus der linken
Hälfte.
Ja, also aus den Anfangsstücken, das sind nur Nullen, die verglichen
werden.
Und dann kommt das erste Mal ein Element von der linken Seite, das
eine Eins ist.
Und ein Element, äh, Quatsch, hier kommt eine Eins.
Da habe ich es so dargestellt, dass hier von links eine Eins kommt und
von rechts eine Null.
Die müssten jetzt vertauscht werden, damit das sortiert ist.
Und es ist so, dass hier, ja, muss man sich anschauen, wann kann denn
sowas auftauchen überhaupt?
Dass ich wirklich vertauschen muss.
Wenn von rechts eine Eins kommt und von links eine Null, brauche ich
gar nichts zu vertauschen.
Und das interessante ist, so eine Situation tritt nur an einer Stelle
auf.
Das schauen wir uns jetzt gleich nochmal an.
Rechts daneben, ich weiß nicht, ich habe hier A plus B Elemente
gehabt, A plus B Einsen.
Diese beiden zusätzlichen Einsen sind dort.
Also, wenn ich eine gleiche Anzahl von, wenn ich also diese
zusätzlichen Einsen gar nicht habe, und ich vergleiche hier immer das
Element I plus Eins an dieser Position mit I an der Position, dann
könnte es passieren, wenn ich gleich viele Einsen habe in beiden
Folgen, dass das Element hier, das Element I ist das erste
Einselement, wird hier verglichen mit dem I minus Eins, das wäre dann
auch eine Null.
Das ist genau diese Situation.
Und dann hätte ich die Vertauschung zu machen.
Wenn aber hier jetzt mehr Einsen sind, auf der rechten Seite, dann
taucht das ja eventuell gar nicht auf.
Das schauen wir uns gleich genauer an.
Also jeder Vergleicher vergleicht LI und RI minus Eins.
Linke Seite Position I, mit rechter Seite Position I minus Eins.
Das sind genau diese Perfect Shuffle.
Oder die Vergleich der benachbarten Elemente bei so einem Perfect
Shuffle.
Und in möglichen Fällen sehen jetzt so aus, ich habe also einmal hier
LI verglichen mit RI minus Eins, das ist ein Vergleich.
LI mit RI minus Eins.
LI plus Eins mit RI.
So.
Jetzt kann es sein, dass ich hier gleich viele Einsen habe in beiden
Fällen.
Dann wird also irgendwo, das ist also das LI die erste Eins.
Und das RI Eins taucht dort auf.
Und das RI minus Eins ist hier.
Beziehungsweise LI und RI minus Eins sind an der Position, die beiden
werden verglichen und müssen vertauscht werden.
Das ist die Situation, die ich hier angedeutet habe.
Wenn ich jetzt eine weitere Eins habe auf der rechten Seite, bei einer
der beiden Folgen hatte ich eine ungerade Anzahl von Einsen, dann ist
das RI minus Eins Eins und das LI war Eins.
Das LI minus Eins war Null.
Aber das wurde ja mit RI minus Zwei verglichen, auch eine Null.
Das heißt, hier werden Elemente verglichen, die gleich sind, da muss
ich gar nichts vertauschen.
Wenn ich zwei Elemente habe, rechts mehr, dann habe ich hier die
Situation, dass zwei Elemente verglichen werden.
Und da ist das rechte Element, die Eins, und links ist eine Null.
Das heißt, der einzige Fall, der eine Rolle spielt, ist für den Fall,
dass wir gleich viele, also eine gerade Anzahl von Elementen haben, in
der linken und in der rechten Folge, die verschmolzen werden müssen.
Dann tritt der Fall auf, dass wir tatsächlich etwas vertauschen
müssen.
Ansonsten ist schon immer alles richtig sortiert.
Nur für diesen einen Fall müssen wir hier einmal die Sortierung
machen.
Und da wir nicht wissen, an welcher Position das der Fall ist, kann ja
irgendeine Position sein, müssen wir eben an jeder möglichen Position
einen solchen Vergleich machen.
Damit wir alle möglichen Null-Eins-Folgen richtig sortieren können.
Jetzt werden Sie sagen, das ist ja vielleicht richtig für Null-Eins
-Folgen, aber die sind ja auch viel einfacher.
Also wenn ich da beliebige Elemente habe, von Eins bis N, Eins bis
Sechzehn, da kann ich ja an zig verschiedenen Positionen falsche
Reihenfolgen haben, und wieso reicht das, dass ich gerade die an
diesen Positionen vergleiche, müsste ich nicht auch nochmal
anschließend da einen Vergleich machen.
Das Interessante ist, dass es ausreicht, Null-Eins-Folgen zu
betreiben.
Also hier sage ich, für Null-Eins-Folgen ist die Ausgabe sortiert.
Das ist also für die beliebige Null-Eins-Folge zu Anfang, ist das
Verfahren korrekt.
Und jetzt sage ich, nach dem Null-Eins-Prinzip ist jede Folge damit
korrekt sortiert.
Das Null-Eins-Prinzip sagt folgendes, wenn irgendein nur auf
Vergleichen basierender Algorithmus, das ist also die wichtige
Bedingung, nur auf Vergleichen basierend, ich darf keine weiteren
Informationen über die Elemente ausnutzen.
Ich darf nicht ausnutzen, dass das Null und Eins sind, oder Sechs und
Fünf sind.
Wenn also ein solcher Algorithmus A alle Folgen aus Nullen und Einsen
sortiert, oder verschmilzt, dafür geht es genauso, dann sortiert oder
verschmilzt er auch jede beliebige Folge von Elementen einer
geordneten Menge.
Und das heißt, ich muss nur argumentieren für Null-Eins-Folgen, und
habe damit etwas gezeigt für die beliebige Folge.
Dahinter steckt einfach die Überlegung, was ich Ihnen gerade sagte.
Ich weiß ja nicht, an welcher Position diese Ungleichheit, also diese
falsche Reihenfolge ist.
Was ich mit Argumentationen über alle Null-Eins-Folgen hinbekomme ist,
dass ich für jede Position, an der eine falsche Reihenfolge ist, mit
diesem Verfahren, das nur Vergleichen basiert, diese falsche
Reihenfolge korrigieren kann.
Das reicht aus, um zu zeigen, für beliebige Folgen ist das Ganze
tatsächlich richtig.
Und Beweis ist natürlich so, dass man das aufwendig beweisen müsste.
Ich mache das ein bisschen wieder durch anschauliche Sachen.
Der formale Beweis geht über mehrere Seiten.
Ich mache das hier auf einer Folie.
Die Annahme ist, dass das falsch ist.
Das heißt, ich nehme an, es gibt eine Folge.
Ich habe also hier eine Folge S, S1 irgendwie bis Sn.
Die wird durch unseren Algorithmus A transformiert in eine Folge A von
S.
Die nenne ich jetzt mal einfach T1 bis Tn.
Also A von S.
Die sortierte Folge wäre jetzt T1 bis Tn.
Und ich behaupte, es gibt eine solche Folge S1 bis Sn, die durch ein
Verfahren A nicht sortiert wird.
Was heißt das, sie wird nicht sortiert?
Das heißt, ich finde...
Kommen wir gleich drauf, was das heißt.
Ganz kurz, die Idee ist, wenn es eine Folge gibt, die durch A nicht
sortiert wird, kann ich eine 0-1-Folge konstruieren, die dann
ebenfalls nicht von A sortiert werden kann.
Wenn ich also zeige, dass ein nur vergleichen basierender Algorithmus
nicht in der Lage ist, alle Folgen zu sortieren aus beliebigen
Elementen, folgt, dass dann dieser Algorithmus auch nicht in der Lage
ist, jede Folge aus 0 und 1 zu sortieren, dann heißt das doch, wenn
ich in der Lage bin, also die Kontraposition, wenn ich in der Lage
bin, jede Folge aus 0 und 1 zu sortieren, kann ich auch jede andere
Folge sortieren.
Das ist einfach Kontraposition.
So, und wie mache ich das jetzt?
Wenn die Folge nicht sortiert wird, dann heißt das, ich habe irgendein
kleinstes Element meiner Folge, S, das in der Ausgabe A von S, also in
der Folge T1 bis Tn, an einer falschen Position steht.
Irgendein Si, das ist das kleinste Element, das steht hier irgendwo,
ein Si, an der falschen Position heißt, das Element davor ist
irgendein Sj, das größer ist, aber in dieser sortierten Reihenfolge
vor dem Si kommt.
Also eine Position, was ist das denn für Quatsch?
Da habe ich also eine solche Unsortiertheit drin.
So, die trat auf, an mindestens einer Stelle, ich nehme das kleinste
Element, bei dem so etwas auftritt, das kleinste Element, das an der
falschen Stelle steht, das heißt, das Element davor, in der Folge, die
A produziert hat, muss größer sein, ist also irgendein Sj, das größer
ist.
Und das in dieser Folge A von S vor Si auftaucht.
So, jetzt definiere ich eine Folge von 0 und 1.
Wenn ich hier mir anschaue, Si und Sj, dann habe ich hier irgendwo
meine Position I, da habe ich irgendwo meine Position J, kann
irgendwie so aussehen.
Oder auch irgendwie anders, ist ja völlig egal, wie das aussieht.
Ich mache das einfach so, dass ich in meiner Folge S' eine 0,1-Folge,
jedes Element, das kleiner gleich meinem Si ist, auf 0 setze.
Und jedes Element, das größer als Si ist, auf 1 setze.
Damit ist also das Element Sj zu einem Element Sj' geworden, das 1
ist, und das Element Si zu einem Element Si' das 0 ist.
Das heißt, ich schreibe hier, ich schreibe da auf jeden Fall für das
Si eine 0 hin, für das Si eine 1.
Und ich weiß, in der sortierten Reihenfolge, bei dem A, war hier eine
Unsortiertheit.
Ich möchte also zeigen, wenn ich jetzt diese so definierte 0,1-Folge
S' mit A sortiere, A weiß ja nichts darüber, dass das 0 und 1 sind,
sondern vergleicht nur die Größen, dann steht anschließend hier die 1
und da die 0.
Das heißt, dann ist auch diese Folge nicht sortiert.
Das heißt, es werden...
Die Argumentation ist einfach, weil ja alle Operationen unabhängig
sind von den konkreten Werten, und es nur auf die Größenvergleiche
ankommt, und ich alle Elemente, die kleiner gleich als Si sind, auf 0
gesetzt habe, und alle, die größer sind, auf 1, habe ich, ja, nichts
falsch gemacht.
Das kann ich argumentieren.
Wenn ich also jetzt mir anschaue, A auf S', dann werden irgendwelche
Elemente, irgendwelche Vergleiche gemacht, von irgendwelchen folgenden
Elementen K und L.
Wenn das Sk kleiner gleich Si ist, ist es 0.
Wenn das Sl größer gleich SJ ist, ist es auf jeden Fall 1.
SJ ist ja auch auf 1 gesetzt worden, auf jeden Fall größer als 1.
Das heißt, die Wirkung dieses Vergleichs ist auf jeden Fall die
gleiche wie vorher bei dem Größenvergleich, weil das eine ist kleiner
als auf jeden Fall in der Folge S, weil das Sk auf jeden Fall kleiner
als das L, weil das Sk ja kleiner gleich Si ist, und das Sl größer
gleich SJ, und Si ist kleiner als SJ.
Also das ist schon mal klar.
Das heißt, sie haben die gleiche Wirkung.
Entweder wurden Sk und Sl in der Anordnung verglichen, dann bleiben
sie stehen, oder sie wurden vertauscht, wenn sie andersrum verglichen
wurden.
Alle anderen Vergleiche haben aber keine Relevanz für die
Ordnungsrelation bezüglich Si und SJ.
Da werden ja nur Elemente, die kleiner als Si sind, miteinander
verglichen.
Das sind jetzt alles Nullen.
Oder Elemente, die größer als SJ sind, das sind jetzt alles Einzelnen.
Oder Elemente dazwischen.
Naja, aber das hat auch keine Relevanz.
Also die Vergleiche, bei denen Si und SJ tangiert sind, wobei es auf
deren Reihenfolge ankommt, die sind alle abgedeckt.
Und das heißt, dass in As', also in der durch A umgeordneten Folge S',
Si' und SJ' an den gleichen Positionen stehen müssen, wie in A von S.
Also so wie hier angedeutet.
Und das heißt, dass ich hier auch eine nicht sortierte Folge habe.
Damit habe ich eine Folge definiert, S', eine 0-1-Folge, die durch
dieses Verfahren A ebenfalls nicht sortiert werden kann, weil diese
Unsortiertheit in der so konstruierten Folge S' bei Anwendung des
Algorithmus A an der gleichen Position vorkommt.
Und damit habe ich genau das gezeigt.
0-1-Prinzip, es reicht zu argumentieren für 0-1-Folgen, um etwas über
beliebige Folgen sagen zu können.
Das ist ein tolles Beweisprinzip, weil es nämlich den Aufwand deutlich
reduziert.
Ich habe zwei hoch N verschiedene 0-1-Folgen, aber ich habe in
Fakultät verschiedene Terminationen von Elementen, über die ich sonst
etwas sagen müsste.
Der Aufwand ist deutlich höher.
In Fakultät ist er deutlich größer als die Anzahl dieser 0-1-Folgen.
Zwei hoch N ist immer noch groß, aber die Argumentation mit 0-1-Folgen
ist deutlich einfacher, weil ich mich nur über die Grenzen zwischen 0
und 1 argumentieren muss, als für die anderen Verfahren.
Und jetzt haben wir noch 5 Minuten, das reicht noch, um Ihnen noch ein
bisschen mehr zu zeigen.
Also, das, was ich vorhin schon angedeutet habe.
Ich habe einen Parallelalgorithmus formuliert als irgendein Programm
auf Parallelrechnern und da werden jetzt diese Verfahren ausgeführt.
Logische Ausführung von Operationen auf diesen verschiedenen
Elementen.
Das Ganze kann ich aber auch als ein Vergleichernetz darstellen.
Vergleichernetz bedeutet, ich habe meine Position, in dem Fall also 1
-16.
Jetzt schaue ich mir an, welches sind denn die Vergleiche, die durch
dieses Schema hier ausgeführt werden.
Naja.
Für OEM von 2 werden 2 Elemente jeweils verglichen, die ich durch so
ein sukzessives immer wieder Perfect Unshuffle auseinandergezogen
habe.
Und das sind gerade Elemente, die gerade den Abstand in halbe haben.
1 und in halbe plus 1 werden verglichen, die beiden Positionen.
Entsprechend 2 und in halbe plus 2 und so weiter.
Das ist genau dieser eine Vergleich, dieses OEM von 2, das ist unser
Komplex auf folgende Länge.
Also, das verschmelzt von 2 folgende Länge 1.
Das ist gerade ein Vergleich.
Das ist dieses hier.
Das ist also unser OEM von 2.
Der erste Schritt, der erste Vergleich, der ausgeführt wird.
Das andere ist alles ein logisches Umkopieren.
Und danach habe ich genau diese weiteren Operationen auszuführen.
Das sind diese Schritte hier.
Das ist der erste solche Schritt.
Es werden 4 Vergleiche ausgeführt in diesem Fall.
Ich habe nämlich 4 Folgen der Länge 2.
Also 4 Folgenpaare der Länge 2, die verschmolzen werden müssen.
4 mal müssen 2 Folgen der Länge 2 verschmolzen werden.
Wenn ich 2 Folgen der Länge 2 verschmelzen möchte, dann muss ich genau
diese Situation...
Ich habe jetzt 1, 2, 3, 4.
Das muss ich die beiden vergleichen.
Das ist jetzt am Ende meine sortierte Folge.
Das ist genau dieser Punkt.
Und die liegen jetzt hier so in der Mitte.
Das liegt halt gerade an den Indizes dieser Elemente.
Die werden gerade jetzt so miteinander verglichen.
Und anschließend habe ich diesen Schritt.
Da sind jeweils 2 Folgen der Länge 4, die verschmolzen werden müssen.
Bei 2 Folgen der Länge 4 habe ich 3 Vergleiche, die ausgeführt werden.
Ich weiß nicht, was das hier jetzt sein soll.
Das sind diese Vergleiche.
Und dann kommt am Ende nochmal ein Schritt.
Das ist praktisch der letzte, der hier oben angedeutet ist.
Das sind diese Vergleiche, die nacheinander ausgeführt werden.
Also iterativ, von unten, mache ich einmal den Vergleich für...
Ups.
Das ist ja echt witzig.
Da sehen Sie, dass man auch manchmal etwas anderes tut.
Ich muss hier mal entspannen.
Also, ich habe hier am Ende noch einmal diesen einen Vergleich.
Und das heißt, ich habe insgesamt diese verschmelzten durchgeführt.
In genau diesen Lockend-Schritten.
Und das ist das Vergleichende.
So.
Und wir hatten jetzt gesehen, dass das eben ausreicht für unser
Sortieren.
Die Korrektheit, also das nervt wirklich.
Jetzt haben wir also hier ein gleiches Netz.
Und jetzt nur noch ganz kurz.
Ich kann noch ein anderes Verfahren angehen, das sogenannte Bitonic
Sort.
Da schaue ich mein Verfahren ein bisschen anders an.
Ich sehe aber, die Zeit ist eigentlich um.
Okay.
Nächstes Mal schauen wir uns Bitonic Sort an.
Sie haben noch eine Frage.
Nochmal?
Nächste Woche hatte ich das angekündigt, dass das der Fall ist.
Warum mache ich nächste Woche am 4., das ist bereits morgens.
Da können Sie sich mal kurz gucken.
Das muss ja irgendeinen besonderen Grund haben.
Das ist am 4.
Am 4.
Da, da, da, da, da, da, ich weiß es gar nicht.
Das hatte irgendeinen Grund gehabt, dass ich das ursprünglich mal
gesagt habe.
Aber ich sehe den Grund im Augenblick gar nicht.
Also, ich kann das genauso gut wie Sie.
Der Grund ist...
Das hat sich erledigt.
Hat sich erledigt.
Die Vorlesung ist ganz normal.
Nehmen Sie die Meldung aus dem Forum raus oder aus der Ankündigung
raus.
Die Vorlesung ist also nächste Woche auch ganz normal.
Um 9.45 Uhr.
Hier in diesem Raum.
Ja?
Okay.
Gut.
Und dann machen wir nächstes Mal hiermit weiter.