So, schönen guten Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung effizienter Algorithmen
und fange gleich an mit der kurzen Wiederholung.
Sie erinnern sich, letztes Mal habe ich Ihnen so ein paar Applets
gezeigt, von dem Mappingansatz und auch die hier von der
Verbindungsstruktur, von dem Butterfly-Netzwerk.
Dann sind wir gleich weitergegangen.
Ich habe Ihnen etwas erzählt über die Rekurrenzgleichung.
Auch daran erinnern Sie sich hoffentlich, dass wir uns hier angeguckt
haben, dass man bestimmte Probleme, wenn man sie mit dem Konker-Ansatz
bearbeitet, dass man den Aufwand sehr systematisch abschätzen kann,
dass man dann so schöne Gleichungen kriegt, die sich hier angegeben
sind, hier unten diese Rekurrenzgleichungen.
Und um nicht jedes Mal wieder das lösen zu müssen, gibt es eben da so
einige Standardverfahren, wie man das machen kann.
Und wir hatten einmal diesen einfachen Spezialfälle, bei denen der
Aufwand für das Aufteilen in Teilprobleme und das Zusammensetzen der
Lösungen konstant ist oder linear ist.
Da kann man relativ einfach die Abschätzungen angeben.
Und für den allgemeinen Fall hatten wir uns das mit dem Mastertheorium
angeschaut, wo es eben auch immer darum geht, wie groß ist der Aufwand
für diese Funktion d von n, für das Aufteilen und das Zusammensetzen
im Vergleich zu diesem Term n hoch log zur Basis c von k,
beziehungsweise, das entspricht ja diesem k hoch m, also wenn k die
Anzahl der Teilprobleme ist, die wir aufteilen, dann m ist gerade n
log in n zur Basis c, Quatsch, log zur Basis c von n.
Und das waren diese beiden Terme, deren Verhältnis im Wesentlichen
entscheidet, was dann dabei rauskommt.
Und ich hatte eben dieses angegeben, damit kann man also sich das
Abschätzen von Aufwänden bei solchen, die bei den CONCA-Ansätzen
relativ leicht ausrechnen und das relativ leicht durchführen.
Und dann kamen wir zum nächsten Kapitel, da geht es jetzt um eben
eines der Standardprobleme, die man sich anguckt bei dem Thema
effiziente Algorithmen.
Da geht es um das Kapitel Suchen und Sortieren und ich habe Ihnen
erstmal nochmal dargestellt, welche Probleme wir überhaupt zu
bearbeiten haben, wie man zugreifen kann auf die einzelnen Elemente.
Also hier waren die Probleme angegeben, Sortierprobleme, dass ich also
aufsteigen oder absteigen sortieren möchte oder ich möchte
verschmelzen oder ich möchte zwei sortierte Listen verschmelzen zu
einer sortierten, oft in Teiloperationen beim Sortieren.
Oder man muss überhaupt erstmal sehen, ob ein Element in einer Liste
ist.
Das sind also Suchoperationen und dann geht es eben darum, wie finde
ich ein Element innerhalb einer größeren Liste oder einer größeren
Menge von Elementen.
Eine der Standardaufgaben, mit dem wir es heutzutage ganz oft zu tun
haben, wobei das auch schon vor dem Aufkommen der Suchmaschinen eine
der wesentlichen Aufwände war, in der Datenverarbeitung auf Daten
zuzugreifen und dann geeignet zu modifizieren.
Wir hatten uns überlegt, wie kann man die Komplexität messen für
solche Operationen.
Da ist eben klar, dass es weniger die arithmetischen Operationen sind,
sondern mehr die Vergleiche von Schlüsseln und bei parallelen
Algorithmen natürlich die Anzahl der Schritte.
Und wir hatten uns dann die Sortierverfahren nochmal kurz angeguckt,
die Sie ja eigentlich überwiegend kennen.
Sortieren durch Auswahl.
Da habe ich Ihnen gezeigt, wie man den Aufwand für das Minimum
abschätzen kann.
Für sequenzielle Verfahren, dann aber auch für parallele Verfahren, wo
man zunächst mal denkt, Log N ist das Optimum.
Es geht aber eben auch in konstanter Zeit mit dem entsprechenden
parallelen Berechnungsmodell.
Nur, dass man eben sieht, wie man hier das machen kann.
Und natürlich ist es so, wenn man, da hatte ich letztes Mal noch
diskutiert mit Herrn Zuckler darüber, selbstverständlich, wenn man
sich anguckt, ich habe hier Log N-Schritte, um das Minimum zu
bestimmen, wenn ich also N Prozessoren verwende, wenn ich aber N oder
N halbe Prozessoren verwende, wenn ich aber das einfach durch Log N
dividiere, dann kann ich natürlich in Log N-Schritten gewisse Minimum
bestimmen und den Rest dann entsprechend auch wieder in Log N, sodass
man dann mit N durch Log N in Zeit Log N das Minimum bestimmen kann
und dann natürlich ein optimales Verfahren hat.
Aber das ändert nichts daran, dass wir, um jetzt auf konstante Zeit zu
kommen, brauchen wir eben doch dann N Quadrat Prozessoren bzw.
N Quadrat parallele Vergleiche, können dann aber eben konstante Zeit
erreichen.
Also, das nur kurz als Nachbemerkung dazu.
Und dann haben wir Sortierung durch Einfügen angeschaut.
Hier ist der wesentliche Unterschied, dass wir hier im besten Fall
sogar lineare Zeit erreichen können, im Mittel aber immer noch
quadratisch sind und auch im schlechtesten Fall natürlich quadratisch.
Wir kamen dann auf Bubble Sort, auch im schlechtesten Fall
quadratisch.
Wenn man Glück hat und eine gute Variante verwendet, kann man eben
hier adaptiv aufführen, sobald man keine Vergleiche mehr macht, dann
hätten wir im besten Fall lineares Verhalten.
Aber im schlechtesten Fall ist, wie gesagt, quadratisch, im Mittel ist
auch quadratisch.
Und das Interessante ist jetzt aber das, was ich Ihnen letztes Mal
ganz kurz schon andeutete, das war die letzte Folie beim letzten Mal,
die parallele Variante von Bubble Sort, genannt Odd-Even Transposition
Sort.
Und das ist ein sehr interessantes Verfahren.
Und ich stelle Ihnen das ganz bewusst deswegen vor, weil man hier
folgendes sieht.
Wir haben ein Verfahren, das ist für das sequenzielle Sortieren
schlecht, weil wir Zeit im Quadrat brauchen.
Wenn wir aber das Ganze jetzt parallel machen, dann bekommen wir auf
einmal die Aussage, dass für eine gewisse Rechnerstruktur, nämlich für
ein lineares Feld von Prozessoren, dieses Verfahren optimal ist.
Es geht nicht besser als mit diesem Verfahren OETS.
Und das ist im Prinzip eine einfache parallelisierte Variante von
Bubble Sort.
Und hier ist sie eben angegeben, das ist also das Verfahren.
Und noch einmal kurz, was wir da machen, wir führen einfach auf den
Elementen einer Liste, wenn das hier also unsere Elemente der Liste
sind, dann führen wir einfach sukzessive immer auf Fahren von
Elementen Vergleiche durch, und zwar einmal auf den, wo der erste
Index ungerade ist.
Wenn wir hier also mit 1, wenn das die Indizes sind, 1, 2, 3, 4, 5, 6,
fangen wir also im ersten Schritt mit den Ungeraden an, jeweils 1, 2,
3, 4, 5, 6 und im nächsten Schritt werden die Paare verglichen, bei
denen der erste Index gerade ist.
Und dann machen wir das nächste nochmal.
Wieder ungerade, gerade und so weiter.
Deswegen OETS, Transposition Sort.
Also OETS heißt immer abwechselnd Paare mit gerade im ersten Index und
ungerade im ersten Index vergleichen.
Und Transposition heißt, wir vergleichen, ob die beiden Elemente in
der richtigen Ordnung sind und wenn nicht, müssen sie halt nochmal
vertauscht werden.
Deswegen Transposition Sortieren durch Transposition, durch einfaches
Vertauschen der Elemente.
Das ist hier angegeben, entweder Paare mit einem ungeraden ersten
Index, deswegen hier 2I-1 oder mit einem geraden ersten Index und das
Ganze n-mal.
Also in dem Fall, wenn wir eine Folgelinie 6 haben, müssten wir 6
solche Schritte machen und dann sind wir fertig.
Behaupte ich einfach.
Dass wir gleich sehen, dass das tatsächlich stimmt.
Und wenn man so ein Verfahren durchführt, sieht man sofort, wie lange
das dauert.
Wir haben hier N-Schritte, die nacheinander ausgeführt werden und
innen drin eine Schleife, bei der Vergleiche parallel ausgeführt
werden.
Das ist eine Pseudo-Programmiersprache, bei der wir einfach andeuten,
dass wir gewisse Dinge parallel machen.
Und das hier geht also in einem Zeitschritt und das heißt, wir können,
also hier dieses N-Paar, das müsste eigentlich hier eingerückt sein,
dann wäre es richtig.
Also das gehört zu dieser Schleife dazu.
Ein Zeitschritt, ein paralleler Schritt.
N-Schritte also.
Wir haben N-halbe Prozessoren, die arbeiten müssen.
Das heißt, der Zeitgewinn, der ist in NlogN.
Wir haben mit N-halben Prozessoren eine Reduktion von Zeit.
Ja, nicht N², sondern wir müssen immer, natürlich können wir Bubble
Sort umzählen, können wir Bubble Sort um Faktor N verbessern.
Das müssen wir immer vergleichen mit dem besten sequenziellen
Verfahren und das ist nun mal NlogN.
Und deswegen ist also der Zeitgewinn hier nur in NlogN, weil wir von
NlogN runterkommen auf N.
Und die Effizienz ist NlogN durch N, das ist auch eine schlechte
Effizienz.
Also die einzelnen Prozessoren sind nicht sehr stark ausgelastet.
Aber, wie gesagt, auf einem linearen Feld geht es gar nicht besser,
weil wir auf einem linearen Feld alleine dafür, wenn wir aufsteigen
und sortieren wollen, das Minimum ist anfangs hier, dann muss das ja
einmal ganz rüber wandern und dafür brauchen wir nur einmal dann N-1
Vertauschungen.
Das heißt, es geht gar nicht mit weniger Aufwand, wenn wir nur lokale
Vertauschungen oder nur lokale Operationen haben.
Das also zu diesem Odd-Even-Transposition-Sort.
Ein klassisches, paralleles Verfahren, das auch einen Vorteil hat,
dass man das, wie man hier sich überlegen kann, das ist also nochmal
das Verfahren.
Sie sehen gleich, warum ich hier diese Diagonale so besonders betone.
Da kommen wir gleich nochmal drauf.
Was man hier sieht ist, wir haben hier einfach die Vergleiche, was ich
gerade eben auch angedeutet habe, in die Zeit ausgerollt.
Also das ist hier praktisch der Zeitstrahl.
Und dann sieht man, was hier so nacheinander passiert.
Und jetzt kann man Folgendes machen.
Wenn man das Verfahren in Hardware implementieren möchte, dann würde
man einfach jeweils so einen Baustein in Hardware implementieren und
hätte dann diese einzelnen Vergleicherbausteine einfach in Hardware
vorliegen.
Und könnte so eine Folge dort sortieren, indem man sie durch dieses
Netz von Vergleichern hindurchschiebt.
Und sobald so eine Folge durch die erste Zeile durch ist, kann die
nächste Folge reingeladen werden.
Das heißt, wir hätten dann auf einmal die Möglichkeit, hier mit
unserem üblichen Ansatz, Pipelining, wir könnten eben ganz viele
Sortieroperationen direkt nacheinander machen, mit einem Abstand von 1
ein Takt.
Und das heißt, wir hätten einen optimalen Durchsatz.
Und hätten also dann im Endeffekt, wenn man sieht, wie ist der
durchschnittliche Zeitaufwand pro Sortierverfahren oder pro
Sortierinstanz, wenn wir viele Sortierinstanzen durchführen, also
bearbeiten müssen, hätten wir konstanten Aufwand.
Und das heißt, mit einem Verfahren, das sequentiell sehr schlecht ist,
weil wir quadratische Zeit brauchen, können wir bei einer Hardware
-Implementierung auf einmal ein ganz tolles Ergebnis erzielen, nämlich
mit konstanter Periode, also im Schnitt jeden Takt können wir eine
Folge dort eingeben und jeden Tag kriegen wir eine sortierte Folge
raus, sofern wir viele Folgen sortieren müssen.
Und das ist etwas, was man zum Beispiel in der Signalverarbeitung
braucht.
Da braucht man Verfahren, die in der Lage sind, bestimmte Fenster von
Signalen zu sortieren.
Die kommen mit einer ziemlich hohen Frequenz an und müssen dann mit
der Frequenz bearbeitet werden.
Das heißt, wir können das mit solchen Strukturen auf einmal sehr
elegant machen.
Das nur kurz als Vorbemerkung.
Ich behaupte einfach, wir können sortieren, das müssen wir jetzt
beweisen, dass das so ist.
Also die Behauptung ist, nach N-odd-even-Schritten ist die Folge
sortiert.
Und ich behaupte jetzt, das ist egal, ob man odd-even macht oder even
-odd, das heißt, das ist egal, ob ich als ersten Schritt diesen hier
habe, wo ich mit dem Paar S1, S2 anfange oder ob ich den zweiten
Schritt zuerst nehme, wo ich erst mit den geraden Paaren beginne und
dann die ungeraden nehme.
Das ist also egal.
Behaupte ich einfach.
Und jetzt möchte ich das beweisen.
Jetzt erleben Sie eine Beweistechnik, die ein bisschen anders ist als
das, was Sie sonst kennen.
Ist auch eine Induktion.
Aber ich mache das etwas wenig formal, sondern visuell.
Also, was machen wir?
Erstmal für N gleich 1 das ganze Trivial.
Wenn ich eine Folge, die Länge 1 habe, dann brauche ich nicht mal
einen Schritt.
Also ein Schritt reicht dann auf jeden Fall aus.
Nach N-Schritten ist die Folge sortiert.
Und auch nach N-even-odd-Schritt.
N gleich 2, nehmen wir das auch nochmal zu Beginn.
Ein Odd-Schritt, wenn wir zwei Elemente haben.
Nur diese beiden hier.
Wir wollen die beiden sortieren.
Wenn wir mit einem Odd-Schritt anfangen, dann werden S1, S2 im ersten
Schritt sortiert.
Wir sind fertig, wir brauchen gar nicht zwei Schritte.
Wenn wir aber mit even-odd das machen, wenn wir also erst mit einem
geraden Vergleich anfangen, dann sehen Sie, ist im ersten Schritt kein
Vergleich zwischen S1 und S2 möglich, sondern erst im zweiten Schritt.
Aber wer ist dann?
S1 mit S2 vergleichen.
Vorher hatten wir S2 mit einem fiktiven Element S3 verglichen.
Deswegen müssen wir hier sagen, weil wir die Aussage machen darüber,
egal ob odd-even oder even-odd, es reichen zwei Schritte aus, stimmt
das auch für den Fall.
So, und jetzt nehmen wir an, wir haben das für n gezeigt und wollen
zeigen, dass es für n plus 1 auch gibt.
Nehmen wir an, das hier ist jetzt gerade die Situation für n plus 1.
Ich radiere mal kurz hier diese Annotation wieder weg.
Ups, jetzt macht er mir wieder hier... Das ist nicht richtig.
Sie sehen, das ist gar nicht so einfach.
Das wegradieren macht er nicht so, wie er es dann nicht soll.
Er setzt das sofort um in Klicks in dem Verfahren.
Also, was wollte ich Ihnen hier zeigen?
Machen wir das schön in der Reihe nach.
Von n auf n plus 1.
Wir nehmen an, wir haben das für n gezeigt und wollen das jetzt für n
plus 1 zeigen.
Wir haben also eine Folge der Länge n plus 1, n plus 1 Elemente, die
wir sortieren wollen.
Und jetzt müssen wir zeigen, dafür reichen n plus 1 Schritte.
Und jetzt betrachten wir den Weg des maximalen Datums.
So, das maximale Datum, das maximale Element liegt im schlechtesten
Fall hier ganz links.
Im schlechtesten Fall liegt das dort.
Wenn das dort liegt, muss es ganz weit wandern, nämlich ganz bis nach
rechts.
Also in diese Position hier.
Das kann es nur durch Vergleiche mit den Nachbarn.
Und wenn es eben ganz links liegt, wird es gleich im ersten Schritt
eins nach rechts bewegt, dann im nächsten Schritt wieder eins nach
rechts und so weiter.
Sie sehen, dieses Element wandert von links nach rechts.
Was Sie auch sehen ist, dass natürlich die Elemente, die rechts von
dem maximalen Element sind, natürlich gerade um eins nach links
geschoben werden.
Also, wenn das maximale Element zuerst bei s1 war, wird das Element s2
anschließend eins nach links gewandert sein, auf diese Position s1.
Hier wird, wenn das Element, das hier im zweiten Schritt an Position 3
ist, wird mit s2 verglichen, wandert eins nach links.
Und so wandert eben immer das Element, das gerade mit dem maximalen
verglichen wurde, um eins nach links.
Und offensichtlich braucht dieses maximale Element maximal n plus eins
Schritte, bis es am Platz pn plus eins angelangt ist.
Das muss ja ganz rüber wandern, es würden hier sogar n Schritte
reichen.
Wir brauchen ja n plus eins, weil ich ja nur hier einmal ganz
durchlaufen muss.
Und das sind gerade bei n plus eins Elementen.
In jedem Schritt läuft es ja hier durch.
Das Problem ist wieder even-odd.
Wenn ich mit even-odd anfangen würde, und das ist an der ersten
Position, dann würde das im ersten Schritt nicht angerührt werden,
dann würde es erst im zweiten Schritt angerührt werden.
Und dann brauche ich noch die n Schritte, um ganz nach rechts zu
kommen.
Also doch n plus eins.
Ich kann also nicht das von n plus eins auf n reduzieren, für den
Fall, dass wir eben einen even-odd-Vergleich haben.
Und jetzt mache ich folgendes, dass ich den Weg des maximalen Datums
einfach eliminiere.
Ich will mir einfach anschauen, was passiert eigentlich mit dem Rest,
wenn ich das maximale Datum rausnehme.
Und dann sehen Sie, dann bleibt hier etwas übrig, rechts, das sind die
drei Vergleiche.
Ich hatte ja gesagt, die Elemente wandern eigentlich bei dem Vergleich
alle um einen Schritt nach links.
Ich habe jetzt einfach alle um eins nach links laufen lassen.
Das war das, was bei den Vergleichen mit dem maximalen Element
passiert ist.
Ich habe die anderen Vergleiche alle mitlaufen lassen, da ist ja
nichts weiter logisch passiert.
Diese anderen, alle anderen Vergleiche werden durch das Wegfallen des
maximalen Elements gar nicht berührt.
Da passiert gar nichts.
Und dieses, dass die bei dem Vergleich mit dem maximalen Element eins
nach links wandern, habe ich hier angedeutet, dadurch, dass ich sagte,
hier das wandert einfach alles einmal nach links.
Das heißt, ich habe jetzt mir angeschaut, wie viele Vergleiche brauche
ich eigentlich, wie viel Zeit braucht es, damit das maximale Element
an den richtigen Platz kommt.
Das sind n plus eins Schritte.
Und der ganze Rest, die ganzen restlichen Vergleiche, wenn wir uns die
anschauen, dann entsprechen die doch gerade einem even-odd, oder wenn
wir es andersrum gemacht hätten, einem odd-even Transposition Sort auf
n Elementen.
Und von dem wissen wir, dass wir odd-even Transposition Sort auf n
Elementen in der Zeit n ausführen können, mit n odd-even Schritten
ausführen können, oder even-odd Schritten.
Und das heißt, wir wissen, dass diese Zeit ausreicht, um die gesamte
Folge zu sortieren.
Das heißt, insgesamt brauchen wir nicht mehr als n plus eins Schritte,
um die ganze Folge zu sortieren.
Dieses, was ich Ihnen hier gezeigt habe, dieses einfach, ich zeige
Ihnen, wie man das, die Diagonale einfach, oder den Weg, das maximale
Element, das kann ja irgendetwas sein, das ist der schlechteste Fall.
Wenn man das rausnimmt und sieht, wie sich das auswirkt auf die
Vergleiche, und man sieht dann sofort, dass der Rest gleich wieder ein
odd -even Transposition Sort ist, denke ich, überzeugt Sie, dass das
richtig ist.
Wenn ich Ihnen das formal aufschreiben würde, dass das Ganze korrekt
läuft, wäre das ein ziemlich aufwendiges Verfahren, um das Ihnen
formal hinzuschreiben.
Ich habe das früher genannt, Beweis mit Folie.
Da habe ich einfach Folien verschoben, jetzt kann ich das animieren.
Das ist also eine einfache Beweistechnik, Beweis mit Folie, man
visualisiert etwas und erreicht den Zweck eines Beweises, ich kann Sie
überzeugen, dass das richtig ist.
Man muss das gar nicht formal hinschreiben, der einzige Zweck des
Beweises ist ja, dass man jemanden überzeugt, dass das, was man
behauptet, richtig ist.
Also, restliche Folge wird sortiert, damit sind wir fertig, haben
bewiesen, das Verfahren ist korrekt.
So, in n plus 1 Schritten wird die gesamte Folge sortiert und wir
haben also jetzt die Korrektheit gezeigt.
Damit ist das Verfahren abgeschlossen, wichtiges Verfahren und ein
wichtiger Punkt ist halt nochmal, wenn ich das ganze Verfahren in
Hardware mache, also in Hardware habe ich also Periode O von 1.
Und das ist ein ganz wichtiger Punkt, dass ich hier mit einem sehr
hohen Durchsatz im Schnittaufwand einen Takt für Vergleich mit einer
hohen Frequenz solche Sortierprobleme lösen kann.
Das wird bei dem Einsatz in der Signalverarbeitung eben durchaus so
gemacht, dafür ist das ein ganz wichtiges Verfahren.
Vor allem ist hier ein Punkt ganz wichtig, ich brauche hier nur sehr
kurze Verbindungen zwischen den einzelnen Elementen, ich habe hier
keine langen Leitungen.
Das heißt, da die ganz dicht nebeneinander sind, habe ich keine langen
Leitungen, ich brauche also keine langen Signallaufzeiten, ich kann
das ganz mit einer hohen Frequenz takten.
Und habe also noch wieder einen Vorteil, das ist ein Verfahren, das
sehr lokal arbeitet, also eines dieser systolischen Algorithmen, die
ich Ihnen schon gezeigt hatte für die Matrix-Modifikation, die ja auch
mit lokalen Operationen auskam, mit direkter Nachbarschaft, keine
langen Leitungen.
Deswegen systolischer Algorithmus, das ist also ein Beispiel für
systolisches Sortieren.
Man kann auch andere solche systolische Sortierverfahren angeben, aber
das will ich jetzt im Augenblick nicht machen, kommen wir später noch
wieder drauf zurück.
Anderes Verfahren, das Sie auch schon kennen, Sortieren durch Teilen,
die beiden Conquer-Einsatz.
Klassisches Verfahren, das Sie kennen, ist Quicksort.
Das Wesentliche ist ja hier bei Quicksort, dass wir sagen, wir wollen
sortieren und das Sortieren ist uns wie üblich zu schwer.
Wir machen uns das Problem einfacher, wir wählen einfach ein Element
aus und nehmen einfach wahlfrei irgendwie das erste Element.
Also dieses Element hier, das sei irgendein C, sogenanntes Pivot
-Element, wie man das normalerweise bezeichnet.
Und dann ist eben die wesentliche Idee von Quicksort, dass wir den
gesamten Aufwand des divide-and-conquer-Ansatzes in das Aufteilen der
Folge stecken.
Und da gar nichts mehr zusammensetzen müssen, sondern dass eigentlich
das Zusammensetzen schon erledigt ist.
Also, wir zerteilen, wir ordnen einfach diese Folge um und erzeugen
die Teilprobleme dynamisch dadurch, dass wir einfach diese Folge so
umordnen, dass alle Elemente, die kleiner gleich C sind, hier links
sind, und alle die größer als C sind, rechts ist daneben.
Ich nehme einfach diese beiden, ich erzeuge also diese Elemente, das S
-Strich, Teilfolgen S-Strich und S-Zweistrich, ordne einfach die Folge
um und kann dann den gleichen Algorithmus auf S-Strich und S
-Zweistrich anwenden und das C steht schon an der richtigen Position,
das ist das Wesentliche.
Das heißt, wenn ich jetzt weitermache, habe ich jedes Element
irgendwann an die richtige Position gebracht und bin fertig.
Ja, wie groß ist denn der Aufwand?
Das wissen Sie auch, wie groß der Aufwand ist.
Also, ich mache hier ein dynamisches Aufteilen, wenn ich immer schön
in die Hälfte aufteile, dann habe ich immer halbieren, wissen wir
genau, Log N solche Elemente, Log N solche Schritte.
Das heißt, wir haben Log N Ebenen, mit denen wir etwas aufteilen
müssen und dann haben wir also im besten Fall diese Darstellung.
Wir haben zweimal bei den zwei Teilfolgen den Aufwand, um eine
Folgelänge in halbe zu sortieren, rekursiv und dazu haben wir den
Aufwand gebraucht, um aufzuteilen.
Wie groß ist denn der Aufwand?
Wie teilt man denn hier überhaupt auf?
Ich gehe darauf nicht weiter ein, aber Sie wissen das, wie das geht.
Ich vergleiche einfach sukzessive die Elemente an der ersten und an
der letzten Position und schiebe die immer so nach rechts und nach
links und wann immer das Position an der rechten Position kleiner ist,
als das an der linken Position, schiebe ich im Prinzip das kleinere
Element oder vertausche ich die beiden Elemente und da habe ich dafür
gesorgt, dass also die kleineren alle nach links wandern, das wollte
ich hier erreichen, die größeren alle nach rechts und das C kommt an
die Position, bei der sich dann irgendwann diese beiden Zeiger
getroffen haben.
Daher kommt das C und dann weiß ich, es sind alle, die links sind,
kleiner als alle, die rechts sind und das C ist genau in der Mitte.
Und damit bin ich schon fertig.
Also das ist ein ganz einfaches Verfahren und der Aufwand für dieses
Aufteilen, der ist linear, das ist also auch ein wesentlicher Punkt,
linearer Aufwand für die Aufteilung und das heißt, wir haben hier,
unser D von N ist linear und dann wissen wir aufgrund unserer
Abschätzung, Rekurrenzgleichung, dann ist die im besten Fall Zeit N
log N.
Allgemein ist es natürlich nicht so einfach, im schlechtesten Fall
kann das natürlich anders aussehen, denn die Zeitkomplexität ist ja
nicht so einfach abzuschätzen.
Wir wissen nur, wir müssen Quicksort anwenden auf die Folge S' und auf
die Folge S''.
Und anschließend haben wir noch einen linearen Aufwand.
Und das ist halt nicht klar, wie groß S' und S'' sind, das kann ja
sehr unterschiedlich sein.
Wenn wir Pech haben, liegt halt das C ganz links.
Das heißt, das ist das kleinste Element.
Wenn es das kleinste Element ist oder auch das größte, dann wirkt das,
dass S' oder S'' leer sind.
Und in dem Fall hätten wir eine Reduktion in der Problemgröße nur um
1, weil wir von einer Folgelänge N auf eine Folge von N-1 kommen.
Und wir könnten, wenn sich das so fortsetzt, immer nur eine Reduktion
um 1, hätten wir N-mal solche Partitionierungsaufgaben zu machen und
müssten jeweils partitionieren, das ist dann wie üblich Summe der
Zahlen von 1 bis N und wir hätten quadratische Zeit im schlechtesten
Fall.
Deswegen Quicksort ist nur in Einschränkungen wirklich quick, wirklich
schnell, weil es halt im schlechtesten Fall quadratisch ist, aber im
Mittel, wo steht hier was vom Mittel, kommt auf der nächsten Folie, im
Mittel ist es NlogN, kann ich schon verraten, das wissen Sie auch,
deswegen heißt es Quicksort, im besten Fall sogar, also auch NlogN, im
besten Fall hätten wir ein anderes Verfahren, das wir hier nicht
einfügen, das wäre besser, im besten Fall.
Aber wenn man jetzt Algorithmen vergleichen will, kombinieren will,
könnte man noch umschalten zwischen bestimmten Situationen auf ein
Verfahren, das im besten Fall dann, also in diesem Fall ausnutzt und
dort linear ist.
Das wäre aber ein bisschen zu kompliziert.
Schauen wir uns das mittlere Verhalten an.
Um das mittlere Verhalten von Quicksort abschätzen zu können, müssen
wir uns das noch ein bisschen genauer angucken, wir gucken uns einfach
an, die Anzahl der Vergleiche bei Aufruf von Quicksort auf eine Folge
der Länge J, das heißt V von J.
Und natürlich ist es so, dass bei dieser Aufteilung, also wenn wir
hier unsere Folge haben und hier ist das C und wir wollen aufteilen
und dann ist uns die Frage, wo kommt das denn nun eigentlich hin?
Wenn wir davon ausgehen, dass alle Eingabefolgen gleichwahrscheinlich
sind, dann ist auch jede Position in der Folge gleichwahrscheinlich
als Zielposition von C.
Und das heißt, wir hätten den Aufwand für, na gut, bei einer Folge
Länge 1 und bei einer Folge Länge 0 ist der Aufwand 0, das ist klar.
Wenn wir eine Folge Länge N haben, dann ist der Aufwand dafür im
Mittel, gerade der Aufwand, um zu partitionieren, das brauchen wir
immer, der Aufwand des N plus 1.
Das ist also das D von N.
Das ist also der Partitionierungsaufwand.
Und dann müssen wir, wenn die Position I ist, dann müssen wir eine
Folge Länge I, wenn das hier also I ist, die Position, dann hat diese
Folge Länge I-1 und diese Folge die Länge N-I.
Das heißt, wir haben dann die Vergleiche für das Sortieren einer Folge
Länge I-1 und einer Folge Länge N-I drauf zu addieren.
Jede dieser Positionen I ist gleichwahrscheinlich.
Das heißt, wir müssen das Ganze noch aufsummieren und durch N
dividieren, dann haben wir den mittleren Aufwand.
Und jetzt müssen wir uns diesen Ausdruck ein bisschen genauer
angucken.
Hier können wir das N plus 1 rausziehen, dann ist das gerade N plus 1
plus, die 2 haben wir auch rausgezogen, 2 durch N mal I gleich 0 bis N
-1 V von I.
Wo kommt die 2 her?
Wenn ich hier immer VI-1 und VN-I addiere, das Ganze wird eine große
Summe.
Dann taucht natürlich das V0 auf für I gleich 1.
Es taucht nochmal auf für I gleich N.
Genau so treten also alle Werte genau zweimal auf.
Deswegen dieses 2 durch N und Summe dieser einzelnen Anzahlvergleiche
auf Folgen der Länge 0 bis N-1.
Das sind die unterschiedlichen Folgenlängen, die vorkommen können und
sie treten jeweils zweimal auf in dieser Summe.
Nun müssen wir uns das noch ein bisschen genauer angucken.
Und jetzt gibt es halt so ein bisschen Modifikationen, wie kann man
daraus jetzt eine vernünftige Darstellung hinkriegen.
Schauen wir uns einfach mal diesen Ausdruck an.
N plus 1 mal V von N plus 1 minus N mal V von N.
Das ergibt gerade diesen Ausdruck.
N plus 1 mal N plus 2.
N plus 1 mal V von N plus 1.
Dann haben wir hier also N plus 2 plus und so weiter.
Deswegen N plus 1 von N plus 2 plus 2 mal diese Summe.
0 bis N.
Also das ist jetzt hier das V von N plus 1 und das hier ist das V von
N mal N.
Und wenn wir uns das genauer anschauen, sehen wir, das hier ist
gerade, können wir hier einiges rauskürzen, das ist 2 mal N plus 1,
bleibt hier übrig.
Und wenn wir uns diese Summe anschauen und die Summe, von der Summe 2
mal Summe I gleich 0 bis N V I wird abgezogen.
2 mal Summe I gleich 0 bis N minus 1 V von I.
Da bleibt einfach nur 2 mal V von N übrig.
Und jetzt haben wir einen Ausdruck, wo V von N plus 1 steht, abhängig
von der Größe von V von N.
Das heißt, ich kann jetzt hier hinschreiben, V von N plus 1, einfache
Umformung, ist 2 plus N plus 2 mal, äh durch N plus 1 mal V von N.
Was hilft uns das?
Das ist für eine Rekursion noch gar nicht gut.
Die Rekurrenzgleichungen helfen uns dann noch nicht sehr viel, wie wir
vorher betrachtet hatten.
Behauptung ist, dieses V von N ist gleich 2 mal N plus 1 mal Summe I
gleich 3 bis N plus 1, 1 durch I.
Und wenn man sich diesen Term anguckt, der ist auch noch aus N log N.
Wie kommt man auf den Term?
Also, wo haben wir das?
V von N ist gleich...
Also das ist jedenfalls diese Summe hier.
Ich nehme jetzt einfach mal, dass das diese Summe ist.
Das kriegt man aber relativ einfach aus.
Das kann man sich einfach ausrechnen, dass ich hier auf diese Summe
komme, 2 mal N plus 1.
Das ist, wenn ich das hier einsetze, komme ich auf jeden Fall auf
solch eine Summe, dass das 2 mal N plus 1 ist, mal dieser Summe 1
durch I.
Was ich jetzt zeigen möchte, also ich muss genau, hier steht es ja,
ich muss eine einfache Induktion machen.
Ich habe das Wort Induktion übersehen.
Ich mache eine einfache Induktion, um das zu zeigen.
Wenn Sie sich diesen Term anschauen, machen Sie einen einfachen
Induktionsansatz und dann sehen Sie, dass dieser Ausdruck gerade die
Lösung ist für die Rekursion, die oben drüber steht.
So.
Das will ich jetzt nicht im Einzelnen ausführen.
Das ist wirklich ein einfacher Induktionsbeweis.
Und wenn ich also diesen Ausdruck habe, muss ich sehen, wie kann ich
das abschätzen.
Und jetzt die Behauptung, dass dieser Term gerade durch N log N
abgeschätzt werden kann.
Das will ich jetzt ein bisschen genauer machen.
Ich sage hier Summe I gleich 3 bis N plus 1, 1 durch I.
Und jetzt gucke ich mir das 1 durch I genauer an.
Und zwar schaue ich mir das jetzt an in Bezug auf Integrale.
Was schaue ich mir hier an?
Hier steht Summe 1 durch I.
Hier ist die Funktion 1 durch I aufgetragen.
Für den Wert I an dieser Position habe ich also den Wert 1 durch I
hier aufgetragen.
So.
Wenn ich das Integral betrachte von I bis I plus 1.
Das ist das, was hier unter der Kurve liegt.
Von I bis I plus 1.
Dieses Integral von I bis I plus 1 ist doch sicherlich kleiner gleich
1 durch I.
Das ist der Wert 1 durch I mal 1.
Das ist nämlich gerade... oder ich kann auch das hier angeben.
Das ist der Wert 1 durch I mal 1.
Und das Integral liegt hier gerade etwas drunter, weil es unterhalb
der Kurve liegt.
Wenn ich mir anschaue das Integral von I minus 1 bis I.
Das ist das, was hier zu sehen ist.
Da liegt das gerade etwas drüber über 1 durch I.
Das heißt, ich kann die Summe 1 durch I.
I gleich 2 bis N.
Abschätzen durch das Integral von 1 bis N.
Von 1 durch X.
Und wie man welchen Wert das hat, wissen wir.
Das ist gerade Logarithmus Naturalis von N.
Das heißt, wir haben hier insgesamt 1 plus lnN.
Und das ist natürlich Größenordnung Log N.
Also ob ich jetzt Logarithmus zur Basis E nehme oder Logarithmus zur
Basis 2, ist völlig egal, weil das eine Konstante ist.
Und deswegen kann ich hier auch hinschreiben aus O von Log N.
Und das heißt, diese Summe, die hier steht, kann ich abschätzen durch
Logarithmus von N.
Und das wird mit N plus 1 malgenommen.
Das heißt, wir haben insgesamt NlogN hier als Wert für das mittlere
Verhalten von Quicksort.
Ich habe das jetzt so ausführlich gemacht, einfach um Ihnen zu zeigen,
wie man eben so mittleres Verhalten abschätzt, so eines Algorithmus.
Und ich mache das im Weiteren in der Regel nicht, weil mir das hier zu
lange dauert.
Man muss eben hier, wie die Annahme war, ich habe eine
Gleichverteilung.
Und ich wollte einfach hier klar machen, dass wir hier eben ein
Verfahren haben, bei dem wir im mittleren Fall ein besseres Verhalten
haben als im schlechtesten Fall.
Wir haben im mittleren Fall halt hier NlogN, im schlechtesten Fall
quadratisch, im besten Fall auch NlogN.
Und das ist halt die Schwachstelle von Quicksort, dass wir im
schlechtesten Fall quadratisch verhalten haben, was uns nicht gefällt.
Und jetzt kann man versuchen, diesen schlechtesten Fall zu vermeiden.
Wir wissen ja, wann der auftritt, wenn die Aufteilung nicht günstig
ist, wenn ich also zu wenig Elemente abschneiden kann.
Ich könnte also sagen, ich nehme einfach hier nicht immer das linkeste
Element, sondern ich nehme das linkeste, das mittlere und das rechte.
Und nehme einfach den Mittelwert von den dreien, das mittlere Element
von den dreien.
Und kann hier sofort eine Folge konstruieren, bei der auch das noch
zum schlechtesten Fall führt.
Bringt uns also auch nicht viel, kann aber trotzdem durchaus etwas
besser werden.
Und eine andere Möglichkeit wäre, ein zufälliges Element zu nehmen.
Das heißt, ich wähle einfach ein zufälliges Element aus und habe dann
ein randomisiertes Quicksort.
Ich muss dann aber jeweils noch eine Zuwachszahl erzeugen.
Und das ist auch wieder etwas Aufwand, den ich habe, um eine
Zuwachszahl zu generieren.
Wenn ich den dazuzähle, dann kann es sein, dass das doch wieder sich
nicht rechnet.
Das muss man einfach sich angucken.
Ab einer gewissen Größe der Folgen rechnet sich das durchaus.
Dann hätte man hier einen Aufwand von N log N.
Und das ist einfach eine Sache, die man dann im Einzelfall abschätzen
muss.
Auf jeden Fall, wenn ich randomisiertes Quicksort nehme, dann ist der
Erwartungswert der Laufzeit in O von N log N.
Weil dann kann ich auch zeigen, dass ich als Erwartungswert immer
rauskriege, eine gleichmäßige Aufteilung.
Oder zumindest so, dass ein gewisser Bruchteil der Folge abgeschnitten
wird.
Und dann bin ich bei einer erwarteten Laufzeit von N log N.
Für also beliebige Folgen, die eingegeben werden.
Wenn mir das nicht gefällt, dann nehme ich ein anderes Verfahren,
mache eine strenge Anwendung von die beiden Conker, verwende Merge
Sort.
Merge Sort kennen Sie vermutlich auch, hoffe ich jedenfalls.
Wenn nicht, kann ich Ihnen das sehr einfach darstellen.
Das ist hier angegeben, wie das aussieht.
Ich teile es einfach auf in zwei gleich große Teillisten.
Das heißt, hier stecke ich jetzt im Gegensatz zu Quicksort keinen
Aufwand in das Aufteilen.
Ich teile sie einfach auf.
Das ist die Aufteilung in zwei große Teillisten.
Das Ganze rekursiv weiter.
Wieder aufteilen und nochmal aufteilen.
Dann habe ich Folgen der Länge 1.
Die kann ich trivial sortieren.
Die sind schon sortiert.
Und jetzt verschmelze ich die sortierten Teilfolgen zu einer neuen
Teilfolge.
Sie wissen, wie man das macht.
Zwei Folgen werden verschmolzen zu einer längeren Folge, die sortiert
ist.
Das Verschlussverfahren zum Beispiel wäre lineare Zeit, lineare Anzahl
von Vergleichen, um zwei sortierte Teilfolgen zu einer größeren Folge
zu verschmelzen.
Also einfach so etwas hier.
Ich verschmelze die beiden jeweils zwei Teilfolgen und bekomme dann
Folgen der Länge 2, die sortiert sind.
Ich verschmelze die jeweils, bekomme Teilfolgen der Länge 4, die
sortiert sind und verschmelze die wieder und habe dann eine Teilfolge
Länge 8, die sortiert ist.
Für dieses Beispiel ist dann die Länge 3.
Also das ist ein einfacher Ansatz.
Und hier haben wir ein strenges Aufteilen, optimales Aufteilen, immer
auf die Hälfte.
Wir haben Log N Ebenen zu bearbeiten.
Also wir fangen im Prinzip an mit den Vergleichen der Einzelelemente.
Wir produzieren hier die Folge Länge 2, Länge 4, Länge 8 und sind
durch.
Das Aufteilen kostet ja nichts, da kann ich sofort anfangen mit dem
Verschmelzen.
Das heißt, ich habe es hier gleich so parallel angedeutet, im Prinzip
haben wir Log N Schritte zu machen.
Und in jedem Schritt natürlich eine Reihe von Vergleichen, um dieses
Verschmelzen der Folgen hinzukriegen.
Und wenn Sie sich das anschauen, wenn wir das mit linearem Aufwand
machen, hier hätten wir den Aufwand für Folgen der Länge 1, die zu
verschmelzen, hier haben wir N Folgen der Länge 1, um sie zu
verschmelzen, mit Aufwand 1 jeweils.
Kein Problem.
Dann haben wir in halbe Folgen der Länge 2, um sie zu verschmelzen,
wieder lineare Aufwand.
Wir haben dann in Viertelfolgen der Länge 4, jeweils Aufwand
korrespondierend zu Länge 4, also haben wir dann entsprechend in der
ganzen Ebene immer den Aufwand, ja welchen Aufwand denn eigentlich?
Wir haben Log N Merge-Stufen und in jeder Merge-Stufe haben wir den
Aufwand, um zwei Folgen der Länge N halbe im Prinzip zu verschmelzen.
Ich habe da hingeschrieben T Merge von N.
Und T Merge von N sei der Aufwand, um zwei Folgen der Länge N halbe zu
verschmelzen, zu einer Folgenlänge N.
Wenn wir uns diese Rekursion anschauen, also wenn wir uns das jetzt
sequenziell anschauen, dann ist der Aufwand für Merge Sort, also so
groß wie der Aufwand, um Merge Sort auf Folgen der Länge N halbe
anzuwenden, dass wir also hier, wir wenden es an auf Folgen der Länge
N halbe, das Merge Sort, wir kommen dann raus, unsere sortierten
Teilfolgen und müssen die beiden verschmelzen.
Zwischendurch passiert genau das, was wir dann über die Rekursion
machen.
Das heißt, wir haben dann hier den Aufwand und der Aufwand, der ist,
wissen wir, in N log N, ist aber auch sofort hier ablesbar, dass das
so ist.
Wir haben an jeder Ebene einen linearen Aufwand.
Und wenn wir das parallel machen, dann haben wir hier den Aufwand für
ein paralleles Merge Sort auf einer Folge der Länge oder auf jeweils
einer Folge der Länge N halbe und den Aufwand, um parallel zwei Folgen
zu verschmelzen.
Und jetzt ist die Frage, wie wirkt sich dieses aus, der Aufwand für
das Verschmelzen von zwei Teilfolgen.
Wenn das linear ist, naja, wenn das linear ist und wir haben hier,
dann wäre der Gesamtaufwand N.
Wir stehen einmal TPMS von N halbe plus linearen Aufwand, da ist die
Rekursion N.
Der lineare Aufwand bringt uns noch nicht so viel.
Aber stellen Sie sich mal vor, das Ganze würde in Zeit log N gehen.
Verschmelzen von zwei Teilfolgen die Länge N halbe zu einer Folge N in
Zeit log N, dann hätten wir hier eine Rekursion, bei der sofort
rauskommt, aufgrund unserer Erkenntnis von Rekurrenzgleichungen,
log²N.
Log N Stufen jeweils log N Aufwand macht log²N als Aufwand für das
Sortieren.
Da hätten wir mit einem Parallelitätsgrad, der in dem Fall größer als
N ist, eine Reduktion von N log N auf log²N.
Das ist schon gar nicht schlecht, ein deutlich besserer Zeitgewinn als
vorher.
Wir hätten dann, also 1 durch log N als...
Wir hätten von N log N auf log²N, N durch log N als Zeitgewinn, und
Effizienz wäre 1 durch log N.
Also das ist hier Merge Sort.
Merge Sort ist aber zunächst mal ein sequenzielles Verfahren.
Jetzt wollen wir uns das Ganze parallel anschauen.
Ich habe das jetzt schon angedeutet, dass man das ja auch parallel
machen könnte.
Und das sieht hier schon so schön parallel aus.
Jetzt schauen wir uns einfach das Gleiche nochmal an.
Etwas anders farbig gestaltet als ein paralleles Merge Sort.
Und vielleicht nochmal zurück.
Hier haben wir eben beim Merge Sort haben wir auch im schlechtesten
Fall, das muss ich hier nochmal betonen, auch im schlechtesten Fall
die Zeit N log N.
Besser geht's nicht.
Das ist etwas, was man eben weiß, dass man zeigen kann, im
schlechtesten Fall und im...
Ich weiß gar nicht, ob ich das später nochmal zeige, aber unsere
Anzahl der Vergleiche, die wir haben, wissen wir beim Sortieren, ist
ja die längste Fahrtlänge im schlechtesten Fall, oder mittlere
Fahrtlänge im Anzahl der Vergleiche im Mittel.
Und man kann eben relativ leicht zeigen, dass egal welches Verfahren
man nimmt, eine untere Schranke für die Anzahl der Vergleiche, im
schlechtesten Fall und auch im Mittel, ist N log N.
Einfach bei einem Baum, der hier insgesamt N Fakultät verschiedene
Blätter hat.
Die brauchen wir beim Sortieren.
N Fakultät verschiedene Permutationen in der Eingangsfolge sind
möglich beim Sortieren.
Steht hier N Fakultät, das heißt wir müssen hier als Höhe hinschreiben
einen Log von N Fakultät.
Ein Log von N Fakultät ist gerade N log N.
Und dann haben wir hier als untere Schranke für die Höhe des Baumes N
log N.
Und zwar ist das für einen gleichmäßigen, für einen fast vollständigen
binären Baum so.
Und man kann zeigen, dass also solche fast vollständigen binären Bäume
die besten möglichen Bäume sind für solche Probleme.
Gehe ich glaube ich später nochmal kurz noch rein.
Nur als kurze Bemerkung, dass wir eben daraus schließen können, dass
wir Omega als N log N haben.
Untere Schranke für die Anzahl der Vergleiche im Mittel und auch im
schlechtesten Fall.
Das heißt, wenn wir hier N log N haben, ist das ein optimales
Verfahren.
Besser geht es nicht.
Im besten Fall wissen wir, geht es besser.
Sortieren durch Einfügen kann es besser.
Das kann Merge Sort nicht.
Braucht immer Zeit in Log N.
Und ist insofern besser als Quicksort.
Trotzdem wird Merge Sort in der Praxis als sequenzielles Verfahren
nicht so viel eingesetzt, weil die Konstante davor etwas größer ist,
als bei dem mittleren Verhalten von Quicksort.
Was man aber verwendet, brauche ich nicht eingehen.
Nochmal kurz als Bemerkung, das beste Verfahren ist Heapsort, das auch
von der Konstante her besser ist, auch im Mittel besser ist als
Quicksort.
Allerdings ein optimiertes Heapsort, muss man sich genau angucken, was
man dort macht.
Heapsort kennen Sie aus Grundlagen der Informatik 1.
Das interessiert mich jetzt nicht, weil ich das nicht weiter brauche
im weiteren Verlauf.
Alle anderen Verfahren brauchte ich noch für andere Dinge, die mit
parallelen Verfahren zu tun haben.
Jetzt also zurück zu diesem Odd-Even-Merge-Sort.
Hier ist einfach die Idee, ich möchte das, was ich gerade vor
angedeutet habe, ich möchte gerne das Mergen beschleunigen und die Log
-In -Stufen nur machen von dem Merge Sort.
Und das Ganze passiert also so, dass ich jetzt ein Odd-Even-Merge-Sort
mache, wieder dieses Odd-Even.
Fängt also wieder mit den Positionen der Elemente zusammen.
Und die Idee ist einfach folgende, dass wir natürlich Merge Sort
anwenden.
Das heißt Odd-Even-Merge-Sort auf folgender Länge in Halbe.
Hier, das ist der ganz normale Merge Sort Ansatz.
Und dann kommen hier zwei sortierte Folgen raus, aufsteigend sortiert.
Das ist das Ergebnis von Odd-Even-Merge-Sort auf den zwei Folgen der
Länge in Halbe.
Und jetzt muss ich sehen, wie arbeitet jetzt Odd-Even-Merge-Sort auf
diesen Folgen der Länge in Halbe weiter.
Jetzt macht es ein Perfect-Un-Shuffle.
Was das ist, wissen Sie.
Das war dieses, wenn ich zwei Hände habe, die so verschränke, ziehe
ich sie auseinander.
Das war das Perfect-Un-Shuffle.
Perfekt-Shuffle war dieses Zusammenstecken oder auch Perfekte Mischen
von zwei Kartensätzen.
Ich nehme beim Perfect-Un-Shuffle einfach alle Elemente von den
ungeraden Positionen, also Position 1, 3, 5, 7 usw.
nach links und alle an den geraden Positionen nach rechts.
Jetzt waren die beiden Folgen sortiert.
Die linke Folge und die rechte Folge.
Das heißt, wenn ich mir anschaue, was hier passiert, was ich hier
reinkriege, das ist jetzt mein Odd-Even-Merge von N.
Da habe ich ein Perfect-Un-Shuffle zunächst gemacht.
Dann habe ich hier zwei Folgen.
Diese ist natürlich sortiert und die ist auch sortiert.
Zwei Folgen der halben Länge, die jeweils aufsteigend sortiert sind,
weil sie ja nur an den entsprechenden Positionen sind.
Ich habe hier das zweite Element rausgezogen.
Und das gleiche ist hier natürlich auch der Fall.
Halb sortiert, halb sortiert.
Jetzt mache ich rekursiv das gleiche nochmal auf diesen zwei
Teilfolgen der Länge N viertel jetzt.
Und wende darauf Odd-Even-Merge an von N halbe.
Also, ich mache das ganze rekursiv weiter.
Ziehe immer so die an den geraden Positionen und ungeraden Positionen
auseinander.
Und wenn ich das bis zum Ende gemacht habe, dann habe ich dort
Elemente der Länge 1, beziehungsweise es reicht eigentlich zu geben es
auf Elemente der Länge 2.
Wenn ich hier zwei Elemente nur noch habe, die ich miteinander
vergleichen muss, wenn ich die verschmelzen muss, dann brauche ich nur
einmal, wenn ich zwei Elemente habe, die ich vergleichen muss
miteinander, X und Y.
So, dann kommt hier einmal ein Vergleich und das Minimum kommt daraus
und das Maximum kommt daraus.
Ein Vergleich von zwei Limiten.
Also das Odd-Even-Merge geht so weit runter, bis ich zwei Folgen der
Länge 1 verschmelzen muss.
Das geht mit einem Vergleich.
Und dann rekursiv krabbel ich das wieder nach oben.
Und dann habe ich also hier aus meinem rekursiven Aufruf, habe ich ja
rekursiv meine verschmelzenden Folgen rausbekommen.
Zwei Folgen der Länge in halbe, einmal die von den ungeraden
Positionen und die von den geraden Positionen.
Und jetzt kommt das Zusammensetzen.
Das mache ich so, dass ich jetzt einfach folgendes mache.
Das linkeste Element hier, das ist schon das Minimum.
Minimum.
Und das rechte ist das Maximum.
Wieso ist das der Fall?
Das linkeste Element, das da rauskommt, ist das kleinste Element der
ungeraden Positionen.
Das kleinste Element der ungeraden Positionen ist aber sicher das
Minimum von dem Element, das hier stand und dem, das da stand.
Das war das kleinste Element der beiden sortierten Folgen, die hier
reingegeben wurden.
Diese beiden, die sind hier reingegangen, in die linke Seite.
Das heißt, das minimale Element, wenn das sortiert ist am Ende, steht
garantiert hier als erstes.
Da brauche ich nichts mehr mit zu machen, das ist garantiert da
genauso symmetrisch.
Das Maximale steht garantiert hier ganz rechts.
Und bei den anderen bin ich mir nicht so sicher, wo die hingehören.
Da muss ich jeweils ein Element aus der Folge der ungeraden Elemente
vergleichen mit einem aus der geraden Folge.
Und zwar das zweite Element der ungeraden, das ist das zweite, mit dem
ersten Element der geraden, das dritte mit dem zweiten und so weiter.
Das sind hier diese Vergleiche.
Einen parallelen Schritt von Vergleichen, jeweils zwei Elemente.
Und Sie sehen, was ich hier mache, ist, dass sich jetzt das, was ich
vorher alles auseinandergezogen habe, einfach wieder zusammenschieben.
Über Perfect Shuffle.
Ja, ich habe hier die beiden links und rechts, die bleiben.
Wenn ich nur Perfect Shuffle mache, dann tut sich nichts und die
anderen werden gerade so schön vertauscht oder ineinander verschränkt.
Das heißt, ich mache hier einfach ein Perfect Shuffle auf den beiden
Folgen, die herausgekommen sind und habe dann gerade die nebeneinander
stehen, die verglichen werden müssen, mache diesen einen
Vergleichsschritt und die Behauptung ist, anschließend ist alles
sortiert.
Anschließend ist also hier das Ganze sortiert.
Das ist eine ziemlich starke Behauptung, dass ich durch diesen einen
Schritt von Vergleichen diese beiden sortierten Teilfolgen insgesamt
sortieren kann.
Das heißt, was ich behaupte ist, es gibt hier nur ganz wenig
Unsortiertheiten drin, die durch lokalen Vergleich ausgeglichen werden
können.
Das heißt, es ist schon relativ stark sortiert, bis auf so kleine
Vertauschungen, die ich hier jeweils noch machen muss an diesen paar
Positionen.
Und wir werden gleich sehen, wie man das beweisen kann, da kommt auch
ein ganz wesentliches Beweisprinzip zu sprechen.
Aber erst nochmal zum Zeitverhalten.
Wir haben uns also jetzt dieses Odd-Even-Merge angeguckt, das ist das,
was hier passiert.
Das ist das Odd-Even-Merge.
Wie ist der Aufwand dafür?
Da muss ich Odd-Even-Merge auf folgende Länge in halbe machen, bzw.
Odd-Even-Merge in halbe heißt, zwei Folgenlänge in Viertel werden
verschmelzen.
Und dann ist dieser eine Schritt, der dazukommt.
Das ist dieser eine Schritt.
Und OEM von zwei ist der gerade, also auf folgende Länge zwei bzw.
zwei folgende Länge eins verschmelzen.
Wie gesagt, das ist einfach das Comparative Exchange der beiden
Elemente.
Also im Vergleich, das ist das, was ich hier angedeutet habe.
Und wenn wir das jetzt auflösen, ist völlig klar, der Aufwand hier
oben...richtig, der Aufwand für das Odd-Even-Merge-Sort insgesamt ist
natürlich auch klar, ich muss Odd-Even-Merge-Sort machen, indem ich
Odd -Even-Merge-Sort für folgende Länge in halbe anwende.
Das mache ich beides parallel.
Deswegen muss ich die Zeit nur einmal hier hinschreiben.
Und ich brauche dann noch den Aufwand für das Odd-Even-Merge.
Und da der Aufwand für Odd-Even-Merge, wie man aus dieser Rekursion
hier sofort sieht, halb logarithmisch ist...
Ich habe ja auf jeder Ebene nur einen Schritt zu machen, Log-N
-Schichten, also das ist ganz einfach, Log-N, auch von der
Rekursionsleitung her sofort zu sehen.
Habe ich insgesamt den Aufwand Log-Quadrat.
Das heißt, hier habe ich ein Verfahren, mit dem ich in Log-Quadrat-N
sortieren kann.
Und das Wesentliche hier sind so viele Umordnungen der Elemente.
Und dann nochmal diese einfachen Vergleiche.
Sie haben eine Frage da hinten.
Keine Frage?
Das ist ja der rekursive Aufruf.
Hier oben kommt die Folge unsortiert rein, da ist es unsortiert.
Dann wird Odd-Even-Merge-Sort rekursiv angewandt.
Und auf folgende Linie in halbe.
Das hier ist eine völlig unsortierte Folge, die hier oben reingeht.
Unsortiert.
Und jetzt kommt dadurch, dass ich auf der ersten Hälfte Odd-Even-Merge
-Sort für in halbe anwende, das ist einfach der Merge-Sort-Ansatz.
Ich mache rekursiv Merge-Sort auf folgende Länge in halbe, dann kommt
eine Folge raus, der Länge in halbe, die sortiert ist.
Das ist das, was ich hier angedeutet habe.
Das ist Merge-Sort auf den Folgen der Länge in halbe.
Das ist der wesentliche Schritt, das mache ich natürlich auch parallel
für die beiden Teilfolgen.
Da die beide gleich groß sind, ist das gleicher Zeitaufwand.
Einmal nur Aufwand für folgende Länge in halbe, die zu sortieren.
Und dann kommt, habe ich also zwei sortierte Folgen, und die muss ich
verschmelzen.
Und den Aufwand wollte ich eben auf Log-N reduzieren, und das habe ich
hier geschafft mit diesem Odd-Even-Merge.
Das heißt, das ist der wesentliche Punkt, wie kann ich Odd-Even-Merge
tatsächlich in der Zeit reduzieren, in diesem Fall auf Zeit-Log-N.
Und das ist hier diese Andeutung, immer so mit Perfect-Unshuffle
-Shuffle.
Einmal ein Anfangsvergleich für dieses Corperates-Change, und dann
kommen diese weiteren Rekursive dazu, die hier in der letzten Zeile
angedeutet sind.
Wir sehen gleich nochmal, wenn man das auftrüselt, welche Vergleiche
insgesamt dabei entstehen.
Wir haben also Zeit-Log-N dabei rausbekommen, bei diesem Verfahren.
Das sieht man allein an diesem Bild.
Hier sieht man, wie die Rekursionsgleichung aufzuschreiben ist, und
ist damit schon mit der Zeitabschätzung fertig.
Nicht fertig sind wir damit, zu zeigen, dass das Ganze korrekt ist.
Also Zeitgewinn ist klar, der ist natürlich hier N durch Log-N, und
das hatte ich schon angedeutet, und damit ist die Effizienz in 1 durch
Log -N.
Das ist schon nicht schlecht.
Das könnte man auch hier sagen, man kann das Ganze ja reduzieren, man
kann es mal ein bisschen weniger vergleichen, und kann dann das Ganze
wieder ein bisschen beschleunigen.
Das ist auch wieder alles richtig, und kriegt dann noch ein besseres
Verfahren.
Aber da würde ich jetzt gar nicht weiter eingehen.
Ich will jetzt was sagen zur Korrektheit.
Und jetzt kommt die wesentliche, und eine ganz wesentliche Idee, wie
kann ich eigentlich Korrektheit zeigen, wenn ich etwas zeigen muss,
über alle Folgen, die irgendwie unsortiert da reinkommen, dass die
sortiert werden.
Ich habe diese Folgen von Vergleichen dort zu machen, dieses
Verfahren.
Schauen wir uns das an, ich mache das in einem ganz einfachen Fall.
Nur Nullen und Einsen.
Das wäre viel einfacher, als wenn ich hier irgendwelche beliebigen
Werte habe.
Dann schauen wir uns erst mal diesen ganz einfachen Fall an.
Zwei verschiedene Elemente, also nicht mehr die Annahme, die ich ganz
zu Anfang hatte, alle Elemente meiner Folge sind verschieden, sondern
hier sind nur zwei verschiedene Elemente drin, und die werden jetzt
hier eingegeben, in irgendeiner Anordnung.
Also hier kommt die Folge S in irgendeine Anordnung rein, und raus
kommt dann etwas, was hier jetzt in den grauen Feldern angedeutet ist,
da das 0,1-Folgen sind, kommt bei...
hier muss ich sagen, da habe ich nur einen Schritt weiter, also es ist
so, dass das, was hier angedeutet ist, ist praktisch die Ausgabe
unseres rekursiven Aufrufs von Merge Sort.
Auf folgende Länge in halbe.
Es kommen also zwei sortierte, folgende Länge in halbe raus, die jetzt
Eingabe sind für Odd-Even-Merge von N.
Man muss ja zeigen, dass dieses Odd-Even-Merge tatsächlich richtig
funktioniert und diese beiden Teilfolgen am Ende sortieren wird,
sodass alle Einsen rechts stehen und alle Nullen links.
Und zu Anfang war das natürlich hier oben bei diesen beiden Folgen
auch der Fall, hier bei der und auch bei der.
Alle Nullen stehen links, alle Einsen rechts.
Das ist die sortierte Reihenfolge.
Das ist sicherlich ein wesentlich einfacherer Fall, als wenn nicht
hier beliebige Werte stehen.
Und jetzt zähle ich einfach mal durch, wie viele Einsen dort stehen.
Und ich sage einfach die beiden Folgen, kann ich ja so
charakterisieren, ich habe hier entweder eine gerade oder eine
ungerade Anzahl von Einsen, angedeutet durch, das sind entweder 2 mal
a oder 2 mal a plus 1 Einsen, also gerade oder ungerade, oder hier 2
mal b oder 2 mal b plus 1 Einsen.
Also wenn ich eine ganz einfache Folge habe, ich könnte meinetwegen
haben hier 0 0 1 1 und ich könnte auch haben 0 1 1 1.
Dann hätte ich hier entsprechend eine gerade Anzahl von Einsen oder
eine ungerade Anzahl von Einsen.
So, jetzt wissen wir, wird hier einfach ein Perfekt-an-Shuffle
gemacht, es wird die Hälfte der Elemente überdraus gezogen.
Und die Elemente an den ungeraden Positionen waren dann nach links,
also an Position 1, 1, 2, 3, 4.
Dann sehen wir, wenn wir eine gerade Anzahl von Elementen haben, und
jedes zweite Element wird rausgezogen, also wird hier gerade die
Hälfte der Einsen aus der linken Folge genommen und die Hälfte der
Einsen aus der rechten Folge.
Die sind an den ungeraden Positionen.
Und an den geraden Positionen sind gerade die restlichen a und b
Einsen.
Wenn das Ganze jetzt ein, wenn a und b, a oder b, eine ungerade,
Quatsch, wenn die Anzahl der Einsen ungerade ist, in der linken oder
rechten Folge, dann steht hier noch so ein Plus Eins.
Das heißt, das ist dieser Fall.
Und diese zusätzliche Eins für eine ungerade Anzahl von Einsen, die
steht an einer geraden Position.
Und das gilt sowohl für die linke Folge als auch für die rechte Folge.
Das heißt, wenn wir eine ungerade Anzahl von Einsen haben, in der
linken Folge und in der rechten Folge oder auch nur in einer von
beiden, dann kommen diese zusätzlichen Einsen beide in die rechte
Folge rein.
Das heißt, wir haben in der linken Folge a plus b Elemente, die Eins
sind, und in der rechten Folge a plus b, eventuell plus zwei.
So, da wird jetzt rekursiv, das ist natürlich noch nicht so schön
sortiert, das, was hier angedeutet ist, das ist die Anordnung, dieses
hier ist die Anordnung, wenn das Ganze rauskommt aus dem rekursiven
Aufruf von odd even merge in halbe.
Das ist natürlich schon sortiert.
Und jetzt wird ein Perfect Shuffle gemacht, aus diesen sortierten
Folgen, der Länge in halbe jeweils.
Und es wird dieser eine Vergleich ausgeführt.
Das heißt, es werden jetzt, die Null bleibt natürlich da stehen, die
Eins da auch, es werden jetzt die ersten Elemente jeweils
rausgenommen, durch das Perfect Shuffle verglichen und irgendwann wird
eine Null aus der linken Folge auf eine Eins aus der rechten Folge
treffen.
Dann haben wir also hier solch einen Fall.
Wenn eine Null aus der linken Folge auf eine Eins aus der rechten
Folge trifft, da wird gar nichts vertauscht, das bleibt eigentlich
auch so stehen.
Hätte man gar nicht vergleichen müssen.
Der einzige Fall, wo etwas passieren muss, ist, dass eine Eins links
steht und eine Null rechts.
Dann muss sich wirklich vertauschen.
So, und jetzt, wenn ich ihn vertauscht habe, stehen die also in der
richtigen Reihenfolge.
Und jetzt ist das Wesentliche, dass rechts von dieser Position
angenommen wird, da stehen nur noch Einsen.
Das heißt, da kommen aus der linken und aus der rechten Hälfte nur
noch Einsen.
Und wenn da nur noch Einsen kommen, dann reicht es ja, dass ich diese
eine Eins hier um eine Position nach rechts verschoben habe, weil
rechts davon keine Nullen mehr stehen.
Das sehen wir uns gleich nochmal an, dass das tatsächlich so
ausreicht.
Wenn nämlich rechts noch eine Null wäre, dann müsste ich ja noch einen
Vergleich machen oder noch eine Vertauschung machen.
Das passiert hier aber nicht, ist die Behauptung.
Das sehen wir gleich auf der nächsten Folie.
Auf dieser Folie sehen wir das schon.
Die möglichen Fälle sind hier angedeutet.
Wenn wir gleich viele Einsen haben, A plus B und A plus B links und
rechts.
Und wir vergleichen ja immer Li und Ri-1.
Li war die linke Folge, linke Position, mit der rechten Folge, i-1
Position.
Dann heißt das, wir vergleichen hier Li und Ri-1.
Diese beiden werden verglichen.
Die beiden werden verglichen.
Und die beiden werden verglichen.
Ja, es sind gleich viele.
Also an der Position i steht die erste Eins, nehmen wir hier an.
Und dann ist an der Position Ri-1 noch eine Null.
Aber Ri ist 1, Li plus 1 ist sowieso 1.
Das heißt, hier haben wir gleich viele Einsen in beiden Folgen.
Dann wird genau das gemacht, die beiden müssen vertauscht werden.
Wenn wir eine Eins mehr haben, da die Einsen nur rechts auftauchen,
ist die extra Eins an der Position, wo vorher eine Null war.
Dann ist also gar keine Vertauschung mehr erforderlich.
Das ist schon richtig, aufgrund dieses Perfektschaffens.
Und wenn wir zwei zusätzliche Einsen haben, dann ist die zusätzliche
Eins an dieser Position.
Und hier wurde zwar verglichen, aber der Vergleich ist überflüssig.
Da wird gar nichts vertauscht.
Das heißt, die einzige Situation, wo überhaupt etwas passiert, ist
diese hier.
Dass wir gleich viele Einsen haben, links und rechts.
Und ich muss dann an einer Position noch vertauschen.
Weil wir an einer Position nicht in der richtigen Reihenfolge sind,
nach dem Perfektschaffens.
Ich weiß natürlich nicht, an welcher Position das der Fall sein würde.
Deswegen muss ich für jede mögliche Situation vorbereitet sein und das
so machen.
Ich bräuchte eigentlich nur einen Vergleich bei den Null-Eins-Folgen.
Also für Null-Eins-Folgen ist das Ganze ganz einfach.
Da kann man sich sofort überlegen, für Null-Eins-Folgen habe ich dafür
gesorgt, dass an jeder potenziellen Position, wo diese erforderliche
Vertauschung der zwei Elemente vorkommt, ein Vergleich tatsächlich
auch durchgeführt wird.
Und jetzt ist die Behauptung, gut, erst mal, dass in jedem Fall die
Ausgabe sortiert ist, ist klar, das ist jetzt hier die Behauptung, und
die starke Behauptung ist, es reicht, solche Folgen zu betrachten.
Also auch wenn ich beliebige Elemente habe, irgendwelche Zahlen da
drin, ich weiß gar nichts über die Elemente, nur, dass sie
vergleichbar sind, es reicht, die Erkenntnis zu haben über Null-Eins
-Folgen, um sagen zu können, es wird an jede beliebige Folge sortiert.
Und es ist völlig klar, dass der Aufwand, der Beweisaufwand für Null
-Eins -Folgen, deutlich kleiner ist, als der für beliebige Folgen.
Wenn Sie hier für beliebige Folgen argumentieren wollen, wünsche ich
Ihnen viel Spaß.
Wenn Sie zeigen wollen, direkt, dass jede beliebige eingegebene Folge
durch dieses Verfahren sortiert wird, das ist ein sehr, sehr
aufwendiger, formaler Beweis.
Das hier für Null-Eins-Folgen, wie Sie gesehen haben, ist sehr
einfach.
Geht sehr schnell.
Es ist nur die Frage, was ist denn das Null-Eins-Prinzip?
Das ist das, was ich Ihnen gerade angedeutet habe.
Wenn also ein nur auf Vergleichen basierender Algorithmus alle Folgen
von Nullen und Einsen sortiert, so sortiert er auch jede beliebige
Folge von Elementen einer geordneten Menge.
Das Wesentliche ist natürlich, dass der nur auf Vergleichen basieren
darf.
Das heißt, ich nutze nichts weiter aus über die Zahlen oder die
Elemente, die sortiert werden.
Ich nutze nur aus, dass sie vergleichbar sind, dass ich sie in ihrer
Größe vergleichen kann und in die richtigen Reihenfolge bringen kann.
Wenn ich ausnutzen würde, dass das Nullen und Einsen sind, wäre das
nicht zulässig.
So, das ist das Null-Eins-Prinzip und jetzt die Frage, wie kann man
das beweisen?
Wir behaupten einfach, dass das nicht stimmt.
Wir behaupten, es gibt eine Folge, die durch A nicht sortiert wird.
Also wir nehmen irgendeinen Algorithmus A, beliebigen Algorithmus A
her und wir behaupten, bei diesem Algorithmus gibt es eine Folge, die
von A nicht sortiert wird.
Das heißt, wir haben hier unsere Folge S, irgendeine Folge und wir
haben den Algorithmus A und der liefert dann daraus eine neue Folge.
Und in dieser Folge sagen wir, die ist nicht aufsteigend sortiert.
Was heißt denn das, dass diese Folge nicht aufsteigend sortiert ist?
Das wäre sowas ähnliches wie, könnte ich hier hinschreiben, A von S
ist nicht aufsteigend sortiert.
Wenn ich mal annehme, die sollen so aufsteigend sortiert sein, also
das ist ja hier nicht der Fall, hier soll es also aufsteigend sortiert
sein, da noch nicht.
Links ist ja eine unsortierte Folge.
Das, was ich jetzt zeigen möchte ist, wenn ich eine solche Folge habe,
die nicht sortiert wird, dann kann ich eine Null-Eins-Folge
konstruieren, die auch nicht sortiert wird.
Und dazu muss ich mir jetzt überlegen, wie man das machen kann.
Ich gucke mir einfach an, was heißt denn das, diese Folge ist nicht
sortiert.
Das heißt doch, es gibt hier irgendein Element, ja, das ist das
Element S-I, also ich habe hier ein Element, dieses Element hier nenne
ich jetzt mal S-I, das steht in der falschen Position.
Das heißt, es gibt ein, das sei das kleinste Element, das Element mit
dem kleinsten Index, hier in S, das entsprechend, also das gilt, dass
das hier ist und es gibt hier unten, und dieses Element ist jetzt
kleiner als das Element, das davor steht.
Dann wäre es ja nicht richtig sortiert.
Ja, das ist kleiner als das Element, das oben drüber steht.
Das heißt, es wäre unsortiert.
Und jetzt habe ich also das Element S-I identifiziert.
Das heißt, es gibt ein S-J, das größer ist, das ist hier an diese
Position gewandert, das ist das S-J und es ist eben das S-I kleiner
als S-J.
Wenn S-I kleiner als S-J ist und das S-J landete hier an dieser
Position direkt da oben drüber, S-I da drunter, dann ist das hier
nicht sortiert.
Und es taucht eben, das S-J taucht in A von S vor S-I auf.
So.
Und jetzt weiß ich ja, S-I und S-J, die tauchen hier irgendwo auf, I
und J.
Die sind dort irgendwo, die sind ja in irgendeiner Position.
Das habe ich gesagt, das ist hier, S-I ist das kleinste Element von S,
das an der falschen Position steht, genau.
So, das wandert in die falsche Position.
Jetzt sorge ich einfach dafür, dass alle Elemente, die kleiner gleich
meinem S-I sind, also alle Elemente der Folge, die kleiner gleich
diesem S-I sind, dass die auf Null gesetzt werden.
Das heißt, insbesondere das S-I hier wird Null.
Und wenn die Elemente größer als S-I sind, dann werden sie auf Eins
gesetzt.
Das heißt, das S-J wird auf jeden Fall Eins.
Und das heißt, wenn ich mir jetzt hier eine...
wenn ich mir anschaue, was ich hier haben möchte, ist doch Folgendes.
Alle Elemente, die kleiner gleich S-I sind, sind auf Null gesetzt
worden.
Die sitzen also dann hier im Prinzip alle oben drüben.
Aber wir haben hier die...
Das sieht jetzt ganz schrecklich aus hier.
Ich mache das mal hier weg.
Ich brauche eine lange Folge, die da rauskommen soll.
Hier war das Element S-I.
Da oben drüber ist das Element S-J.
Das habe ich gesagt in der Folge, die ich konstruiere.
Da soll das auf jeden Fall Null sein.
Und das auf jeden Fall Eins.
Und alle Elemente, die kleiner gleich S-I sind, sind Null gesetzt.
Ja, die sitzen aber in der Ausgangsfolge, sitzen die Elemente kleiner
gleich S-I, ja alle hier oben drüber.
Wenn ein größeres Element da sitzen würde, dann wäre schon vorher
solch eine Ungleichheit entstanden.
Das wäre dann also nicht der richtige Vergleich gewesen.
Das heißt, ich habe jetzt hier oben drüber Nullen stehen.
Vielleicht noch ein paar Einsen, aber irgendwann, das Element ist ja
das, was hier die erste falsche Position ist.
Es könnte sein, dass hier noch ein paar Einsen sind.
Und da oben tauchen dann Nullen auf.
Auf jeden Fall habe ich hier diese eine Position, wo es falsch ist.
Und alle Elemente, die größer sind als das S-I, die sind auf Eins
gesetzt.
Die sind garantiert alle hier unten drunter.
So.
Und jetzt schaue ich mir an, was passiert.
Wenn ich jetzt auf einer Folge von Nullen und Einsen, die so definiert
ist, also auf dieser Folge von Nullen und Einsen, meinen Algorithmus A
anwende, dann werden die gleichen Vergleiche durchgeführt wie vorher
auf diesen einzelnen Elementen.
Ich nutze ja nicht aus welcher Wert das steht, sondern ich nutze nur
aus, dass ich Größenvergleiche durchführen kann.
Das heißt, alle Vergleiche von Elementen S-K-Strich und S-L-Strich,
das sind also die Nullen- und Einselemente, bei denen S-K
kleinergleich S-I und S-J kleinergleich S-L, die haben die gleiche
Wirkung, weil nämlich das S-K-Strich dann eine Null ist und das S-L
-Strich eine Eins.
Die haben die gleiche Wirkung wie bei Ausführungen auf S.
0,1 wird ja nicht weiter, da passiert gar nichts.
Da alle anderen Vergleiche keine Ordnungsrelation bezüglich S-I und S
-J tangieren,
werden in A von S-Strich S-I-Strich und S-J-Strich an den gleichen
Positionen stehen wie vorher.
Das heißt, an den Positionen dieser Elemente ändert sich gar nichts.
Und ich habe eine Folge konstruiert, die hier vorne eingeben konnte,
die Folge S-Strich, die nur aus Nullen und Einsen besteht, die durch A
nicht sortiert wird.
Wir kommen dort garantiert wieder an der gleichen Stelle wie vorher
eine Unsortiertheit rein.
Und das heißt, dass ich aus der Tatsache, dass es eine Folge gibt, die
nicht durch A sortiert wird, eine 0,1-Folge konstruieren kann, die
dann ebenfalls nicht sortiert wird.
Und damit habe ich gezeigt, dass durch Kontrapositionen ein
Algorithmus, der jede 0,1-Folge sortiert, auch jede beliebige andere
sortiert.
Also damit bin ich dann fertig.
Das ist halt hier das, was wir zeigen wollten.
Es reicht, 0,1-Folgen zu betrachten.
Und das ist ein ganz wesentliches Beweisinstrument, um sich klar
darüber zu werden, welche Eigenschaften ein Algorithmus hat und zu
zeigen, Algorithmus sortiert oder sortiert nicht.
Das werden wir jetzt gleich weiterhin noch intensiv ausnutzen.
Sie können sich gerne mal überlegen, wie stark dadurch der Aufwand
reduziert wird, wenn Sie ansonsten für jede Folge etwas sagen müssten,
jetzt nur noch für die 0,1-Folgen, wie stark das den Aufwand insgesamt
reduziert.
Wenn Sie alle Folgen durchprobieren müssten, wie stark das den Aufwand
reduziert, wenn Sie nur noch alle 0,1-Folgen anschauen müssen.
Also, und das ist auch so andersrum, wenn Sie zeigen wollen, wenn Sie
zeigen können, ein Algorithmus sortiert nicht, es reicht eben, eine
einzige 0,1-Folge anzugeben, die nicht sortiert und so eine zu finden,
ist wesentlich einfacher, als eine beliebige Folge zu finden, die
nicht sortiert wird.
So, jetzt schauen wir uns nochmal an, hatte ich Ihnen versprochen, wie
eigentlich dieses Netz aussieht, wenn wir Odd-Even-Merge-Sort
anwenden.
Wie sich das auswirkt auf die Vergleiche, die durchgeführt werden.
Ja, wir hatten gesagt, wir machen Odd-Even-Merge.
Das ist also hier ein Odd-Even-Merge auf diesen Folgen der Länge in
halb.
In diesem Fall haben wir zwei Folgen der Länge 8, die verschmolzen
werden sollen, durch Odd-Even-Merge.
Und wir hatten gesehen, zunächst einmal macht man immer wieder so
einen Perfect-On-Shuffle, bis ich folgende Länge 1 habe.
Und dann kommt das Shuffle mit diesen Vergleichen, die hier stehen.
Also, wenn ich ganz unten angekommen bin, dann werden jeweils zwei
Elemente verglichen.
Und welche sind denn das, die dann zusammenkommen?
Wie Sie hier sehen, wird dann das erste verglichen mit dem neunten.
Das zweite mit dem zehnten.
Also, der Abstand ist gerade immer in halbe für die Elemente.
Weil ich die gerade so zusammengebracht habe, das ständige Ausführen
von Perfect-On-Shuffle, habe ich genau jeweils die beiden
zusammengebracht.
Die werden jetzt alle parallel miteinander verglichen.
Das ist also das, was am Ende der Rekursion passiert für folgende
Länge 1.
Die verschmolzen werden zu folgende Länge 2.
Jetzt habe ich also bei... ich habe hier folgende Länge 2.
Ich habe also jetzt acht folgende Länge 2.
Und die werden jetzt verschmolzen zu folgende Länge 4.
Wenn ich folgende Länge 2 habe, die verschmolzen werden zu folgende
Länge 4.
Dann habe ich also links und rechts jeweils ein Element, an dem nichts
passiert.
Und dann bleiben noch zwei Elemente in der Mitte übrig und die werden
verglichen.
Das sind genau diese Vergleiche, die Sie hier sehen.
Das heißt, da haben wir die Situation, dass wir im Prinzip so etwas
machen.
Hier wird ein Vergleich gemacht, da nicht.
Da nicht, da, da diese werden.
Und das ist vielleicht auch wieder etwas anders.
Was wird hier gemacht?
Hier kommen die Sortiere raus.
Das kommt von da.
Das geht im Prinzip...
Ne, die werden einfach so...
Da wird gar nichts drüber geschoben.
Im einfachen Fall sieht das so aus.
Das sind meine beiden Elemente aus der kleinen...
Zwei Folgen der Länge 2.
Das zweite Element wird mit dem ersten der zweiten Folge verglichen.
War schon erst richtig gemalt.
Die werden verglichen und das ist dann das, was dabei rauskommt.
Das ist genau das, was hier passiert, an dieser Stelle.
Diese vier Vergleiche sind gerade die vier Vergleiche, die wir
brauchen, um unsere Folgen der Länge... um jeweils zwei Folgen der
Länge in Halbe zu verschmelzen, zu Folgen der Länge in Viertel.
Und dann brauchen wir entsprechend Vergleiche, um Folgen der Länge in
Viertel zu verschmelzen, zu Folgen der Länge in Halbe.
Das passiert hier, an der Stelle.
Das sind jeweils drei Vergleiche, die gemacht werden müssen.
Und die tauchen... wir haben also insgesamt sechs in dieser Schicht.
Und anschließend werden zwei Folgen der Länge in Halbe verschmolzen zu
einer Folge der Länge in...
Und das sind genau die Vergleiche, die wir hier nochmal gesehen
hatten.
Genau die hier am Ende, die werden hier in dieser Schicht ausgeführt.
Also das sind der Reihe nach die Vergleiche.
Ist vielleicht ein bisschen lang gewesen, diese Erklärung.
Aber es ist immer ganz hilfreich zu sehen, was passiert eigentlich,
wenn ich so ein rekursives Verfahren anwende.
Das, was hier drinsteckt, das ist ja alles versteckt in unserem...
Dieser ganze Bereich hier ist ja versteckt in unserem Kasten, der hier
oben steht.
Das ist genau das, was hier drinsteckt.
Dieses... das passiert da.
Und hier sehen wir nur diese eine Zeile, diese eine Zeile hier unten,
das ist die Zeile.
Und der Rest ist eben... der Rest ist halt gerade die... das, was
rekursiv passiert.
So.
Ein solches Vergleichenetz, Sie sehen, das sieht recht relativ
systematisch aus.
Ist ja klar, durch rekursiven Abstieg kann nur etwas sehr Reguläres,
Symmetrisches entstehen.
Das sind die Vergleiche.
Und Sie können sich auch sofort überlegen, das könnte man natürlich
genauso auch in Hardware implementieren.
Wenn ich das aber in Hardware implementiere, dann habe ich natürlich
nicht einen solchen langen Vergleich.
Die Vergleichselemente, die sehen alle, das ist halt mein Vergleich,
mein Comparison Exchange.
Und da müssen die Elemente von irgendwo herkommen und irgendwo
hinwandern.
Das heißt, da habe ich tatsächlich solche langen Leitungen.
Wenn ich das in Hardware mache.
Dann haben wir eine Leitung der Länge Größenordnung N, einmal quer
rüber oder halb rüber über Chip.
Und ich habe sofort Probleme mit meinen Taktseiten.
Das heißt, hier habe ich sehr lange Leitungen und nicht so eine schöne
reguläre Struktur wie bei diesem Transposition Sort.
Aber ich habe ein deutlich schnelleres Verfahren, was die Anzahl der
Schritte handelt.
Jetzt zeige ich Ihnen noch ein anderes Verfahren, bei dem wir etwas
anders sortieren.
Wir schauen uns noch einfachere Folgen an.
Und zwar besondere, ich erkläre das jetzt über 01-Folgen, aber im
Prinzip rede ich über beliebige Folgen, nämlich über bitonische
Folgen.
Das heißt, ich möchte bitonische Folgen sortieren.
Was ist eine bitonische Folge?
Wir kennen monotone Folgen.
Wir kennen monoton aufsteigende, monoton absteigende Folgen.
Und eine bitonische Folge ist sowohl monoton absteigend als auch
monoton aufsteigend.
Aber eben verschoben.
Hier haben wir eine zyklische Verschiebung einer auf- oder
absteigenden Folge.
Und wenn Sie sich vorstellen, Sie haben eine solche aufsteigende
Folge, verschieben die zyklisch.
Na ja, dann haben Sie auf einmal so etwas, jetzt sagen wir dieses
Absteigen, das kann doch etwas länger gehen.
Sie haben dann auf einmal hier eine solche Anordnung, aufsteigend,
absteigend.
Und das ist eine bitonische Folge.
Über einen gewissen Zeitraum ist ein gewisser Teil rein aufsteigend
und dahinter ist es nur absteigend.
Das ist an irgendeiner Position so.
Wenn das Ganze nach rechts geht, kann es sein, dass wir hier nur
aufsteigend haben.
Aber es kann auch andersrum sein.
Das heißt, wenn wir das als 0-1-Folge hinschreiben, dann haben wir
zunächst mal kleine Elemente, dann große und dann wieder kleine.
Wir können also eine bitonische Folge mit 0-1-Folgen charakterisieren,
indem wir das so hinschreiben als 0 hoch A, 1 hoch B, 0 hoch C.
Also zunächst mal A nullen, dann B einzeln und dann C nullen.
Oder andersrum, es kann auch sein, dass das so aussieht, wie hier
angedeutet, dass wir zunächst mal einige Einsen stehen haben, dann
einige Nullen, dann einige Einsen.
Und es kann auch sein, dass wir zunächst mal etwas absteigendes haben,
dann etwas aufsteigendes und dann etwas absteigendes.
Das wäre ja auch eine Verschiebung einer auf- und absteigenden Folge.
Auch das ist noch eine bitonische Folge.
So, solche Folgen, die hier angedeutet sind, in grün und in blau, kann
ich eben als 0-1-Folgen charakterisieren als diese beiden
verschiedenen Fälle.
Und jetzt schauen wir uns ein Vergleichernetz an, das ein bisschen
anders aussieht als das, was wir vorher hatten.
Schauen wir nochmal auf die vorherige Folie, das war diese hier.
Da sehen Sie, hatten wir hier unten, wir hatten oben die gleichen
Vergleiche.
Und dann unten drunter waren hier aber deutlich, das war nicht so ganz
symmetrisch.
Auf der Folie, die wir hier haben, oder auf dem Vergleichennetz, das
wir hier haben, sieht das Ganze sehr nach den beiden Punkten aus.
Hier haben wir nämlich die gleiche Situation, das ist praktisch die
erste Situation, die wir vorher auch hatten, bei dem odd-even merge.
Und jetzt haben wir hier im Prinzip das Gleiche nochmal, zweimal
hingeschrieben.
Da nochmal, jetzt aber wieder etwas kleiner.
Und hier haben wir nochmal einen Vergleich jeweils von
nebeneinanderliegenden Netzen.
Aber Sie sehen, die Vergleiche sind leicht anders, aber ein sehr
systematisch einfach aufgebautes Netz.
Jetzt ist die Frage, was passiert, wenn wir hier eine betonische Folge
reinschieben.
Das ist eine betonische Folge, zum Beispiel beginnend mit Nullen, dann
Einsen, dann Nullen.
Wenn das da durchläuft, durch die erste Folge, die ersten Vergleiche,
also ein Vergleichsschritt, jeweils die Elemente mit Abstand in Halbe
werden verglichen.
Dann stellen Sie fest, anschließend sind in der linken Seite nur
Nullen, in der rechten Seite Einsen und Nullen.
Woran liegt das?
Naja, wenn hier irgendwo Null und Eins verglichen, also wenn Null und
Null verglichen wird, passiert ja gar nichts.
Das bleibt stehen.
Wenn hier Null und Eins verglichen wird, dann bleibt die Eins rechts
und die Null geht nach links.
Also wenn Null und Eins verglichen wird, geht die Eins immer nach
rechts.
Das heißt, die Einsen, die hier auf dieser Hälfte standen, in diesem
Bereich, die wandern alle nach rechts.
Es sei denn, rechts stand an der Position auch eine Eins.
Und die Nullen, die hier stehen, in der rechten Seite, die wandern
nach links, sofern dort links eine Eins gestanden hat.
Und das heißt, wir haben dann auf einmal hier eine Hälfte, eine Folge,
das sind nur Nullen.
Und hier sind Einsen und Nullen noch nicht sortiert.
Was Sie hier sehen, das sind beides Folgen, die im Prinzip mitonische
Folgen sind.
Die linke ist schon vollständig sortiert, das sind also nur Nullen.
Und rechts haben wir Einsen, dann eine Null und dann wieder Einsen.
Jetzt gehen die durch die nächste Stufe durch.
Links tut sich natürlich nichts mehr.
Und rechts sehen Sie, haben wir jetzt, naja, im Prinzip diese beiden
Folgen.
Ich sagte ja, die Einsen wandern nach rechts, die Nullen nach links.
Wenn rechts noch Nullen sind, rechts waren gar keine Nullen mehr.
Das heißt, wir können keine Nullen nach links wandern.
Wir haben also jetzt hier zwei Folgen.
Die linke ist bitonisch, beginnt mit Einsen, anschließend kommen
Nullen und danach kommen keine Einsen mehr.
1 von 0.
Und dann geht das weiter.
Das hier, diese Folge, wird mit diesen beiden Vergleichen aufgeteilt
in zwei Folgen.
Das ist hier eine bitonische Folge, das ist auch eine bitonische
Folge.
Und anschließend werden die beiden hier verglichen, dann haben wir
hier zwei Folgen.
Und das sind auch wieder zwei triviale bitonische Folgen.
Und das, worauf ich hier hinweisen wollte bei dieser Erklärung, ist,
dass wir nach jedem Schritt jeweils die Folgen aufgeteilt haben in
zwei Teilfolgen, die jeweils bitonische Folgen sind.
Und zwar so, dass die linke Folge insgesamt kleiner ist als die rechte
Folge.
Und wenn das so ist, dann ist also dadurch das ganze Sortieren im
Prinzip schon gemacht worden.
Das heißt, wir haben, da die linke Folge jeweils kleiner gleich der
rechten Folge ist, ist am Ende die Folge insgesamt sortiert, weil die
Argumentation für das, was hier steht, ja gerade das gleiche Argument
ist, wie das, was wir vorher gemacht haben.
Das heißt, rechts daneben ist schon richtig sortiert, das heißt, also
ist schon in richtiger Anordnung, linke Folge kleiner als rechte
Folge, wir haben es insgesamt sortiert.
Das heißt, durch dieses Netz von Vergleichen wird eine bitonische
Folge sortiert.
Inside Log N.
Log N Schritte.
Ich kann also eine bitonische Folge mit Log N Schritten parallel
sortieren.
Was hilft mir das jetzt?
Warum will ich bitonische Folgen sortieren?
Das Interessante ist, also hier steht nochmal, das war gar nicht
bewiesen, wir müssen auch schnell beweisen, dass es wirklich richtig
war, was wir da gemacht haben.
Was passiert denn, wenn wir jetzt diese Vergleiche, die wir hier
angeschaut haben, wir werden immer die Elemente mit Abstand in Halbe
verglichen.
Also, wenn wir das uns hier anschauen, wir haben unsere Folge
praktisch aufgeteilt in diese zwei Hälften und wir vergleichen immer
das Element, das hier steht, mit dem Element Abstand in Halbe dazu.
Halbe Folgenlänge.
Wenn wir also eine Folge haben der Art Null, wo es mit Nullen losgeht,
dann kommen Einsen und dann kommen Nullen hinterher.
Hier sind also Nullen, da sind Einsen und da sind wieder Nullen.
Dann ist das, was wir in diesem Vergleichsschritt machen, praktisch,
dass wir immer übereinander folgende Elemente vergleichen.
Hier werden praktisch jeweils lokale Vergleiche gemacht.
Und dann wandern natürlich dadurch die Einsen nach unten und die
Nullen nach oben.
Das heißt, wenn wir den Schritt gemacht haben, einmal, dann haben wir
diese Situation, dass die Einsen sind natürlich hier geblieben, da ist
nichts verschoben worden.
Und der Rest steht jetzt so da, die Nullen sind nach oben gewandert.
Das heißt, wir haben aus der Situation, die hier angedeutet ist, jetzt
eine Folge, die ist bitonisch, beginnt mit Nullen, hat dann ein paar
Einsen, hat dann Nullen hinterher.
Und wir haben hier unten drunter auch eine Folge, das sind alles
Einsen.
Eine andere Situation wäre gewesen, wir haben erst Einsen, dann
Nullen, dann Einsen.
Dann würden bei diesen Vergleichen mit Abstand in Halbe, die hier sehr
lokal aussehen, auch wieder die Einsen nach unten wandern, also
rechts, und die Nullen nach oben.
Dann haben wir die gleiche Situation, wir haben hier wieder diese
beiden Folgen, die jeweils bitonisch sind.
Andere Situation wäre, wir haben hier weniger Einsen, und wir haben
hier einen Bereich, da stehen nur Nullen übereinander.
Na ja, dann wird bei dem Ergebnis hier oben eine Folge stehen, wo nur
Nullen sind, und unten drunter beginnt es mit Einsen, dann haben wir
Nullen, dann haben wir Einsen.
Und das gleiche passiert hier, wenn wir weniger Einsen haben, dann
haben wir hier eben auch die Lücke, und wir bekommen dann hier eine
solche Folge.
Und dann gibt es noch den Punkt, dass wir vielleicht deutlich mehr
Nullen haben, und dann würden alle Einsen, die hier stehen, nach unten
wandern, und wir hätten im Prinzip eine ähnliche Situation.
Wir hätten unten eine Folge, wo noch ein paar Einsen drinstehen, oben
nur Nullen.
Und hier, wenn das so wäre, bei der Situation, hätten wir eben die
Nullen alle nach oben geschoben, bei diesen Vergleichen, wir hätten
hier die Folge, zwei betonische Folgen, die erste ist kleiner gleich
der untere.
Das heißt, wir haben jeweils die Eigenschaften hier nachgewiesen für
die 0,1-Folgen, dass die untere Folge, das heißt die rechte Folge,
größer gleich der linken Folge ist, und wir haben jeweils betonische
Folgen da drin.
Jetzt kommt noch ganz kurz eine Folie, auf der ich Ihnen zeige, warum
das interessant ist für Sortieren.
Wenn ich Merge Sort anwende, dann ist der wesentliche Schritt das
Verschmelzen von zwei Folgen, die sortiert sind.
Also zwei so aufsteigend sortierte Folgen.
Ob ich aber die beiden Folgen so aufsteigend nebeneinander male, oder
wenn ich diese hier andersrum anordne, dann würde ich daraus so etwas
machen.
Ich ordne die einfach andersrum an.
Und dieses andersrum anordnen der zweiten Folge, habe ich hier einfach
in die Vergleiche reingesteckt.
Das andersrum anordnen, das hier, ist ausgedrückt dadurch, dass ich
einfach die Abstände zwischen den zu vergleichenden Elementen hier
einfach anders eingezeichnet habe.
Das heißt, dieser erste Schritt ändert sich, und dadurch ist auf
einmal die Eingabefolge eine betonische Folge.
Und ich kann also bei Tonic Sort anwenden, um den
Verschmelzungsvorgang der beiden Folgen hinzubekommen.
Das heißt, ich habe hier am Ende eine aufsteigend sortierte Folge,
habe also das Mergen gemacht durch das Sortieren einer betonischen
Folge.
Das geht in SideLogN.
Das heißt, ich habe hier ein alternatives Vergleichernetz, um das
Verschmelzen zu machen in SideLogN.
Ich habe etwas mehr Vergleicher, aber diese Struktur ist für die
Realisierung deutlich einfacher zu machen.
Sie haben immer die gleiche Struktur.
Ja, immer die gleiche Struktur, Elemente, deren Abstand inhalte werden
miteinander verglichen.
Das wird halt immer kleiner, der Wert, also die Abstände.
Aber es ist ein sehr systematischer Ansatz.
Und damit haben wir dann, also hier sieht man jetzt, also hier das,
was da gemacht wird.
Es entsteht dann offensichtlich insgesamt für das Sortieren insgesamt,
also Laufzeit von...
bei Tonic Merge Sort ist dann Aufwand Block Quadrat N.
Und damit sind wir mit dem Sortieren von solchen Folgen erstmal durch.
Nächstes Mal zeige ich Ihnen, wie man Elemente in einem
zweidimensionalen Prozessornetz sortieren kann.
Da kommen wir auch noch auf eine ganze Reihe interessanter Aspekte,
die man da beachten kann.
Vielen Dank für die Aufmerksamkeit.