So, der übliche Effekt.
Das Bild ist verschwunden.
Sehr seltsam.
Ich begrüße Sie zu einer weiteren Fortsetzung von effizienten
Algorithmen.
Wir haben uns in der letzten Woche mit Suchen und Sortieren
beschäftigt.
Wir haben uns einige Dinge angeschaut.
Erstmal das Problem angeschaut.
Ach, vielleicht sollte ich auf eine Sache noch hinweisen.
Es ist ab dieser Woche, ab heute, die Anmeldung für die Prüfungen
geöffnet.
Und das heißt, wer an der Prüfung teilnehmen möchte, sollte sich am
Terminal anmelden.
Dann ist noch ein bisschen Zeit.
Das läuft ziemlich lange, dieses Semester.
Beginnt auch relativ früh in diesem Semester, die Anmeldeperiode.
Aber Sie können sich jetzt jederzeit anmelden.
Und bei der geringen Zahl von Hörern.
Ich sehe natürlich in der Vorlesung sowieso nur eine Teilmenge der
Hörer.
Aber ich gehe davon aus, dass es nicht mehr sind, als diejenigen, die
in den Übungen teilnehmen.
Das sind dann zu Größenordnung 6, 6, 7 vielleicht.
Bei der Zahl von Hörern bin ich also bereit, das als mündliche Prüfung
zu machen.
Die mündlichen Prüfungen würden dann in der Woche nach Vorlesungsende
auch stattfinden.
In etwa zeitgleich mit den schriftlichen Prüfungen.
Also noch vor dem, wahrscheinlich am 3.
August.
Also der 3.
wäre Donnerstag.
Ich werde mich bemühen, das dann zu machen.
Oder am Montag.
Das können wir dann noch vereinbaren.
Also entweder am Montag der Woche, denn da haben Sie garantiert keine
Prüfungen.
Sie haben vielleicht andere schriftliche Prüfungen.
Nach dem 4.
August wäre es dann erst wieder im September irgendwann möglich, weil
da zwischen die Urlaubszeit liegt und Tagungen und ähnliches.
Also melden Sie sich an zur Prüfung und dann sehen wir, wie viele das
sind und wann wir den Termin machen können.
Und wenn Sie spezielle Wünsche bezüglich des Prüfungstermins haben,
also wenn das in der Woche, in der üblichen Prüfungswoche bei uns, bei
irgendjemandem nicht möglich ist, dann sollten Sie mich rechtzeitig
per E-Mail informieren.
Das ist das Sinnvollste.
So, letztes Mal haben wir uns mit Suchen und Sortieren beschäftigt,
haben dort zunächst mal das Problemus angeschaut, verschiedenste
Operationen auf Komponenten von Listen.
Wesentlich ist eine Liste, bei der man Größenvergleiche machen kann.
Wir hatten also hier eine Reihe solcher Probleme.
Suchen, Sortieren, Verschmelzen von Listen, Einfügen, Löschen,
Extrahieren eines Elements aus einer Liste.
Das wäre das Suchen in irgendwelchen Verzeichnissen.
Und mit einigen dieser Operationen beschäftigen wir uns halt, wenn man
so einige Operationen zusammennimmt.
In SearchDelete waren das gerade die sogenannten Lexikon-Operationen.
Und was wir uns anschauen, ist im Wesentlichen zunächst mal das
Sortieren und später dann das Suchen.
Und die Operationen, die wir betrachten müssen, sind halt hier die
Vergleiche, wie wir schon mehrfach jetzt betont haben.
Das Erste war dann ein Blick auf die Sortierverfahren, die den meisten
bekannt sind.
Das Einfachste war das Sortieren durch Auswahl.
Einen kurzen Blick darauf, wie viel Aufwand das eigentlich ist.
Und wir hatten dann festgestellt, dass man das parallel in konstanter
Zeit machen kann.
Wenn man die entsprechenden Annahmen macht, bezüglich des
Berechnungsmodells, mit gemeinsamem Schreiben, geht das halt mit drei
Schritten.
Und dann ist man fertig mit der Bestimmung des Minimums.
Und damit hätte man also das Minimum in konstanter Zeit bestimmt.
Na gut, das heißt noch nicht, dass man sortieren kann in konstanter
Zeit.
Da brauchen wir noch ein bisschen mehr.
Aber da kommen wir später auch nochmal zu.
Jetzt haben wir hier Sortieren durch Einfügen.
Auch ein bekanntes Verfahren mit quadratischem Aufwand.
Wir haben Bubble Sort angeschaut, noch ein Verfahren mit quadratischem
Aufwand und gesehen, dass man das in einer parallelen Variante als Odd
-Even Transposition Sort recht effizient auf einer linearen Liste oder
auf einem linearen Feld von Prozessoren implementieren kann.
Und dann geht es auch nicht besser vom Zeitverhalten her.
Das heißt, ein Verfahren, das sequenziell schlecht ist, kann parallel
durchaus bei einem geeigneten Rechnungsmodell eine sinnvolle Variante
sein.
Hat den Vorteil, dass es ein sehr einfaches Verfahren ist und nur mit
lokalen Operationen arbeitet.
Das war hier dieser Beweis über eine Visualisierung des Ablaufes.
Wir hatten Sortieren durch Teilen nochmal angeschaut.
QuickSort, auch allen bekannt mit der Analyse des Zeitverhaltens,
insbesondere des mittleren Verhaltens, NlogN.
Die Schwachstelle ist dieses unvorhersehbare Aufteilen, was im
schlechtesten Fall zu quadratischem Verhalten führt.
Wir hatten dann MergeSort als Alternative angeschaut, wo wir ein
striktes Aufteilen haben, striktes Divide & Conquer mit der
Möglichkeit, in NlogN-Verschmelzungsstufen das Problem des Sortierens
zu lösen.
In jeder Ebene hat man linearen Aufwand und dadurch das Verhalten
NlogN.
Und wenn man jetzt daran geht, das Ganze parallel zu machen, dann kam
man auf ein Verfahren wie OddEvenMergeSort.
Und das Wesentliche da drin war halt diese OddEvenMerge-Stufe, in der
man dieses Vermischen oder Verschmelzen von sortierten Teilfolgen in
einer rekursiven Art und Weise macht.
In einer geschickten Art und Weise immer gerade jedes zweite Element
rausnimmt.
Die ungeraden Elemente nach links, die geraden Elemente nach rechts.
Also Elemente an geraden Positionen nach rechts.
Und dann hatte ich behauptet, dass man durch einen einzigen
Vergleichsschritt nach diesem rekursiven Aufteilen in der Lage ist,
die Verschmelzung durchzuführen, indem man, so wie hier angedeutet,
entsprechend dem Perfect Shuffle die einzelnen Elemente vergleicht.
Und damit kommt man dann auf eine sortierte Folge.
Und es ist klar, dass das hier vom Zeitverhalten her Log N Aufwand
hat, das OddEvenMerge, weil wir ja diese Rekurrenzgleichung haben, die
hier steht.
Wir haben den Aufwand für die halbe Problemgröße plus einen weiteren
Schritt.
Das macht gerade Log N Stufen.
Log N Zeilen da drin, damit haben wir Zeitlog N parallel.
Und damit haben wir dann insgesamt für ein OddEvenMerge Sort, wo wir
das Log N mal machen müssen, gerade Log N² als Zeit.
Und die Frage war, damit haben wir letztes Mal aufgehört, warum ist
das eigentlich korrekt?
Und darauf kommen wir in dieser Vorlesung nun endlich.
Also Korrektheit des OddEvenMerge, woran liegt das?
Wir betrachten einfach mal 0-1-Folgen.
Solche 0-1-Folgen sind also Folgen von Nullen und Einsen.
Die zu sortieren ist ja ganz einfach.
Muss man ja nur vorne Nullen hinschreiben und Einsen ans Ende.
Das ist also kein großes Problem.
Wir wissen aber, dass wir bei den Sortierverfahren nur durch
Vergleiche zwischen Elementen sortieren.
Das heißt, wir machen nur Größenvergleiche.
Und das Interessante ist, darauf kommen wir noch etwas später, dass
natürlich diese 0-1-Folgen deutlich einfacher zu behandeln sind als
andere Folgen.
Nur der Algorithmus kann davon gar keinen Gebrauch machen.
Der Algorithmus führt ja nur Vergleiche aus zwischen Nullen und
Einsen.
Und das heißt, wenn da zwei Nullen reingehen in so ein Vergleich,
gehen da halt zwei Nullen raus.
Und wenn wir hier einen Vergleich machen und wir haben hier eine Eins
und da eine Null, dann wird mal etwas vertauscht, aber in allen
anderen Fällen passiert gar nichts.
Es werden also nur Nullen und Einsen hier vertauscht.
Das ist aber im Grunde genommen für den Algorithmus irrelevant.
Der vergleicht einfach nur Elemente und schreibt das Minimum der
beiden Elemente nach links und das Maximum nach rechts.
Und das ist halt alles, was er machen kann.
Und das Interessante ist, dass man nur durch Betrachtung der 0-1
-Folgen in der Lage ist, etwas zu sagen über die Korrektheit der
Sortierverfahren.
Da gehen wir gleich nochmal genauer darauf ein.
Zunächst mal ist es also eine ganz einfache Art von Folgen.
Und wenn wir jetzt sagen, wir betrachten 0-1-Folgen und wir betrachten
jetzt die Korrektheit von odd-even-merge, dann haben wir also zwei
Folgen, die eingegeben werden, die bereits sortiert sind, der Länge in
halbe.
Und wenn das sortierte Folgen sind, dann heißt das, die beginnen mit
Nullen und enden mit Einsen.
Nur die Position, wo der Wechsel zwischen 0 und 1 ist, weiß man
natürlich nicht.
Irgendwo haben wir halt hier den Wechsel von 0 auf 1.
Und jetzt nehmen wir einfach an, dass die Anzahl der Einsen gerade
gleich 2a plus 1 eventuell ist, auf der linken Seite.
Hier sieht man das, 2a plus 1 und 2b eventuell plus 1 auf der rechten
Seite.
Warum 2a plus 1?
Ganz einfach, das interessiert uns, ob die Anzahl der Einsen gerade
oder ungerade ist.
Wenn sie gerade ist, dann ist das ein 2a.
Wenn sie ungerade ist, dann ist das ein 2a plus 1, entsprechend 2b
plus 1.
Und wenn wir uns jetzt so eine Folge anschauen, also hier kann ich es
auch mal...
Nehmen wir an, das hier ist unsere Folge.
Und da stehen jetzt Nullen und Einsen.
Und wir wissen, also es ist jetzt nicht sortiert, aber...
Also, nehmen wir an, dass es hier, wenn das hier sortiert ist, dann
wären das hier nur noch Einsen dahinter.
Wenn wir eine gerade Anzahl von Einsen haben, dann ist natürlich die
Anzahl der Nullen auch gerade, weil wir annehmen, dass N eine
Zweierpotenz ist.
Eine gerade Anzahl heißt, wir haben immer solche Pärchen.
Wenn wir eine ungerade Anzahl von Einsen haben, dann ist hier keine
Null, sondern dann ist da eine Eins.
Oder es ist vielleicht hier, das hier eine Null.
Oder neben eine Eins.
Das heißt, das wäre eine ungerade Anzahl von Einsen.
Was heißt das bezüglich der Aufteilung der Nullen und Einsen auf die
linke und die rechte Folge?
Die ersten Positionen in jedem solchen Paar gehen doch nach links.
Das sind die ungeraden Positionen.
Die geraden Positionen, die gehen nach rechts.
Und das heißt, dass bei einer ungeraden Anzahl von Einsen, diese Eins
hier, die dann in so einem Zweierpärchen extra da ist, die geht nach
rechts.
Und das passiert sowohl in der linken als auch in der rechten Folge.
Wenn also z.B.
in beiden Folgen die Anzahl der Einsen ungerade ist, dann entstehen in
der rechten Folge zwei zusätzliche Einsen.
Wenn eine ungerade ist, entsteht nur eine zusätzliche Eins.
Und wenn keine ungerade ist, dann haben wir nur diese, ja, wie viele
Elemente?
Gerade die Hälfte der Einsen aus jeder Folge.
Weil wir ja die eine Hälfte nach links und die andere Hälfte nach
rechts packen.
Also nehmen wir genau A-Elemente aus der linken Folge und B-Elemente
aus der rechten Folge.
Die gehen nach links und entsprechend nach rechts.
Und die eventuell zusätzlichen Einsen, wenn also die Anzahl der Einsen
ungerade ist, die gehen auf jeden Fall nach rechts.
Damit wissen wir, nach diesem Perfect-And-Shuffle für dieses Divide
-and -Conquer ist die Anzahl der Einsen in der linken Folge A plus B
und in der rechten auch A plus B plus eventuell noch zwei weitere
Elemente.
Jetzt nehmen wir an, dass das was unten rauskommt, oder anders gesagt,
die Behauptung ist, dass das was unten rauskommt, ist nachher
insgesamt sortiert.
Also nur Nullen links und Einsen rechts.
Und das müssen wir uns jetzt anschauen, was dort eigentlich genau
passiert.
Also hier oben drüber kommen ja irgendwelche Nullen und Einsen aus
diesen beiden Folgen.
Und jeder Vergleicher vergleicht das i-te Element der linken Folge mit
dem i-ersten Element der rechten Folge.
Also hier war das erste Element von links, das wurde gar nicht
verglichen.
Und weil klar ist, das minimale Element von dieser Folge hier, also
dieses minimale Element, das ist auf jeden Fall anschließend.
Also es ist ja so, dass die beiden minimalen Elemente, hier dieses
Element und das Element, die beiden gehen ja beide in die linke Folge.
Also ist das minimale Element der beiden Folgen, wenn sie verschmolzen
werden, auf jeden Fall an dieser Position.
Da brauchen wir gar nichts zu vergleichen.
Genauso geht das maximale Element der beiden Folgen, das ist auf jeden
Fall am Ende hier an dieser Position.
Das heißt, da brauchen wir auch nichts zu vergleichen.
Und dann wird L2 verglichen mit R1, diese beiden Elemente, und so
weiter.
Also jeder Vergleicher hier drin vergleicht gerade das i-te Element
der linken Folge, für i gleich 2 bis in halbe, mit dem i-ersten der
rechten Folge.
Und jetzt gibt es verschiedene Fälle.
Wir wissen ja, das sind Nullen und Einzen, die da rauskommen.
Also hier stehen a plus b Einzen in jeder Folge.
Und das heißt, die möglichen Fälle, die dort rauskommen, die sehen so
aus.
Wenn das gleich viele Nullen und Einzen sind, dann heißt das, irgendwo
haben wir einen Wechsel zwischen 0 und 1.
Der Wechsel zwischen 0 und 1 ist dann zum Beispiel von i-1 auf i.
Das heißt, wir hätten ab der Position i die erste 1 in der Folge
links.
Dann ist aber die erste 1 in der rechten Folge auch an der Position i.
Das heißt, wenn wir gleich viele Einsen in der linken und rechten
Folge haben, also keine zusätzlichen Einsen links oder rechts, also es
kann ja nur rechts sein, dann haben wir diese Situation.
Dann werden hier L i und R i minus 1 verglichen.
Wir wissen, dieser Vergleich wird ausgeführt.
Das ist ja gerade das, was hier oben drüber steht.
Die beiden werden verglichen.
Und durch den Vergleich wird dann festgestellt, dass die hier nicht in
der richtigen Reihenfolge sind und sie werden vertauscht.
Das heißt, diese Situation, wo die Folge nicht sortiert wäre, wird
richtig erwischt.
Der andere Fall kann sein, dass wir rechts eine 1 mehr haben.
Dann würde eine 1 mehr heißen, dass das Element R i minus 1 bereits 1
ist.
Dann ist die Folge sowieso schon sortiert.
Dann schadet der Vergleich auch nichts.
Aber wir haben ihn auf jeden Fall erwischt.
Und das nächste ist, dass wir zwei zusätzliche Einsen haben.
Dann wäre auch R i minus 2 gleich 1.
Aber auch dann wäre das Ganze bereits sortiert.
Das heißt, der einzig problematische Fall ist, dass wir gleich viele
Einsen links und rechts haben.
Weil in der Situation es hier eine unsortierte Stelle gibt.
Und die wird durch diesen einen Vergleich erwischt.
Und die ganze Folge ist nach dem einen plötzlichen Vergleich sortiert.
Da wir nicht wissen, an welcher Position das auftaucht, müssen wir
natürlich für jedes i das machen.
Deswegen haben wir hier also entsprechend diese Vergleiche in dieser
Zeile hier.
Aber es ist, glaube ich, offensichtlich, die 0,1-Folgen werden durch
dieses Verfahren korrekt sortiert.
Und wir haben ja für n gleich 2 wird ein Vergleich gemacht der beiden
Elemente.
Dadurch werden die sowieso richtig sortiert.
Also für den Abbruch der rekursiven Aufteilung.
Und wie wir hier sehen, wenn wir hier entsprechend die sortierten
Folgen haben, von links und rechts, also aus diesem rekursiven
Verfahren, durch diese eine Zeile hier unten werden die Situationen,
in denen noch etwas unsortiert sein kann, auf jeden Fall erwischt.
Und wir haben anschließend eine sortierte Folge.
Das heißt, für diese 0,1-Folgen ist das Ganze richtig.
Die Ausgabe ist richtig sortiert.
Und nach dem 0,1-Prinzip wird damit auch jede Folge korrekt sortiert.
Und das 0,1-Prinzip ist eben das, was ich schon angedeutet habe.
Das steht hier auf dieser Seite.
Das 0,1-Prinzip lautet wie folgt.
Wenn ein Algorithmus A, der nur auf Vergleichen basiert, das heißt er
vergleicht Elemente, mehr macht er nicht.
Praktisch ein Entscheidungsbaumalgorithmus.
Wenn der alle Folgen von Nullen und Einzelnen sortiert oder
verschmilzt, dann sortiert er auch jede beliebige Folge von Elementen
einer geordneten Menge.
Und das heißt, wir können uns bei der Überlegung bezüglich der
Korrektheit eines Sortieralgorithmus, sofern er nur auf Vergleichen
basiert, beschränken auf die Betrachtung der 0,1-Folgen.
Das ist eine deutliche Erleichterung bei solchen Korrektheitsbeweisen.
Verifikation von Algorithmen wird so ganz viel einfacher.
Wir werden das an mehreren Stellen noch sehen.
Die Frage ist nur, wieso ist das so?
Die 0,1-Folgen sind doch so viel einfacher zu behandeln.
Wieso kann es sein, dass man damit zeigen kann, dass auch beliebige
Folgen sortiert werden?
Nun hier steht, wenn er alle Folgen von Nullen und Einzelnen sortiert,
dann sortiert er jede beliebige Folge.
Wenn man sowas zeigen will, ist es ein Ansatz zu sagen, ok, nehmen wir
doch mal an, so ein Algorithmus würde für eine beliebige Menge eine
Folge nicht sortieren.
Dann müssten wir einfach eine 0,1-Folge konstruieren können, die dann
auch nicht sortiert wird.
Das wäre also Beweis durch Kontraposition.
Wenn er also nicht jede beliebige Folge von Elementen einer geordneten
Menge sortieren kann, dann kann er auch nicht alle 0,1-Folgen
sortieren.
Wenn wir das zeigen können, dann haben wir gezeigt, dass wir aus der
Tatsache, dass er alle Folgen von Nullen und Einzelnen sortiert,
schließen können.
Er sortiert jede beliebige Folge von Elementen einer geordneten Menge.
Wie können wir das machen?
Wir nehmen einfach an, es gibt irgendeine Folge S, das ist irgendein
beliebiger Algorithmus, die durch diesen Algorithmus A nicht sortiert
wird.
Das heißt, wir haben hier irgendeine Folge S1 und so weiter bis Sn,
die wird durch A sortiert oder durch A irgendwie bearbeitet.
Und dann kommt eine Folge raus von Elementen und wir behaupten, diese
Folge S wird nicht sortiert.
Wenn die nicht aufsteigend sortiert ist, dann heißt das, es gibt
irgendeine Position, wo die Reihenfolge nicht stimmt.
Und da nehmen wir einfach...
Wir wollen eine 0-1-Folge konstruieren, die dann ebenfalls nicht von A
sortiert werden kann.
Und das machen wir so, indem wir uns angucken, wo ist eigentlich das
kleinste Element von S?
Also irgendwo ist hier ein Si in dieser Folge, das in der falschen
Position steht.
Wir nehmen das kleinste Element der Folge S her, das nicht an der
richtigen Position steht.
Wenn es nicht an der richtigen Position steht, dann heißt das, es gibt
ein Sj irgendwo hier vor.
Wahrscheinlich müsste genau das Element davor sein.
Wenn es nicht sortiert ist, heißt das, hier stimmt die
Sortierreihenfolge nicht.
Es gibt ein Sj.
Die Reihenfolge soll ja so sein, aufsteigend in der Richtung.
Das Sj ist größer als Si, bzw.
Si kleiner als Sj.
Und das Sj taucht aber in der von A abgelieferten, angeblich
sortierten Folge vor Si auf.
Das heißt, die Folge ist nicht sortiert.
Wir haben also eine Folge, die ist nicht sortiert worden.
Und jetzt machen wir das ganz einfach.
Wir konstruieren eine 0-1-Folge.
Eine 0-1-Folge S', indem wir genau das, was hier passiert, versuchen
nachzubilden.
Und diese Folge S' von 0 und 1 wird so definiert, dass alle Elemente,
die in der Folge S, die kleiner gleich Si sind, die werden auf 0
gesetzt.
Und alle anderen Elemente, die also größer als Si sind, werden auf 1
gesetzt.
Das heißt, wir haben dann hier irgendwelche Nullen und Einsen.
Das war ja hier S1 bis Sn.
Wir haben also das Si auf 0 gesetzt und alle anderen auf 1.
Das heißt insbesondere bei dem S', da wäre ja dieses Si auf 0 gesetzt
worden und das Sy auf 1.
Das heißt, wenn der Algorithmus A die Folge S' genauso behandelt wie
die Folge S, dann würde am Ende hier eine 1 vor einer 0 kommen.
Das heißt, die Folge wäre nicht sortiert.
Das wollen wir irgendwie erreichen.
Was wir jetzt argumentieren müssen ist, dass der Algorithmus A auf
dieser 0-1-Folge-S' das gleiche Ergebnis abliefert, prinzipiell, wie
auf der Folge S.
Das heißt, er wird auch diese Unsortiertheit produzieren am Ende.
Dann hätten wir die 0-1-Folge, die nicht sortiert wird.
Jetzt schauen wir uns an, was der Algorithmus macht.
Der Algorithmus A, der vergleicht doch Elemente aus der Folge, die
eingegeben wurde.
Und wir haben, wenn wir jetzt betrachten, was macht der Algorithmus
auf der Folge S', auf dieser 0-1-Folge, dann vergleicht er Elemente,
irgendwie Sk' und Sl', irgendwelche zwei Elemente.
Dann muss man sich anschauen, was macht er mit denen, was kann er mit
denen machen.
Wir vergleichen das mit der Situation, als er nur die Folge S
bearbeitet hat.
Nun kennen wir die Beziehung zwischen Folge S und S'.
Also, wenn das Sk kleiner gleich Si ist, dann wissen wir, dass Sk ist
0.
Dann ist das hier 0.
Und wenn Sl, das andere Element, das wir verglichen wird, wenn das
größer gleich Sj ist, dann ist das hier 1.
Naja, das heißt, das Element, wir wissen in der Folge, in der
ursprünglichen Folge S, da ist Si kleiner als Sj, also ist dort auch
Sk kleiner als Sl gewesen.
Hier ist jetzt in der Folge S', das eine 0, das andere 1, ist also
auch diese kleiner Beziehung tatsächlich da.
Das heißt, diese Elemente werden durch einen Vergleich genauso
behandelt.
Sie werden also, wenn sie verglichen werden, entweder vertauscht oder
nicht, je nachdem, mit welcher Reihenfolge sie in der Folge
vorgekommen sind.
Wir haben hier auch das gleiche Größenverhältnis.
Das heißt, da wird der Algorithmus A auf der Folge S' genau die
gleichen Operationen ausführen, wie auf der Folge S.
Alle anderen Vergleiche tangieren aber keine Ordnungsrelationen
bezüglich Si und Sj.
Und darum geht es ja eigentlich nur.
Die anderen Vergleiche, Vergleiche von Sk' und Sl', bei denen beide
kleiner als Si sind, das sind Vergleiche von Nullen.
Ob er die vertauscht oder nicht, ist völlig egal.
Da passiert ja nichts weiter.
Das hat keinen Einfluss auf die Position von Si und Sj.
Also für alle anderen eine Situation.
Wenn beide größer als Si sind, dann sind beide eins.
Auch das verändert nichts an der Position von Si' und Sj' in der
endgültigen Folge.
Und das heißt, dass diese Situation hier zwangsläufig genauso
auftreten muss, wenn jetzt die Folge S' sortiert wird.
Dann wird hier also in der entsprechenden durch A sortierten Folge
diese nicht sortierte Situation eintreten.
Und damit haben wir die Folge aus Nullen und Einsen, die nicht
sortiert wird.
Und damit ist gezeigt, dass das Null-Eins-Prinzip gilt.
Sobald irgendeine Folge nicht sortiert wird, können wir auch eine Null
-Eins -Folge konstruieren, die nicht sortiert wird.
Und damit können wir also andersrum jetzt die Beweise der Korrektheit
von Sortierverfahren, sofern sie nur Vergleiche verwenden, reduzieren
auf die Betrachtung von Null-Eins-Folgen.
Und Sie werden gleich sehen, wie schön man das ausnutzen kann.
Wir haben es ja gerade eben schon gesehen bei odd, even, merge.
Sie werden noch mehr Beispiele kennenlernen heute.
Was ich auch noch machen möchte, ist ein bisschen genauer zeigen,
welche Vergleiche eigentlich ausgeführt werden.
Wenn wir uns dieses Netz hier anschauen, dieses Verfahren, man sieht
hier zwar, dass dort an der untersten Position hier, da werden
Vergleiche ausgeführt.
Aber welche Elemente mit welchen verglichen werden, ist hier noch
nicht so ganz deutlich.
Sie können das sofort als Programm aufschreiben, mit rekursivem
Abstieg, also rekursiv formuliert, mit Abbruchbedingungen.
Für N gleich 2 werden die einfach verglichen und an die richtige
Position gebracht.
Und ansonsten haben Sie diese einfachen Operationen.
Wenn man sehen will, welche Vergleiche werden tatsächlich ausgeführt
auf den Elementen der Folge, dann schaut man sich doch gerne das etwas
anders an.
Also, dieses war unser odd, even, merge Netz.
Die Frage ist, was passiert, wenn man das tatsächlich insgesamt
ausführt.
Für N gleich 16 kommt dann folgendes Vergleichernetz raus.
Wie entsteht dieses Netz?
Sie sehen, das ist ein sehr reguläres Netz.
Ist klar, durch dieses rekursive Aufteilen, das geschieht ja ganz
systematisch links und rechts, entsteht etwas Symmetrisches in den
beiden Hälften oder bei dieser ganzen Aufteilung.
Wie entstehen diese Vergleiche, die hier jetzt aufgeführt sind?
Das Vergleichernetz hat letztes Mal schon gesagt, da wird die Folge in
dem Fall für N gleich 16, also hier S1 eingegeben, da kommt S16 rein.
Und hier unten kommt dann die aufsteigend sortierte Folge raus.
Das Vergleichernetz ist für odd, even, merge, also für ein solches
Merge.
Das heißt, wir nehmen an, dass wir gerade hier zwei aufsteigend
sortierte Folgen haben, von S1 bis S8 aufsteigend sortiert und von S9
bis S16 auch aufsteigend sortiert.
Und die werden dann so verschmolzen.
Wie kommen diese ersten Vergleiche zustande?
Und was sind die ersten Vergleiche, die ausgeführt werden?
Zunächst mal machen wir ein Perfect-On-Shuffle.
Da kommen also die Elemente 1, 3, 5, 7 usw.
alle nach links und die Elemente S2, S4, S6 usw.
alle nach rechts.
Dann wird ja rekursiv das weitergemacht.
Dann machen wir wieder ein On-Shuffle.
Also wenn wir so eine Folge haben, schauen Sie sich an hier, 1, 2, 3,
4, 5, 6, 7, 8, wenn wir es dafür machen, dann würden wir zunächst mal
1, 3, 5, 7 nach links schreiben und 2, 4, 6, 8 nach rechts.
Und dann würden wir das wieder so machen, dann würde hier stehen 1, 5
und 3, 7 und hier würde stehen 2, 6 und 4, 8.
Jetzt habe ich das nur gemacht für n gleich 8.
Für n gleich 16 wäre das entsprechend eine andere Aufteilung.
Und was man sieht ist, jetzt haben wir die Situation, dass wir hier
Paare von Elementen haben.
Und bei diesen Paaren von Elementen werden zunächst mal einfach
Vergleiche gemacht.
Also bei dieser Situation für n gleich 8 hätten wir 4 Vergleiche, die
gleichzeitig ausgeführt werden.
Und es wird das Element 1 mit 5 verglichen, 2 mit 6, 3 mit 7 und 4 mit
8.
Und Sie sehen, das sind genau die Vergleiche, die hier entsprechend
gemacht werden.
Durch die Frequenz, die wir aufteilen, werden also die Elemente S1 und
S8 verglichen, also genau die Elemente mit Abstand n halber.
Die werden so paarweise verglichen und vertauscht.
Das ist der erste Vergleich, der gemacht wird, wenn wir auf Folgen der
Länge 2 gekommen sind.
Und danach treten diese Vergleiche in Aktion.
Dann wird das erste Mal verschmolzen.
Die werden verschmolzen.
Wenn wir das bei diesem kleineren Beispiel anschauen, dann würden wir
nur einen Vergleich machen zwischen den beiden Elementen und einen
Vergleich zwischen den beiden Elementen.
Ja?
Zwei Vergleiche.
Weil wir ja die Positionen links und rechts, die sind bereits sortiert
und da genauso.
Und dann würde man entsprechend...
Das ist also genau dieser Vergleich.
Hier haben wir jetzt vier Vergleiche zu machen.
Wir haben vier Paare von...
Oder ne, in dem Fall hätten wir acht Paare, die jetzt jeweils
paarweise verschmolzen werden.
Also vier Verschmelzungsvorgänge.
In jedem Verschmelzungsvorgang ein Vergleich.
Und das sind gerade die Elemente an den Positionen, die hier durch
Pfeile verbunden sind.
In dieser Stufe.
Jetzt kommt die nächste Verschmelzung, wo Folgen der Länge 4
verschmolzen werden zu Folgen der Länge 2.
Das passiert genau...
Folgen der Länge 4 werden verschmolzen zu Folgen der Länge 8.
Entschuldigung.
Dann haben wir genau diese Vergleiche auszuführen.
Und entsprechend, wenn wir diese zwei Folgen der Länge 8 haben, dann
werden, so wie man das hier oben drüber auch sieht, werden genau diese
Vergleiche ausgeführt.
Das linkeste und das rechteste Element, die sind bereits in der
richtigen Position.
Und alle anderen müssen entsprechend verglichen werden.
Und die stehen hier jetzt an genau diesen Positionen.
In der...
So, dass wir genau diese Vergleiche hinschreiben können.
Also das sind einfach die Vergleiche so aufgemalt, wie sie zwischen
den einzelnen Positionen der ursprünglichen Folge, also zwischen den
ursprünglichen Elementen hier ausgeführt werden.
Das einfachen Auftrüseln dieses Perfect-Unshuffle und Perfect-Shuffle
sukzessive.
Dann kommen wir genau auf dieses Vergleichernetz.
Und damit haben wir hier offensichtlich für Folgen der Länge 16, für n
gleich 16, haben wir gerade 1, 2, 3, 4 Stufen, die gemacht werden
müssen.
Genau Lockendstufen.
Und entsprechend, wenn wir jetzt das regressiv machen, dann halt
Lockquadratendstufen für das gesamte Sortieren.
Ich hoffe, dass das verständlich geworden ist, was hier gerade
passiert.
Also ein sehr einfaches Vergleichernetz.
Und natürlich ist die Gesamtzahl der Vergleiche, die ausgeführt
werden, hier, die ist Größenordnung n mal Log n.
Wir haben hier n halbe Vergleiche in der ersten Stufe, wir haben
Größenordnung n halbe nochmal in der zweiten Stufe, in der dritten
Stufe, in der vierten Stufe.
Nicht genau, ein bisschen weniger, aber so über den Daumen schon.
Das heißt, die Anzahl der Vergleiche ist n log n, allein fürs
Verschmelzen.
Das wird log n mal gemacht.
Wir haben also n mal Log n Quadratvergleiche im gesamten Verfahren.
Mehr Vergleiche als beim sequenziellen Sortieren.
Da hatten wir im besten Fall n log n, beziehungsweise bei Merge Sort
hatten wir n log n Vergleiche.
Das heißt, hier wird ein bisschen mehr gemacht, als bei dem, was man
sequenziell machen könnte.
So, das ist das Einsortierverfahren.
Es gibt noch andere, nicht, dass Sie da meinen, das wäre das Einzige,
was man parallel machen kann.
Wenn wir parallele Strukturen haben, kann man sehr viele verschiedene
Verfahren einsetzen.
Und hier ist noch ein anderes Prinzip, das auch ganz witzig ist.
Oder auch nicht nur witzig, sondern das hat ein paar Vorteile, Wenn
wir uns das Verfahren hier anschauen, dann sieht man, das ist zwar
einigermaßen systematisch aufgebaut, aber das malt man sich nicht
sofort hin, also welche Vergleiche hier genau ausgeführt werden.
Ich zeige Ihnen jetzt ein anderes Netz für das Sortieren bitonischer
Folgen.
Sortieren bitonische Folgen.
Die sind nicht monoton oder antiton, sondern biton.
Das heißt, wir haben eine auf- und absteigende Folge.
Und zwar geht das ein Stück lang aufwärts und dann wieder ein Stück
lang abwärts.
Das ist eine Folge, die kann man als 0-1-Folge so charakterisieren,
dass wir Nullen haben, danach Einsen und danach wieder Nullen.
Das wäre auf- und absteigend.
Jetzt ist eine bitonische Folge ein bisschen allgemeiner definiert.
Das darf eine zyklische Verschiebung einer auf- und absteigenden Folge
sein.
Was ist denn eine zyklische Verschiebung einer auf- und absteigenden
Folge?
Was kann dabei entstehen?
Wenn wir das zyklisch verschieben, Belegen Sie sich die Einsen, die
wandern immer weiter nach rechts.
Irgendwann haben wir Einsen bei der zyklischen Verschiebung, die dann
von hinten wieder nach vorne wandern.
Dann kann es so eine Situation geben, dass wir erst Einsen haben, dann
Nullen und dann wieder Einsen.
Und das bedeutet, wir hätten dann etwas, oder wenn man das jetzt von
den Größenverhältnissen anschaut, bei einer zyklischen Verschiebung,
wenn man also jetzt auf Folgen von beliebigen Elementen das
betrachtet, dann kann es sein, dass eine Zeit lang absteigend ist,
dann im bestimmten Bereich wieder aufsteigend und dann wieder
absteigend.
Und in Bezug auf diese Null-Eins-Folgen heißt das, wir haben entweder
die Situation, dass wir Nullen haben, gefolgt von Einsen, gefolgt von
Nullen, oder Einsen gefolgt von Nullen, gefolgt von Einsen.
Zwei ganz einfache Fälle.
Und jetzt betrachten wir ein Vergleichernetz, dieses hier.
Das sieht offen, denkt man, das habe ich schon gesehen, aber das
andere Merge Sort sah anders aus.
Hier haben wir eine sehr gleichartige Darstellung.
Wir haben hier Vergleiche, also dieses Vergleichen zwischen Elementen
mit einem Abstand in halbe.
Also diese Elemente haben den Abstand in halbe jeweils.
Element 1 mit Element S9, S2 mit S10, S3 mit S11 und so weiter.
Und dann betrachten wir das entsprechende für das, was hier rauskommt,
nochmal.
Und wir sehen, das ist wieder genauso aufgebaut.
Wir betrachten das hier nochmal und wir sehen, das ist wieder genauso
aufgebaut.
Und dann betrachten wir das hier nochmal und wir sehen, auch hier ist
es nochmal so aufgebaut.
Die beiden Elemente werden verglichen.
Das heißt, hier haben wir eine ganz gleichartige Anordnung der
Einzelvergleiche.
Es werden immer paarweise die Elemente verglichen, die so hälftig in
der Folge verteilt sind.
Immer Abstand in halbe, wobei n die aktuelle Folgelänge ist, der
Folgen, die hier insgesamt betrachtet werden.
Die Ausgangssituation ist, dass wir eine bitonische Folge eingeben,
von dieser Art.
Also wir hatten vorher zwei aufsteigend sortierte Folgen, die bei dem
Merge eingegeben wurden.
Beziehungsweise bei Odd-Even-Merge-Sort eine völlig unsortierte Folge.
Hier machen wir die Annahme, wir müssen nur noch eine bitonische Folge
sortieren.
Die bitonische Folge sortieren als 0-1-Folge heißt, wir haben zum
Beispiel diese Situation, dass wir Nullen mit Nullen anfangen, dann
irgendwelche Einsen haben und am Ende wieder Nullen.
Und jetzt schauen wir uns einfach mal für diesen Fall, der hier
angegeben ist, an, was passiert.
Durch diese ganzen Vergleiche bleiben natürlich die Nullen, sofern sie
den Vergleichen auftauchen, links und die Einsen wandern nach rechts.
Und in diesem Beispiel sehen wir, bereits nach den ersten Vergleichen
tauchen links nur noch Nullen auf.
Das ist schon alles sortiert, das heißt in dem jetzt eingerahmten
Bereich, da passiert nichts mehr, da werden unten auch diese Nullen
alle stehen bleiben.
Und in der rechten Folge sehen wir, da haben wir jetzt genau die
andere Situation der bitonischen Folge.
Einsen, dann steht dort eine Null und wieder eine Reihe Einsen.
Das war auch eine bitonische Folge.
Und auf diese bitonische Folge wenden wir jetzt ja das gleiche Prinzip
nochmal an.
Wir vergleichen die Elemente, die gerade um ein Halbe verschoben sind
und was passiert?
Also links tut sich sowieso nichts mehr, aber rechts werden die
Elemente entsprechend verglichen.
Und wir haben...
Wieso wandert jetzt diese Eins diese Null?
Wir haben also hier diese Elemente, dieses Element hier, diese Null,
die ist in dieser Position, wird verglichen mit einer Eins, da tut
sich nichts.
Die bleibt an der Position.
Die verändert nicht ihre Position.
Was rauskommt, ist eine Folge von Einsen in der rechten, im rechten
Viertel.
Die ist bereits sortiert.
Natürlich auch eine bitonische Folge.
Weil für, wenn also nur Einsen auftauchen, ist es natürlich auch
bitonisch.
In dem dritten Viertel, hier drin, haben wir jetzt Einsen gefolgt von
einer Null.
Auch wieder eine bitonische Folge.
Und entsprechend, Sie sehen hier wird ein Vergleich jetzt ausgeführt
zwischen einer Eins und einer Null.
Das heißt, da wird etwas vertauscht.
Und dann haben wir wieder die Situation, dass hier eine Folge
auftaucht, die schon sortiert ist, und eine, die noch nicht sortiert
ist.
Ist aber auch bitonisch.
Eine Eins gefolgt von einer Null.
Und am Ende sind wir fertig.
Und was Sie sehen ist, dass wir nach jeder Vergleicherstufe wieder
eine Situation haben, bei der wir wieder eine bitonische Folge
sortieren müssen.
Und das ist also die Behauptung, nach jeder Stufe ist eine bitonische
Folge, die eingegeben wurde, in zwei bitonische Folgen halber Länge
geteilt.
Mit einer weiteren Eigenschaft, sodass die linke kleiner oder gleich
der rechten Folge ist.
Das heißt, alle Elemente der linken Folge sind kleiner gleich den
Elementen der rechten Folge.
Beziehungsweise das Maximum der linken Folge ist kleiner gleich dem
Minimum der rechten Folge.
Und wenn das so ist, die werden dann anschließend nicht mehr in
Beziehung gesetzt zueinander, habe ich auf jeden Fall am Ende die
Folge insgesamt sortiert.
Weil ja, wenn also diese Eigenschaft gilt, die linke Folge ist kleiner
oder gleich der rechten Folge, wegen dieses sukzessiven Aufteilens
habe ich dann automatisch am Ende eine insgesamt sortierte Folge.
Ein sehr systematisch aufgebautes Vergleichernetz und die Frage ist,
was bringt uns das?
Wann haben wir schon die Situation, dass wir bitonische Folgen
sortieren müssen?
Ja, normalerweise haben wir irgendwelche unsortierten Folgen, die
sortiert werden müssen.
Und da werden wir später gleich sehen, wie man das anwenden kann.
Wir müssen aber zunächst mal uns überlegen, ob das überhaupt richtig
ist, was ich da gesagt habe.
Das war ja hier ein kleines Beispiel.
Ist das tatsächlich immer so?
Und jetzt hilft uns das Null-Eins-Prinzip.
Das wenden wir jetzt an.
Die Folgen, die auftauchen können, sind bitonisch.
Das heißt, wir haben entweder diese Situation, Nullen gefolgt von
Einzelnen gefolgt von Nullen oder Einzelnen gefolgt von Nullen gefolgt
von Einzelnen.
Wenn wir das jetzt betrachten, was da passiert, dann haben wir also
entweder...
Ja, es kann so eine Situation sein oder so eine Situation.
Betrachten wir uns das an, diese Folge von Nullen und Einzelnen.
Hier ist jetzt farbig dargestellt, dass wir hier mit Nullen beginnen
und dann irgendwann Einzelnen haben.
Und irgendwann wieder Nullen.
Also hier sind die beiden Hälften.
Ich nehme mal an, ich habe jetzt insgesamt Folgenlänge 2n.
Und ich habe jetzt die zwei Hälften der Folge dargestellt.
Und wenn ich das so hälftig darstelle, sind praktisch jetzt
übereinander genau die Elemente, die durch dieses bitonische Sortieren
verglichen werden.
Wir hatten ja gesehen, das war ja gerade diese Struktur.
Und der Abstand zwischen den Elementen, die hier waren, war gerade
halbe Folgenlänge.
Und das heißt, wenn wir die so übereinander schreiben, dann sind das
genau die Elemente, die verglichen werden, die übereinander stehen.
So, die Folge insgesamt bestand aus Nullen, gefolgt von Einzelnen,
gefolgt von Nullen.
Da kann es natürlich sein, dass so eine Situation auftaucht, dass wir
hier einen Bereich haben, wo es sich überlappt.
Wenn wir also mehr als N Einzelnen bei einer Gesamtfolgenlänge von 2n
haben, dann überlappt sich das.
Jetzt werden die alle so senkrecht verglichen.
Das heißt, alle Einzelnen wandern nach unten in diesem Bild.
Und die Nullen bleiben oben.
Die Nullen bleiben oben heißt hier in diesem Bereich, wandern also die
Nullen nach oben.
Nur in diesem Bereich bleiben die Einzelnen insgesamt stehen.
Und wir haben dann zwei Folgen als Ergebnis.
Eine Folge, da stehen Nullen, gefolgt von Einzelnen, gefolgt von
Nullen.
Und in dieser Situation nur noch Einzelnen unten drunter.
Offensichtlich sind alle Elemente der Folge, die unten steht, größer
gleich den Elementen, die oben stehen.
Analog kann man das betrachten für die Folge, wo Einzelnen von Nullen
von Einzelnen gefolgt werden.
Da haben wir also Einzelnen, Nullen, Nullen und Einzelnen.
Hier hätten wir wieder mehr als N Einzelnen.
Also mehr als die Hälfte der Elemente sind eine Eins.
Dann haben wir diese Überlappung.
Auch hier hätten wir die gleiche Situation, dass wir oben eine Folge
haben, die aus einer Folge von Nullen, gefolgt von Einzelnen, gefolgt
von Nullen besteht und unten nur Einzelnen.
Das ist natürlich nur eine Möglichkeit, wie das aussieht.
Wenn das b kleiner ist, in diesem Fall, das heißt wir haben weniger
Einzelnen drin, dann kann so eine Situation auftauchen.
Weniger Einzelnen heißt, wir haben hier einen gewissen Bereich, da
treten nur Nullen auf.
Und wenn wir die jetzt vergleichen, die Elemente, dann haben wir also
hier diesen Bereich, wo nur Nullen gewesen sind.
Also stehen oben nur Nullen und unten stehen Einzelnen, gefolgt von
Nullen, gefolgt von Einzelnen.
Und in einer anderen Situation, wir haben weniger Einzelnen, also mehr
Nullen, das heißt auch hier überlappen sich die Eins-Bereiche nicht,
wie man hier sieht.
Dann haben wir die gleiche Situation.
Taucht dort genauso auf.
Und die letzte Situation, die noch möglich ist, ist, dass die
Einzelnen nur in einem Bereich liegen.
Wenn sie unten sind, passiert sowieso nichts.
Und wenn sie oben liegen, wandern sie nach unten.
Und dann haben wir aber auch wieder genau die Situation wie vorher.
Zwei Teilfolgen, die jeweils betonisch aufgebaut sind.
Und analog sehen wir das in dem anderen Fall auch hier zwei Folgen,
die betonisch sortiert sind.
Also für alle möglichen Fälle, die auftreten können, bei 0-1-Folgen,
haben wir gezeigt, das Ergebnis dieses einen Vergleicherschritts ist,
dass wir zwei betonisch sortierte Folgen haben.
Und die rechte Folge, bzw.
in diesem Bild die untere, ist auf jeden Fall insgesamt größer gleich
der drüberliegenden Folge.
Und damit ist die Aussage von der vorigen Folie nachgewiesen.
Dieses Sortiernetz, oder Vergleichernetz, sortiert tatsächlich eine
betonische Folge.
Jetzt ist immer noch die Frage, was hilft uns das?
Betonische Folgen sind ja nicht so üblich.
Zumindest ist uns das gar nicht so klar gewesen, dass man mit
betonischen Folgen was machen kann.
Und die Idee ist also, dass man beim Botonic Merge ein Verschmelzen
sortierter Folgen macht.
Das Verschmelzen sortierter Folgen, das haben wir doch bei dem
einfachen Odd-Even-Merge-Sort gemacht.
Da hatten wir jeweils zwei sortierte Teillisten und mussten die
verschmelzen.
Wir wollen doch aber etwas betonisches sortieren.
Wir machen einfach ein logisches Spiegeln der rechten Folge.
Also was wir eigentlich haben, ist zwei aufsteigend sortierte Folgen.
Das transformieren wir einfach in die Situation, die so aussieht.
Die rechte Folge wird einfach gespiegelt.
Dann haben wir eine betonische Folge.
Aufsteigend, absteigend.
Und wenn sie betonisch ist, brauchen wir nur das betonische
Sortiernetz anzuwenden.
Ein einfaches Vertauschen der rechten Folge macht daraus eine
betonische Folge insgesamt.
Und das wissen wir, können wir mit Log-End-Stufen machen.
Damit müssen wir nur die Anfangssituation erzeugen, dass wir zwei
aufsteigend sortierte Folgen haben.
Und damit sind wir fertig.
Jetzt steht hier ein logisches Spiegeln der rechten Folge.
Das geht ganz einfach.
Das ist hier unsere ursprüngliche Folge.
Oder das sind die beiden sortierten Teilfolgen.
Präkursiv, auf so einem Merge Sort ähnlichen Ansatz, haben wir zwei
Teilfolgen der Länge in halbe, die jetzt verschmolzen werden sollen.
Jetzt wollen wir die logisch spiegeln, die rechte Folge.
Das machen wir einfach so, indem wir die Vergleiche anders anordnen.
Das logische Spiegeln der rechten Teilfolge entspricht dem, dass wir
die Vergleiche anders machen.
Wir müssen beim logischen Spiegeln dafür sorgen, dass dieses Element
hier verglichen wird mit dem Element dort.
Genau das wird gemacht.
Und entsprechend dieses Element soll verglichen werden, wenn das
vertauscht wird mit dem Element.
Genau das wird gemacht.
Die Vergleiche werden anders hingemalt, in der ersten Stufe des Bit
-Bitonic -Sort.
Und damit haben wir ein Bitonic Merge, weil wir einfach nur aus diesem
Netz, wissen wir jetzt, können wir eine sortierte Folge machen.
Und wir müssen nur sukzessive solche sortierten Teilfolgen erzeugen.
Das geht halt mit dem üblichen präkursiven Ansatz.
Und damit haben wir jetzt ein Bitonic Merge Sort.
Also hier nochmal die zwei Listen, das ist klar, das ist ja nur das
gleiche nochmal, was vorher auch passiert war.
Einfach mit diesen etwas anders angeordneten Vergleichen kommen wir
dann auf jeden Fall auf eine sortierte Folge.
Rekursiv bekommt man dann bei Bitonic Merge Sort und Laufzeit ist
wieder log²n, weil wir in jeder Merge-Stufe logn-Stufen haben von
Vergleichen.
Die Anzahl der Vergleiche ist hier ein bisschen größer als bei Odd
-Even Merge Sort.
Aber der Aufbau dieses Vergleichernetzes ist etwas symmetrischer und
das macht den Entwurf etwas einfacher.
Das führt dazu, dass man in bestimmten Verfahren bei Tonic Merge Sort
dem Odd-Even Merge Sort vorzieht.
Beide Verfahren werden in der Praxis aber eingesetzt.
Und die werden übrigens in der Praxis vor allen Dingen dort
eingesetzt, wo man häufig sortieren muss.
Das passiert zum Beispiel in der Signalverarbeitung, wenn man
irgendwelche Filter baut, bei denen man rangbasierten Filter macht.
Möchte man es wegen Medien bestimmen oder irgendwelche Quantile
bestimmen.
Und da baue ich so ein Sortierverfahren direkt in Hardware.
Wenn ich das in Hardware baue, dann heißt das, ich baue also einen
Baustein, der so aufgebaut ist, das kann ich ganz systematisch machen.
Und in Hardware werden also durchaus solche Odd-Even Merge Sort oder
bei Tonic Merge Sort Strukturen realisiert.
Ich habe dann zwar lange Leitungen da drin, das ist ein anderes
Problem, weil ich Elemente an sehr weit auseinanderliegenden
Positionen hier vergleichen muss.
Das kann man durch eine geschickte Anordnung der Vergleiche noch ein
bisschen reduzieren.
Also dieses Perfect Shuffle und Unshuffle muss man machen.
Das führt zu gewissen Problemen.
Aber da kommen wir gleich noch drauf, was man da machen kann.
Das sind jedenfalls Verfahren, die sind sehr praxisrelevant, werden
eingesetzt, werden auch in Verbindung mit anderen Ansätzen durchaus
verwendet.
Gut, das zu dem Sortieren.
Vielleicht noch eine kurze Bemerkung zum Sortieren, das hatte ich
letztes Mal glaube ich schon gesagt.
Wenn man allgemein dann mit einer PRAM sortiert, also das PRAM Modell
hat, kann man sogar runterkommen bis auf Log N parallele Stufen mit
insgesamt N Log N vergleichen.
Also optimaler Zeitgewinn, aber das ist ein sehr kompliziertes
Verfahren, das ich Ihnen hier nicht vorstellen kann, das würde viel zu
lange dauern.
Das ist auch ein Verfahren, bei dem die Konstante vor dem Log N sehr
sehr groß ist.
Und das heißt praxisrelevant ist es nicht, nur theoretisch
interessant, dass man tatsächlich einen optimalen Zeitgewinn
asymptotisch bekommen kann.
Praxisrelevant sind die Verfahren, die ich Ihnen hier vorstelle,
dieses Merge Sort und das Bitonic Merge Sort.
Und jetzt schauen wir auf eine andere Situation, die auch
praxisrelevant ist.
Unsere zu sortierenden Elemente sind in einem zweidimensionalen Feld
von Prozessoren verteilt.
Die Situation kann durchaus öfter auftauchen.
Es gibt viele Superrechner, in denen man zweidimensionale Felder von
Prozessoren hat, in denen Elemente liegen, die sortiert werden müssen.
Etwas, was durchaus auftauchen kann.
Ich nehme natürlich jetzt an, dass wir jeweils ein Element pro
Prozessor hier drin haben.
In der Praxis werden das eher größere Dateien oder größere Teilmengen
von Elementen oder Teillisten, die insgesamt dann später sortiert sein
sollen.
Aber für jetzt unsere Situation nehme ich an, ich habe pro Prozessor
ein Element.
Und jetzt muss ich diese Elemente in Prozessoren P1 bis Pn.
Ich habe hier noch ein n.
Also ich habe Anzahl der Zeilen, auch Anzahl der Spalten sei n.
Und ich muss jetzt hier sortieren.
Was heißt denn hier eigentlich sortieren?
Bei einer linearen Liste ist es einfach.
Aufsteigen oder absteigen.
Wie will man das denn hier anordnen?
Was ist denn hier eine sinnvolle Sortierreihenfolge?
Also ich habe groß n gleich klein n² Prozessoren.
Und ich nehme an, ich habe ein Datum pro Prozessor.
Wenn Sie es in der Realität anwenden und Sie haben irgendein größeres
Feld von Prozessoren, werden Sie das niemals mit einem Datum pro
Prozessor so machen, sondern nur wenn das größere Dateien sind.
Weil einfach die Anzahl der, also der Kommunikationsaufwand ist
einfach zu groß.
Aber für diese Situation hier kann man das zunächst mal so annehmen.
Und jetzt haben wir zwei Annahmen, unterschiedliche Annahmen.
Wir sagen, wir wollen zeilenweise sortieren, das heißt hier jeweils
aufsteigend.
Das heißt, das Element, das hier in Pn steht, soll kleiner gleich
Element Pn± sein.
Und dann wieder aufsteigend nach rechts.
Also zeilenweise sortiert und in jeder Zeile aufsteigend.
Das kann man auch anders machen.
Man kann sagen, ich möchte nicht in jeder Zeile aufsteigend, sondern
abwechselnd aufsteigend und absteigend.
Also das heißt, ich habe so eine Schlangenlinie.
Das heißt, dann nehme ich diese beiden Elemente, die rechts stehen,
die sind direkt aufeinander in der sortierten Reihenfolge.
Wenn ich mir das hier anschaue, dann sehe ich, diese beiden sind
sicherlich auch in der größeren Relation.
Aber das nächste Element liegt ja hier ganzes Ende weg.
Also das sind zwei Möglichkeiten.
Das sind aber nicht die einzigen Möglichkeiten.
Da sage ich ja noch, MEMD sei erlaubt.
Also es sei erlaubt, dass wir unterschiedliche Operationen machen
können auf verschiedenen Prozessoren.
Sie erinnern sich, SEMD, die gleichen Operationen müssten...
Wenn wir die gleichen Operationen machen müssen auf allen Prozessoren,
würde das bedeuten, wir müssten auf allen Prozessoren gleichzeitig
einen Vergleich machen zwischen den beiden Elementen links und rechts.
Dann müsste es genau identisch sein.
Wenn es MEMD ist, heißt das, es können einige etwas beim rechten
Nachbarn lesen, andere etwas beim unteren Nachbarn lesen, andere etwas
beim oberen Nachbarn lesen.
Ich kann also beliebige Kommunikation zwischen den Prozessoren
erlauben, die unterschiedlich sein mag von Prozessor zu Prozessor.
Deswegen MEMD.
Unterschiedliche Operationen in den einzelnen Prozessoren.
Jetzt hatte ich gesagt, hier die Reihenfolge.
Nochmal zu der Reihenfolge.
Das sind nicht die einzigen Reihenfolgen, die man sich vorstellen
kann.
Ich könnte auch sagen, ich habe hier mein Feld.
Mein zweidimensionales Feld.
Und ich sage meinetwegen rekursiv, alle Elemente, die hier drin
stehen, sollen kleiner sein als die Elemente, kleiner als die und
kleiner als die.
Und das Ganze mache ich rekursiv so weiter.
Auch hier und da.
Das wäre auch eine sortierte Reihenfolge.
Oder ich sage, in meinem zweidimensionalen Feld, ich möchte
meinetwegen so eine Anordnung haben.
Auch eine Möglichkeit.
Oder denken Sie sich irgendeine Hilbert-Kurve.
Hilbert-Kurven sind Kurven, die ein Objekt vollständig ausfüllen.
Eine durchgezogene Linie.
Genau das machen wir hier.
Was ich hier gerade eben gemalt habe, ist eine Hilbert-Kurve, bei der
wir durch eine Linie alle Elemente unseres zweidimensionalen Gebildes
hier verbinden.
Da gibt es verschiedenste Möglichkeiten, das anzuordnen.
Man hat manchmal Anforderungen, dass man sagt, wenn ich mir
irgendeinen Ausschnitt nehme, dann sollen in Bezug auf die Abstände
der Elemente, die jetzt hier drin liegen, da liegen jetzt irgendwelche
Elemente drin, die sollen tatsächlich auch in Bezug auf die Anordnung
der Elemente in der sortierten Reihenfolge nah beieinander liegen.
Wenn wir das bei dem zeilenweisen Sortieren anschauen, oder auch bei
dem schlangenweisen Sortieren, die liegen nicht alle nah beieinander.
Die hier zum Beispiel haben Abstand in halbe, da genauso.
Abstand klein in halbe.
Oder klein n sogar.
Das heißt, die sind relativ weit auseinander.
Und man kann auch Ordnungen finden, bei denen alle Elemente, wenn ich
irgendeinen Teil-Ausschnitt hier nehme, dann sollen die Elemente dort,
auch wenn ich annehme, ich habe tatsächlich eine Folge von 1 bis N,
natürliche Zahlen, wenn ich mir irgendeine Teilmenge raushole, dann
sollen die nicht weit auseinander liegen.
Also nur in einer konstanten Umgebung liegen.
Also die maximale Distanz der Elemente soll nicht größer sein, als die
Größe der Teilmenge hier angibt.
Das sind ganz andere Anforderungen an Sortierreihenfolgen, kann man
alles machen.
Wir beschränken uns aber auf diese beiden Fälle, zeilenweise sortiert
oder zeilenweise in Schlangenlinien.
Und man kann auch für die anderen Sortierreihenfolgen entsprechend
Sortierverfahren sich überlegen, aber die sind ein bisschen exotisch.
Jetzt haben wir also diese beiden möglichen Reihenfolgen.
Wie sieht das aus mit dem Mindestaufwand, den wir treiben müssen?
Was kann denn passieren, wenn wir hier sortieren wollen?
Zeilenweise in Schlangenlinien.
Es kann doch sein, dass wir anfangen und wir haben das Element, wir
haben deswegen Folgen von 1 bis N zu sortieren.
Dann könnte es sein, dass das Element N hier liegt und das Element 1
dort.
Und die müssen genau vertauscht werden, bei einer aufsteigenden
Sortierung.
Damit die vertauscht werden können in einem zweidimensionalen,
gitterverbundenen Feld, müssen wir dafür sorgen, dass die Elemente
hier durch entsprechende lokale Operationen rübergeschoben werden.
Das heißt, die können nur sukzessive hier durchwandern.
Und das, was wir jetzt betrachten müssen, ist einfach die Distanz der
Elemente P1 und PN.
Und die Distanz in so einem zweidimensionalen Feld ist gerade die
Manhattan -Distanz.
Das ist gerade 2 n-2.
Es ist völlig egal, ob ich hier gleich nur nach rechts laufe und dann
nur nach unten oder ob ich das irgendwie abstufe.
Egal, wie ich es mache, ich brauche 2 n-2 Operationen, um so eine
Vertauschung zu machen.
Es geht nicht anders.
Das ist die Manhattan-Distanz.
Also mindestens so viel Zeit brauchen wir auf jeden Fall, um auf einem
zweidimensionalen Feld zu sortieren.
Und jetzt schauen wir mal, wie nah wir da rankommen können.
Ob man tatsächlich diese 2 n erreichen kann.
Und wie man überhaupt das machen könnte.
Jetzt stelle ich Ihnen ein Verfahren vor.
LS-Hoch-3-Sort.
Ein Grund ist natürlich, dass ich selbst da mitgewirkt habe.
Ein anderer Grund ist, dass es wirklich sehr einfach zu verstehen ist.
Ein sehr einfaches Verfahren.
Es ist nicht das optimale Verfahren.
Es gibt Bessere.
Aber die Besseren sind wesentlich komplizierter zu beschreiben.
Und dieses ist sehr einfach zu beschreiben.
Das ist ein Verfahren unter vielen zum Sortieren auf Gittern.
Da haben sich viele Leute mit beschäftigt.
Und alle etwa um die gleiche Zeit.
Also das war von 80 bis 85 so etwa.
Und die sind übrigens alle Leute, die hier stehen, sind mittlerweile
Professoren für Informatik.
Waren alle in meiner Arbeitsgruppe damals.
Oder die waren in einer gemeinsamen Arbeitsgruppe.
Und beschäftigen sie alle noch nicht alle mit Sortierverfahren, aber
mit Algorithmen.
So, was machen wir hier?
Wir nehmen an, wir wollen in Schlangenlinien sortieren.
Also das ist das Ziel, das wir haben.
Wir wollen eine in Schlangenlinien sortierte Folge haben, auf einem
zweidimensionalen Feld.
Und unser Ansatz ist, das regressiv zu machen wieder.
Die Weide-Konker-Ansatz, die schon so oft.
Wir gehen davon aus, wir haben vier Quadranten, die wir bereits
zeilenweise in Schlangenlinien sortiert haben.
Und die wollen wir jetzt verschmelzen.
Sie sehen immer wieder diesen Merge-Sort-Ansatz im Prinzip.
Hier haben wir aber einen 4-Way-Merge, also vier Teile werden
verschmolzen.
Vorher hatten wir einen 2-Way-Merge, da wurden nur zwei Teile
verschmolzen.
Wie kann man das machen?
Das geht relativ einfach.
Wir nehmen an, dass das n sei 2 hoch r, also die Zeilenlänge sei 2
hoch r, also eine Zweierpotenz.
Damit das alles schön aufgeht mit diesem Weide-Konker-Ansatz.
Der Algorithmus läuft wie folgt.
Wir machen ein Perfect-Shuffle in jeder Zeile des Feldes.
Was ein Perfect-Shuffle ist, wissen Sie?
Wir verschieben einfach die beiden Folgen ineinander.
Und wenn wir so ein Perfect-Shuffle machen, dann heißt das doch, dass
die Elemente aus der ersten Spalte und aus diesen beiden Spalten hier,
die werden nebeneinander geschoben.
Das heißt, was wir jetzt hier sehen, diese Spalte hier ist also dahin
gewandert.
Und entsprechend haben wir jetzt nebeneinander jeweils Spalten aus
diesen beiden Hälften.
So, das ist eine Operation.
Die nächste Operation läuft so, dass wir einfach zwei dieser Spalten
nebeneinander betrachten, also insgesamt betrachten, als jeweils eine
Folge, die zu sortieren ist.
Also hier war übrigens natürlich jeweils aufsteigend in
Schlangenlinien sortiert.
Und hier entsprechend wollen wir jetzt diese Doppelspalten jeweils
aufsteigend sortieren.
Das sind jetzt Folgen der Länge 2n.
Doppelte Spaltenlänge.
Die müssen wir sortieren.
Das machen wir mit OETS.
Mit OETS wissen wir, wir vergleichen immer gerade und ungerade
Elemente.
Was heißt das denn hier auf so einer Doppelspalte?
Wenn wir ungerade haben, erste Position mit zweiter, heißt das, wir
würden jeweils solche Vergleiche machen von genau nebeneinander
liegenden Elementen.
Und in dem ungeraden Schritt, den male ich jetzt mal in das gleiche
Feld mit rein, hier hinten.
Entschuldigung, der ungerade Schritt war so, dass wir die genau
horizontal nebeneinander liegenden Elemente jeweils vergleichen.
In Schlangenlinien heißt, der eine Vergleich geht nach rechts, der
nächste geht nach links, der nächste wieder nach rechts und wieder
nach links, weil wir das in Schlangenlinien machen wollen.
Wenn wir jetzt den Even-Vergleich machen, dann werden Elemente 2, 3,
4, 5 und so weiter miteinander verglichen.
Und das heißt, wir haben gerade diesen Vergleich zu machen und den
Vergleich und den und den.
Und so wechseln sich also Zeilenvergleiche und Spaltenvergleiche
miteinander ab und das sind immer gerade benachbarte Elemente, die
hier verglichen werden.
Also ganz einfache lokale Schritte zwischen diesen Prozessoren.
Und dann wenden wir einfach OETS auf die gesamte Matrix als
Schlangenlinie an.
Also wir passen jetzt die Matrix insgesamt als eine lineare Folge auf,
so abgewickelt in Schlangenlinien und wenden darauf OETS an.
Also schön unsere abwechselnd ungeraden und geraden Paare von
Elementen werden verglichen.
Aber nur zwei Endschritte, also entsprechend der Länge von zwei
Zeilen, machen wir hier OETS-Schritte.
Und die Behauptung ist, danach ist das Feld vollständig in
Schlangenlinien sortiert.
Also die ersten Schritte, was hier passiert, ist klar, dass danach,
dass hier tatsächlich nach diesen zwei Endschritten das Feld insgesamt
in Schlangenlinien sortiert ist, das ist nicht offensichtlich.
Da muss man überlegen, dass das reicht.
Das heißt, mit zwei Endschritten kann ich ja maximal eine Folge
sortieren, die zwei Endelemente hat.
Und das heißt, der Bereich, der unsortiert sein kann, der darf nicht
zu groß sein.
Wir müssen nur mal das Zeitverhalten hernehmen.
Also nochmal hier kurz, können wir kurz überlegen, was haben wir hier
für Schritte zu machen.
Das erste ist ein Perfect Shuffle.
Ein Perfect Shuffle, da überlegen wir uns gleich, wie man das machen
kann.
Das geht also in Zeit klein n, im Prinzip.
Das Sortieren der Doppelspalten, also das hier geht sogar in Zeit n-1,
Sortieren der Doppelspalten in Schlangenlinien, das sind zwei
Endelemente in der Schlangenlinie, das heißt, das sind gerade hier
zwei Endschritte, die gemacht werden müssen.
Danach werden nochmal zwei Endschritte von OETS ausgeführt, also
insgesamt sind das 4n... Quatsch, wir haben hier...
Das n ist hier insgesamt, das stimmt nicht ganz, hier haben wir n-1,
das ist wichtig.
Das ist nicht n, sondern in diesem Fall n-1, also die beiden Folgen,
auf denen wir das Perfect Shuffle machen, haben jeweils die Länge n
-Halbe und die können wir gerade mit n-Halbe-1-Schritten vertauschen,
dass dann das Perfect Shuffle rauskommt, das zeige ich Ihnen gleich.
Aber wir können auf jeden Fall, wenn man das so zusammenzählt hier,
die 4n-Vergleiche, die gemacht werden müssen, in Schritten 2 und 3 und
nochmal ein halb n etwa, minus 1 dann, für dieses Perfect Shuffle.
Und das heißt insgesamt, da steht es nochmal, kommen wir auf 4,5n-1
-Takte.
Das ist das Perfect Shuffle, hier also nochmal alles aufgemalt.
Wenn wir unsere Elemente hier hinschreiben, also wir haben hier 1, 2,
3, 4, 5, 6, 0 und 7.
Das sind genau die Elemente, das ist das, was hier geschieht.
Und das linkeste Element beim Perfect Shuffle muss ja nicht vertauscht
werden.
Das bleibt ja, das rechteste Element bleibt auch an der Position.
Und wir müssen dafür sorgen, dass das Element 4 an diese Position
gelangt.
Das geschieht einfach durch diese Vertauschungen.
Also 4 wird mit 3 vertauscht, dann kommt es hier hin, dann wird es mit
2 vertauscht, dann kommt es da hin.
Entschuldigung, die 4 hier ist falsch.
Lassen wir das sofort wegradieren.
Die 4 muss natürlich an diese Position.
So wie es ja auch hier passiert.
Sie wandert nicht durch den Vergleich, sondern durch diese
Vertauschungsoperation an die Position.
Und die 1 sollte an diese Position, genau wie es hier auch geschieht.
Und die 3 entsprechend, die wandert durch diese Vertauschung an die
Position, durch die Vertauschung an die Position, durch die
Vertauschung an die Position.
Auch genau richtig.
Also was hier passiert ist, dass wir genau diese Vertauschungen
hinbekommen, hier haben wir die 2 und da kommt die 2 hin, die 6 kommt
da hin und die 3 kommt da hin.
Bitte?
Die 5, Entschuldigung, ja, danke.
Also, das ist 4, 5 und 6, genau.
Das ist genau diese Verschmelzung.
0, 1, 2, 3 und 4, 5, 6, 7.
Und das sind genau diese, wenn wir das jetzt nochmal aufmalen, 3 geht
darüber und die 4 geht da hin, die 5 kam da her und die 6 kam da her.
Und Sie sehen, an jeder Kreuzungsstelle dieser Linien, die ich gemalt
habe, haben wir gerade eine Vertauschungsoperation.
Und wenn Sie das Perfect Shuffle aufmalen, dann sehen Sie an den
Schnittpunkten der Linien, die dabei entstehen, gerade die Position,
wo Vertauschungen gemacht werden müssen.
Und das sind genau diese n-halbe, minus 1 Schichten von
Vertauschungen, die das Perfect Shuffle realisieren.
So, damit haben wir die 4.5n, minus 1 Takte.
Das Zeitverhalten mag ja so sein, aber ist tatsächlich korrekt.
Das müssen wir natürlich auch noch überlegen.
Warum ist das korrekt?
Wir haben zunächst mal diese Situation.
Wir haben 4 in Schlangenlinien sortierte Quadranten.
4 in Schlangenlinien sortierte Quadranten heißt, wir haben hier
irgendwelche Einsen jeweils drin.
Wir nehmen natürlich an, wir haben 0-1-Folgen, das ist klar.
Und bei 0-1-Folgen heißt das, da die in Schlangenlinien sortiert sind,
diese angefangenen Eins- oder diese unvollständigen Eins-Zeilen, die
sind entweder rechtsbündig mit Einsen gefüllt, wenn wir gerade in
einer nach rechts sortierten Zeile sind, oder linksbündig, wie das
hier zu sehen ist.
Da haben wir eine gerade andersrum, eine absteigend sortierte Zeile.
Und je nachdem, in welcher Zeile wir gerade sind, haben wir ja
absteigend oder aufsteigend, damit es in Schlangenlinien ist.
Und das heißt, wir haben hier solch eine Situation.
Es könnte also sein, dass gerade die in den übereinanderliegenden
Quadranten gleichartig gerichtet sind, diese unvollständigen Eins
-Zeilen.
Es könnte auch sein, dass sie gegenläufig angeordnet sind.
Und Sie können sich vorstellen, je nachdem, wie man das macht, treten
unterschiedliche Situationen auf.
Wir haben hier zum Beispiel eine Situation in diesem Bereich und in
dem Bereich.
Wenn wir uns das zusammenpacken, also das, was ja passieren muss, ist,
dass alle Einsen nach unten wandern.
Und hier hätten wir also Elemente nur aus diesen vollständigen Eins
-Halbzeilen, die zusammenkommen.
Und hier hätten wir in dem Bereich jeweils noch eine zusätzliche Eins
drin, die nach unten wandern muss.
Und in diesem Bereich, wenn wir uns die Situation hier anschauen, da
haben wir mindestens eine zusätzliche Eins, zusätzlich zu diesen A, B,
C oder D vollständigen Eins-Halbzeilen in jedem Quadranten.
Also wir haben in jedem Quadranten eine gewisse Zahl von vollständig
gefüllten Zeilen, eine unvollständig gefüllte Zeile maximal.
Wenn wir Glück haben, kommt das gerade hin, dass es schön aufgeteilt
ist.
Aber in der Regel werden wir hier eine unvollständige Zeile haben mit
Einsen, wo wir Nullen und Einsen haben.
Und oben drüber sind nur Nullen.
Und das, was das Ganze also charakterisiert, ist diese Verteilung der
halben Einszeilen.
Jetzt wird das Ganze ja durch den ersten Schritt, durch das Perfect
Shuffle, werden ja diese Zeilen von links und rechts nebeneinander
geschoben.
Und wenn wir uns jetzt eine Doppelspalte anschauen, wie viele Einsen
sind dann da drin?
Also in der Doppelspalte sind A plus B plus C plus D Einsen drin aus
den jeweils vollständigen Zeilen der Quadranten.
Und dann kann es sein, dass noch, da kommt also in dem Fall noch
dieser Eins dazu und die Eins und die Eins, aber aus den links oberen
Quadranten kommt keine zusätzliche Eins dazu.
Da kommen also drei zusätzliche Einsen dazu, zu diesen A plus B plus C
plus D vollständigen Zeilen.
Und damit wissen wir genau, das ist ja in allen Doppelspalten das
gleiche, dass wir A plus B plus C plus D Einsen drin haben, plus ein
paar weitere Einsen aus diesen unvollständigen Einszeilen.
Jetzt muss man sich anschauen, was da passiert.
Da gibt es zwei verschiedene Situationen.
Und zwar hängt das davon ab, welchen Wert das E hat.
Ist das E gerade?
Wir wissen, es sind genau E Einsen dort drin, plus eventuell noch ein
paar mehr aus den unvollständigen Einszeilen.
E sind es auf jeden Fall.
Wenn das E gerade ist, heißt das, nach diesem Sortieren der
Doppelspalten haben wir hier jeweils diesen Bereich vollständig
gefüllt mit Einsen.
Und das sind genau E Halbe.
Wenn das E gerade ist, dann haben wir also hier solche Einsbereiche.
Und dazu können natürlich maximal zwei Zeilen mit Null und Einsen
kommen, weil wir aus jedem Quadranten maximal eine Eins dazubekommen.
Aus diesen unvollständigen Zeilen.
Wenn wir aber aus jedem Quadranten maximal eine Eins dazubekommen,
dann heißt das, die maximale Zahl von Zeilen, in denen wir etwas
Unsortiertes haben, sind gerade zwei.
Zwei Zeilen, heißt zwei mal klein n Elemente, sind nicht sortiert.
Das heißt, mit zwei N-Schritten von OETS können wir genau diesen
Bereich, der hier angegeben ist, vollständig sortieren.
Wir wissen nicht, wo der Bereich ist, bei Null-Eins-Folgen.
Irgendwo ist er natürlich angeordnet.
Deswegen müssen wir das auf dem ganzen Feld machen.
Zwei N-Schritte.
Aber wir wissen genau, nach zwei kleinen N-Schritten von OETS ist der
hier eingerahmte Bereich, diese beiden Zeilen, auf jeden Fall
sortiert.
Der Rest oben drüber und unten drunter ist sowieso sortiert.
Das heißt, insgesamt ist es sortiert.
Zwei kleinen N-Schritte von OETS reichen aus, um insgesamt das Feld zu
sortieren.
Jetzt ist die Frage, was passiert, wenn das E ungerade ist.
Jetzt, wenn das E ungerade ist, dann wissen wir, der Bereich sieht
nicht so schön aus wie vorher, sondern wir haben so einen Bereich.
Das sind jetzt unsere E-Einzelnen in jeder Doppelspalte.
Und jetzt können auch hier natürlich bis zu vier Einzelnen dazukommen
aus diesen vier Quadranten.
Und dann haben wir ein Problem.
Wenn nämlich vier Einzelnen dazukommen, dann kann es sein, dass wir
keine Eins haben oder bis zu vier Einzelnen.
Wenn diese Unterschiede von null zusätzlichen Einzelnen bis vier
zusätzlichen Einzelnen auftauchen, dann könnte es sein, dass wir hier
drei Zeilen haben, die nicht sortiert sind.
Und dann reichen zwei N-Schritte nicht aus.
Also müssen wir das ein bisschen genauer anschauen.
Wenn wir das ein bisschen genauer anschauen, stellen wir Folgendes
fest.
Es gibt zwei verschiedene Situationen.
Wenn es passiert, dass es eine Doppelspalte gibt ohne eine zusätzliche
Eins.
Das ist die Situation, die ich hier schon markiert hatte.
Diese Situation hier.
Hier haben wir eine Doppelspalte.
Die ist hier gar nicht markiert.
Entschuldigung.
Hier hätten wir eine Spalte, wo keine zusätzliche Eins kommt, aber auf
der linken Hälfte, in diesem Beispiel, ist überall mindestens eine
Eins da.
Also das ist nicht die Situation.
Es gibt eine Doppelspalte ohne zusätzliche Eins.
Das würde bedeuten, dass wir in der linken und in der rechten Hälfte
unseres Feldes zwei korrespondierende Spalten haben müssen, bei denen
keine extra Eins auftaucht.
Und nun muss man sich überlegen, welche Situation haben wir
eigentlich, wenn das E ungerade ist.
Wenn das E ungerade ist, dann wissen wir etwas über die Werte von A,
B, C und D.
Die können nicht alle gerade sein.
Die können nicht alle ungerade sein.
Es kann auch nicht sein, dass zwei gerade sind und zwei ungerade.
Sondern es kann sein, dass eins ungerade ist und der Rest gerade.
Oder drei ungerade und der Rest gerade.
Und wenn wir das, also eins gerade, dann wissen wir in dem Augenblick,
wie diese unvollständigen Einszeilen hier angeordnet sind.
Und sobald es zwei Situationen, also zwei korrespondierende Spalten
gibt, die jeweils keine zusätzliche Eins brauchen, dann kann man sich
überlegen, dann gibt es nicht die Situation, dass sich zwei andere
korrespondierende Spalten haben, in denen ich vier zusätzliche Einsen
kriege.
Dann können es maximal drei sein.
Weil die unterschiedlich angeordnet sind.
Und wenn diese Situation auftaucht, wir haben für eine Doppelspalte
keine zusätzliche Eins, d.h.
wir hätten hier nur diese Eins von diesen E-Einsen.
Alle anderen haben maximal drei Einsen zusätzlich, dann sind wir also
in diesem Bereich mit unseren zusätzlichen Einsen.
Und wir haben zwei Zeilen insgesamt, die nicht sortiert sind.
Oben drüber stehen nur Nullen.
Und die andere Situation ist, dass in jeder Doppelspalte mindestens
eine zusätzliche Eins auftaucht, dann sind aber nur diese Zeilen hier
unsortiert, weil wenn wir überall mindestens eine extra Eins haben,
das ist die Situation, die wir hier sehen, das ist also übrigens die
Situation, die wir hier in diesem Bild sehen, da hätten wir in jedem
Fall mindestens eine Eins in jeder Doppelspalte.
Dann hätten wir eine weitere sortierte Zeile, nämlich diese Zeile hier
wäre jetzt auch sortiert, weil wir dort mit Einsen aufgefüllt haben.
Und oben drüber liegen maximal zwei unsortierte Zeilen.
Für maximal zwei unsortierte Zeilen wissen wir aber, dass dafür die 2N
-Schritte OETS ausreichen.
Und damit ist auch hier am Ende von den 2N-OETS-Schritten die gesamte
Folge sortiert.
Und wir haben also gezeigt, also das war ja das, was wir zeigen
mussten, Schritt 3 reicht aus, um insgesamt eine sortierte Reihenfolge
zu bekommen.
Das haben wir jetzt erreicht.
Und damit haben wir insgesamt das LS hoch 3 sort.
Zunächst mal für N kleiner gleich 2, nehmen wir einen trivialen
Algorithmus, irgendwelche Vergleiche, also 2 mal 2 Feld, 4 Elemente,
können Sie ganz einfach vergleichen mit, ich glaube, es reichen 3
Vergleiche aus.
Und dann für N größer 2, für größere Felder, macht man das Ganze
rekursiv.
Und hat dann entsprechend diesen Ansatz.
Wir haben hier 4, ok, 4 Schritte brauchen wir, 4 Vergleiche für unsere
2 mal 2 Felder.
Und wenn wir jetzt das rekursive Verfahren anwenden, dann haben wir
jeweils Quadranten der Größe N halbe Kreuz N halbe, bei denen machen
wir das rekursiv.
Und anschließend noch 4.5 N Schritte, eigentlich minus 1, die minus 1
habe ich jetzt hier einfach ignoriert.
Dann kommen wir auf insgesamt maximal 9 N minus 14 Schritte.
Das Ganze kann man ein bisschen verbessern und kommt dann auf etwa 7 N
Schritte.
Dann hat man gesehen, die untere Schranke ist 2 N und hier sind wir
bei 7 N.
Wir werden nächstes Mal eine untere Schranke zeigen, die liegt bei 3
N.
Und das beste Sortierverfahren, das es gibt, liegt auch bei 3 N.
Das ist nicht unser Verfahren, unser Verfahren ist bei 7 N, also etwas
mehr als Faktor 2 weg von dem besten Verfahren.
Aber das Ganze gilt auch noch nur bis zu einem eingeschränkten
Berechnungsmodell.
Das ist durchaus praxisrelevant und wenn man das ein bisschen
verallgemeinert, kommt man sogar recht nah an 2 N ran.
Was ziemlich erstaunlich ist, dass man das schaffen kann.
Das war's für heute.
Vielen Dank.
Wir sehen uns in einer Woche wieder.
Beziehungsweise in einer Woche ist der 13.
Juni und am 13.
Juni sind sowohl Frau Mostergehm als auch ich in Hannover.
Ich würde sagen, Sie haben von allen die Mailadresse, Frau Mostergehm.
Haben Sie nicht?
Dann schreiben wir das auf die Homepage, was passiert, wie wir das
machen, wer mich hier vertritt.
Oder ich muss die Vorlesung, wir müssen einen Sondertermin aufmachen
für die Vorlesung.
Könnten Sie denn auch zum Beispiel am Montag...