So, es sind doch noch ein paar gekommen.
Willkommen zur dritten Übung.
Schön, dass Sie trotz des schönen Wetters Ihren Weg hierher gefunden
haben.
Es sind nicht mehr so viele da, aber immer noch genug.
Sie werden es nicht bereuen.
Also wir beschäftigen uns heute nochmal mit Insertion Sort.
Wir bauen da eine kleine Optimierung ein, die wir so in der Vorlesung
nicht hatten, um einen Fachbegriff zu motivieren und zu verstehen, den
Sie hier in Algorithmen 1 mitnehmen sollen.
Dann beschäftigen wir uns noch mit adaptivem Sortieren.
An der Stelle versuchen wir zu messen, wie chaotisch eine Liste von
Zahlen sein kann und führen da verschiedene Möglichkeiten ein, das
Chaos zu messen, indem wir Anzahl der Inversionen zählen, Anzahl der
Runs und Anzahl der Removals, was das genau bedeutet, zeige ich mit
Beispielen.
Und dann analysieren wir nochmal ein paar
Sortieralgorithmen relativ zu diesen,
analysieren den Zusammenhang zu den Zahlen, die wir hier oben neu
gelernt haben.
Als nächstes beschäftigen wir uns mit der schnellen Mediansuche für
Quicksort.
Wir werden sehen, dass man, um den Median zu finden, eine Liste nicht
erst sortieren muss, sondern dass man den auch so finden kann.
Machen wir ein Beispiel.
Dann schauen wir an, was in Ihrem Alltag als Informatiker, wie Sie da
sortieren werden.
Da werden Sie höchstwahrscheinlich keine Sortieralgorithmen selbst
schreiben.
Da sage ich kurz was dazu.
Und am Ende wollte ich mir eigentlich was anhören, mit Ihnen zusammen
was anhören.
Da irgendwie das Audiokabel nicht funktioniert, müssen wir das anders
machen.
Vielleicht klappt es mit dem Mikrofon.
Müssen wir mal ausprobieren nachher.
Gut, aber fangen wir erstmal mit Insertion Sort an.
Hier ist so ein Beispiel für Sortierschritte in Insertion Sort.
Hier wäre quasi so ein Array.
Rot markiert sind immer die Elemente, die schon sortiert sind.
Grün ist quasi so ein Zeiger in der Liste.
Und hier sieht man an der Stelle 1, wir fangen mit einer leeren Liste
an, wo am Ende dann quasi die sortierte Liste drinstehen soll.
Und mit einer unsortierten Liste.
Und wir fügen dann schrittweise an der richtigen Stelle ein.
Das Ganze geht auch in place.
Hier muss man jetzt nichts vertauschen, aber hier an der Stelle, wenn
wir uns hier die 1 anschauen, dann bewegen wir die hier nach vorne,
indem man hier einzelne Vertauschungen vornimmt.
Hier zum Beispiel die 1, die würden wir jetzt erstmal mit der 7
vertauschen und dann mit der 4 bis an der richtigen Stelle ist.
Und so geht das Ganze dann auch in place, also ohne zusätzlichen
Speicherplatz zu verbrauchen.
Genau dieses Move AI to the right place, das haben wir hier nochmal
ausformuliert.
Das sind hier die paarweisen Vertauschungen, die wir vornehmen müssen.
Wir haben hier diesen einen Cursor, wir gehen einmal bis ganz ans Ende
und wenn wir hier einmal sehen, die Invariante wäre jetzt verletzt,
dann tauschen wir das an die richtige Stelle, sodass die dann im
nächsten Schritt wieder gilt.
Also hier Flip, Flip, Flip, bis wir angekommen sind.
Und jetzt beschäftigen wir uns heute mit diesem J Größe 1 an der
Stelle.
Also wir haben hier zwei Abbruchbedingungen.
Das eine ist, wir sind an der richtigen Stelle angekommen und das
andere ist, wir laufen nicht übers Ende hinaus.
Hier haben wir die Möglichkeit eine Mikro-Optimierung zu machen, indem
wir sagen, wir sorgen dafür, dass an der ersten Stelle immer das
kleinste Element der gerade betrachteten Sequenz steht.
Wenn das nämlich gilt, hier ist nochmal in grün, die Waldschleife von
gerade eben, brauchen wir diese Überprüfung auf den Index nicht mehr.
Ich gehe nochmal kurz zurück.
Zurück ist die andere Richtung.
Also hier diese Überprüfung, laufe ich über den Anfang raus, brauchen
wir nicht mehr, wenn quasi hier unten, wenn am Anfang immer das
kleinste Element steht und das stellen wir hier außerhalb der Schleife
sicher.
Das heißt, wir prüfen das einmal und dann, während wir am Flippen
sind, müssen wir das dann nicht mehr prüfen.
Dieses A1, über das wir nicht hinauslaufen können, weil die
Abbruchbedingung da sowieso schon gilt, nennt man Sentinel-Element.
Das ist sozusagen ein Wächter, der dafür sorgt, dass man nicht mehr
daran vorbeiläuft.
Genau, das kann man an einigen Stellen machen, wenn man solche Listen
traversiert und eine Abbruchbedingung hat, die sich aus mehreren
Komponenten zusammensetzt, kann man sich überlegen, ob man dafür
sorgt, diese Abbruchbedingung so zu reduzieren, dass sie auf jeden
Fall für den Grenzfall gelten.
Genau, also das ist im Prinzip, der Begriff, den Sie mitnehmen sollen,
ist Sentinel.
Sie sollten verstehen, warum man sowas macht und wo man ihn einsetzt.
Dann kommen wir zum nächsten Thema.
Wir wollen Chaos messen.
Das wäre jetzt eben hier beim Sortieren ein Maß dafür, wie unsortiert
eine Liste ist.
Wir haben jetzt hier zwei unsortierte Folgen, so als Motivation.
Hier an der Stelle haben wir nur zwei Paare, an denen eine
Vertauschung vorgenommen werden muss.
Und hier haben wir im Vergleich dazu ein ziemliches Chaos.
Und das können wir jetzt messen, wenn wir jetzt die Anzahl der
Inversionen zählen.
Also wir wollen hier, sagen wir mal, zwei haben, weil hier ist die
Zwei größer als die Drei.
Also hier gibt es eine Inversion und hier gibt es nochmal eine.
Und jetzt definieren wir die Anzahl Inversionen als die Anzahl Paare
in so einer Menge.
Hallo, schön, dass Sie auch noch hergefunden haben.
Die Anzahl Paare, die zu vertauschen sind.
Also jetzt können wir im Prinzip hier dieses ziemliche Chaos messen.
Wie viel Chaos ist da drin?
Gemessen an der Anzahl der Inversionen.
Für die Acht haben wir hier genau sieben Inversionen, weil Acht gehört
eigentlich an den Schluss.
Also an der Stelle haben wir schon mal sieben.
Für die Zwei gibt es nur eine Inversion, mit der Eins sind wir bei
Acht.
Für die Sieben gibt es dann wieder fünf Inversionen, weil die Sieben
größer ist als alle danach folgenden.
Jetzt sind wir bei 13.
Für die Eins gibt es hier dann keine Inversionen mehr, das hatten wir
hier alles schon.
Für die Fünf gibt es nochmal zwei.
Und für die Sechs gibt es nochmal zwei.
Also sind wir bei 17 Inversionen.
Also Chaoszahl 17, hier Chaoszahl 2, kommt ungefähr hin mit unserer
Intuition.
Also kann man hier verwenden.
Zweite Möglichkeit, wenn wir jetzt hier mit Inversionen drangehen
würden, was hätten wir?
Da hätten wir jetzt hier Inversionen 6 mal 4, sind 24 Inversionen.
Dafür, dass die Folge eigentlich fast sortiert ist.
Also an der Stelle passt jetzt der Begriff der Inversion nicht mehr zu
unserer Intuition, über die Anzahl oder Menge an Chaos.
Das motiviert uns quasi hier nochmal eine zweite Zahl einzuführen.
Wir zählen die Anzahl der Runs.
Die Anzahl der Runs ist die Anzahl der Sortierten Teillisten.
Das wären jetzt hier auch wieder zwei.
Eine weitere Möglichkeit, das Chaos zu messen, wäre die Anzahl der
Removals zu zählen.
Also die kleinste Anzahl an Elementen, die ich rausnehmen muss, damit
ich am Ende eine sortierte Liste übrig habe.
Das wären hier eben auch zwei an der Stelle.
Genau, das heißt hier zum Beispiel hätte man dann auch zwei Removals,
aber drei Runs.
Inversionen hätten wir, ich glaube, das sind hier sechs und an der
Stelle dann noch mal 16.
16 Inversionen, ja, also Inversionen passt da nicht so ganz.
Okay, die Idee ist jetzt, jetzt können wir ungefähr messen, wie
chaotisch eine Liste ist.
Können wir jetzt unsere Algorithmen so analysieren, dass wir schauen
können, ist die Laufzeit unserer Algorithmen ein bisschen abhängig von
der Menge an Chaos, die da drin steckt in der Liste.
Und das wollen wir uns jetzt genauer anschauen.
Also normalerweise messen wir immer abhängig von der Eingabegröße.
Jetzt messen wir eben n, da ist die untere Schranke, Omega n, Log n.
Jetzt wollen wir mal abhängig von so einer Chaoszahl, der Anzahl der
Inversionen oder sowas, unsere Komplexität, unsere Laufzeit bestimmen.
Genau,
da hat man alles gesagt, was wir hier auf der Folie haben.
Genau, also der Insertion Sort.
Insertion Sort, da ist der Zusammenhang eigentlich relativ klar, weil
beim Insertion Sort bin ich ja tatsächlich einzeln am flippen.
Also ich bin halt an irgendeiner Stelle und dann sortiere ich
paarweise ein Element nach vorne.
Das heißt, da ist relativ deutlich, dass die Laufzeit von der Anzahl
der Inversionen abhängig ist.
Und wenn wir jetzt die erwartete Laufzeit bestimmen wollen, in
Abhängigkeit von der Anzahl der Inversionen, können wir einfach das
Problem verschieben, indem wir die erwartete Anzahl an Inversionen in
einer Folge berechnen.
Dazu nehmen wir uns erstmal alle n-Fakultät-Permutationen her.
Und schauen uns im Prinzip an, wie viele Inversionen sind denn jetzt
in den einzelnen Permutationen drin.
Also der beste Fall ist, die ist schon sortiert, dann gibt es keine
Inversion.
Wenn alles umgekehrt sortiert ist, haben wir n über zwei Inversionen.
Und jetzt schauen wir mal, wie wir den Erwartungswert dafür ausrechnen
können.
Wir nehmen uns so eine Zufallsvariable her, die 1 ist, wenn zwischen i
und j eine Inversion in der gegebenen Permutation Sigma ist.
Und ansonsten ist die 0.
Und dann haben wir hier die Gesamtzahl der Inversionen, können wir
dann berechnen, indem wir für alle i, j, bei denen i kleiner als j
ist, diese Inversionen zusammenzählen.
Also wir betrachten hier quasi alle Paare, die nacheinander kommen.
Also das i kleiner als j ist entscheidend.
Wir laufen aber mit i und j komplett über das ganze Quadrat sozusagen.
Jetzt wollen wir hier den Erwartungswert rechnen.
Der Erwartungswert von der Summe von Elementen ist die Summe des
Erwartungswertes der Elemente.
Das haben wir unten stehen.
Jetzt haben wir das ganze Problem reduziert auf ein einzelnes Paar.
Da alle Permutationen gleich wahrscheinlich sind, haben wir hier quasi
ein Halb stehen.
Das heißt, wir können hier diese Summe wieder auflösen.
Das sind im Prinzip n über zwei x, i, j haben wir hier drin.
Das ist überall ein Halb.
Das heißt, wir können das relativ schnell auflösen und sehen dann
hier, dass wir etwas Quadratisches haben.
Also wir haben hier beim Insertion Sort auch abhängig von den
Inversionen einen quadratischen Zusammenhang.
Ja, das wollte ich mal zeigen.
Beim Merge Sort ist es ein bisschen schöner.
Wenn wir Merge Sort in Abhängigkeit von Runs stellen, können wir uns
echt vorstellen, ein gutes Ergebnis zu kriegen, gerade bei der Liste.
Da müssen wir im Prinzip eigentlich nur einmal teilen.
Vielleicht zweimal, je nachdem, wo die Null hinfällt.
Auf jeden Fall können wir bei Merge Sort sagen, wir gucken erstmal,
ist das überhaupt ein Run, also ist das schon sortiert, dann brauchen
wir gar nicht mehr weiter aufteilen.
Merge Sort haben Sie im Kopf, oder?
Also ich teile quasi auf, bis ich irgendwie nur noch eine elementige
Liste habe, die sortiert sind und dann merge ich wieder.
Das heißt, hier teile ich einfach nicht mehr weiter auf, wenn ich
sehe, ich habe einen Run.
Genau, das heißt, wir haben hier was in Abhängigkeit von Runs.
Jetzt gibt es hier nochmal eine kleine Rechnung.
Wir wollen uns ausrechnen, wenn wir jetzt wirklich wieder alle
Permutationen betrachten, wie viele Runs gibt es denn da.
Jetzt definieren wir uns hier erstmal ein Hash K, das die Anzahl der
Permutationen mit K Runs angibt.
Das N ist festgegeben.
Das heißt, wir sehen hier zum Beispiel drei Runs.
Jetzt gucken wir, unser kleinster Fall ist, wir haben einen Run.
Unser Worst Case ist, wir haben N Runs.
Das ist quasi, wenn alle umgekehrt sortiert sind.
Das heißt, unsere Grenzfälle kommen einmal vor und jetzt teilen wir
quasi auf in solche Traditionen.
Wir haben hier einen Run sortiert.
Dann gucken wir, was hat alles zwei Runs.
Das sind dann N verschiedene.
Quasi alle Möglichkeiten, eine Liste einfach zu vertauschen, sodass
man zwei Runs hat.
Und die legen wir jetzt alle nebeneinander.
Also wir haben auf der einen Seite die sortierte Liste, auf der
anderen Seite die inverse Liste.
Und dazwischen gibt es im Prinzip die Anzahl der Runs.
Und da packen wir unsere Permutationen so rein.
Es ist im Prinzip so eine Art und Weise, die Permutationen zu ordnen.
Wir sehen, dass es hier so eine Bijektion gibt.
Das ist genau spiegelbildlich.
Das ist hier hergeleitet.
Also wenn ich jetzt hier sage, hier kommen alle mit einem Run rein,
hier kommen alle mit zwei Runs rein, hier kommen alle mit drei Runs
rein.
Dann ist es genau von der Anzahl her inverse zu dem.
Wenn ich sage, hier kommen alle mit N Runs rein, mit N-2 Runs, mit N-3
Runs, spiegelt sich genau.
Und das ist hier hergeleitet, das sieht man dann hier unten.
Das bedeutet, wenn hier steht sharp K gleich, sharp N-K plus 1.
Jetzt will ich den Erwartungswert ausrechnen.
Und diesen Zusammenhang, das ist quasi gespiegelt, den brauche ich
jetzt gleich.
Das war jetzt noch Vorarbeit.
Also was haben wir jetzt?
Die Erwartungswerte für die Anzahl der Runs ist die Summe mal der
Auftrittswahrscheinlichkeit einer bestimmten Permutation mal der Runs
in dieser Permutation, also die Anzahl der Runs da drin.
Und das haben wir im Prinzip genau ausgerechnet.
Das ist im Prinzip hier für,
genau, also sharp K ist ja die Anzahl der Elemente mit K Runs.
Das immer relativ zu der Gesamtzahl der Elemente.
Also Elemente, damit meine ich Permutationen.
Und das im Prinzip multipliziert mit dem jeweiligen K, das wäre dann
der Erwartungswert.
Genau, das kann ich jetzt natürlich dann auch nochmal ändern.
Also ich kann dieses sharp K ersetzen.
Wir hatten ja schon gesehen, das ist symmetrisch, also quasi nochmal
der gleiche Term von der anderen Seite ausgedrückt.
Und dann kann man im Prinzip hier ausrechnen.
Der Trick an der Stelle ist jetzt, dass ich jetzt hier zweimal den
Erwartungswert ausrechne und beide Darstellungen verwende.
Einmal die Darstellung mit diesem hash K und einmal die Darstellung
mit diesem hash N-K.
Das ist genau im Prinzip von der anderen Seite betrachtet.
Da ich hier eine Äquivalenz habe, kann ich an der Stelle auch nochmal
zurücktauschen.
Also hier benutze ich dann auch nochmal die Äquivalenz.
Und dann bekomme ich einen ganz netten Term hin.
Das heißt hier am Ende habe ich dann sowas da stehen.
Da kommt ein linearer Zusammenhang raus.
Ich glaube jetzt wird es aber spannender.
Splitsort ist mal ein ganz anderer Algorithmus.
Haben Sie wahrscheinlich noch nicht gesehen.
Hier teilen Sie erstmal das Array A in drei Arrays auf.
Und Sie gehen im Prinzip über diese Removals bzw.
Inversionen.
Also wir gucken uns quasi an, wo sind die Abstiege.
Am Ende von jedem Run gibt es immer so einen Abstieg.
Und überall da wo ein Abstieg ist, nehmen wir das große Element,
packen es in A-G, das kleine Element und packen es in A-S.
Und dann haben wir am Ende drei Folgen.
Also wo sind die Abstiege?
Ein Abstieg ist hier nach dem dritten Element.
Ein Abstieg hier nach dem sechsten.
Das heißt wir haben im Prinzip zwei Elemente, die wir hier rausnehmen
wollen.
Das eine, die großen kommen in A-G.
Und die kleinen kommen in A-S, in die Menge A-S rein.
Bis dahin ist jetzt quasi sortiert.
Jetzt bleiben in A übrig alle grünen.
Also die grünen Säulen verbleiben in A.
Und dann gucken wir wieder, wo sind die Abstiege.
Und jetzt haben wir den Abstieg zwischen diesem ursprünglich mal
fünften, jetzt dritten Element und dem darauf folgenden grünen
Element, das deutlich kleiner ist.
Genau, jetzt sind sie auch im Prinzip markiert.
Also das größere ist jetzt blau geworden, das kleinere rot.
Die entfernen wir aus dieser Liste und packen sie in unser A-G
beziehungsweise A-S.
Und am Ende gibt es keine Abstiege mehr, das heißt der Rest verbleibt
in A.
Am Ende ist im Prinzip A in der sortierten Liste übrig geblieben.
Und für den Rest machen wir dann nochmal das Gleiche.
Also dann kommt im Prinzip die Rekursion.
Dann machen wir hier nochmal Split damit und Split damit.
Bis wir im Prinzip bei einer sortierten, kleinsten Liste der Größe 1
angekommen sind.
Im Austritt aus der Rekursion gibt es dann nach oben hin wieder Merge
-Operationen.
Und dann haben wir eine sortierte Liste.
Genau, das ist im Prinzip Split Sort.
Das, was habe ich gelesen, asymptotisch optimal ist bezüglich Removals
und Inversionen.
Jetzt kommen wir zur schnellen Mediansuche für Quick Sort.
Das ist neu, Ihre Tutoren hatten das noch nicht in der Übung.
Die habe ich jetzt gerade schnell mal aus dem Boden gestampft, weil
man tatsächlich den Medien relativ effizient bestimmen kann.
Nochmal eine kurze Wiederholung zu Quick Sort.
Die Laufzeit von Quick Sort ist ja abhängig von dem Pivot-Element.
Also ich nehme ja immer so ein Pivot-Element raus und dann betrachte
ich quasi auf der einen Seite alle, die kleiner sind und auf der
anderen Seite alle, die größer sind als mein Pivot-Element.
Dann habe ich das Problem schön zerteilt in zwei Teilprobleme und dann
mache ich das Ganze wieder so lange, bis ich ein triviales Problem
habe und führe dann die Lösungen zusammen am Ende.
Und hier hängt die Laufzeit ganz stark davon ab, was für ein Pivot
-Element ich habe.
Also wenn ich immer das Minimum oder das Maximum erwische, habe ich an
der Stelle die Worst-Case-Laufzeit.
Weil ich die Liste jedes Mal im Prinzip nur um eins verkleinere.
Der Best-Case, die End-Log-End-Laufzeit, den kriegen wir leider nur,
wenn wir jedes Mal auch wirklich den Median erwischen.
Wenn wir jetzt aber anschauen, der Median ist das mittlere Element der
schon sortierten Liste.
Könnte man Schlussfolgern an der Stelle, dass das nicht möglich ist.
Wir sind gerade beim Sortieren und sollen jetzt schon wissen, was der
Mittelpunkt der sortierten Liste ist.
Geht aber auch ohne zu sortieren.
Also wenn man sich überlegt, es muss ja nicht die ganze Liste sortiert
sein.
Ich muss nur wissen, die Hälfte ist kleiner und die andere Hälfte ist
größer.
Aber die müssen nicht sortiert sein.
Das heißt, es ist schon weniger Aufwand.
Und wie man jetzt dahin kommt, das möglichst effizient zu suchen, da
gehen wir jetzt mal schrittweise ran.
Also wir suchen das Element mit Rang N halber.
Ich habe jetzt mal noch solche Glammern drum gesetzt, damit es gerade
wird, falls wir einen ungeraden Fall haben.
Aber wir suchen das mittlere Element.
Wir haben jetzt hier einen Algorithmus Select, der bekommt diesen Rang
mit rein.
Und der ist rekursiv, also den Rang passen wir unter Umständen jetzt
nochmal an.
Aber schauen wir mal erst, wie es weitergeht.
Wir müssen auch hier erstmal ein Pivot-Element suchen bei diesem
Algorithmus.
Machen wir mal, suchen wir im Prinzip zufällig ein Element raus.
Und was machen wir jetzt?
Jetzt teilen wir auf, auch wieder so wie bei Quicksort selber.
Wir teilen auf in eine Liste von kleineren Elementen und eine Liste
von größeren Elementen.
Und dann gucken wir am Ende, ja das geht linear.
Einmal alle durchvergleichen, zack, aufgesplittet.
Wenn jetzt die Länge der kleineren Liste, also L ist quasi die Liste
der kleineren Elemente, R ist die Liste der größeren Elemente, wenn
die Liste der kleineren Elemente jetzt so groß ist wie unser R, dann
haben wir es genau gesplittet, dann kennen wir schon unseren Median.
Wenn jetzt das L aber größer ist, dann haben wir irgendwie weiter
hinten gesplittet, dann lassen wir R weg, dann schauen wir uns nur
noch L an.
Und das ist im Prinzip der Trick dabei, dass wir hier ein ganzes Stück
einfach wegfallen lassen können, das wir nicht mehr in der
Medianberechtigung berücksichtigen, weil wir im Prinzip nach diesem
bestimmten Rang suchen.
Wenn jetzt unser rechtes Stück größer ist als das linke Stück, dann
müssen wir im rechten Stück nach dem Median suchen, da müssen wir dann
nochmal das R anpassen, weil es ist ja dann nicht mehr am Rang N
halbes, sondern an der früheren Stelle, weil wir links schon was
weggeschnitten haben.
Also im Worst-Case kriegen wir da jetzt noch nichts so Überzeugendes
hin, weil wir immer noch so eine komische Pivot-Element-Geschichte da
drin haben, die eben einfach im Worst-Case immer nur an der Seite im
Scheibchen abschneidet, wodurch die Rekurrenzgleichung im Prinzip so
aussieht.
Wir haben immer so Aufwand O von N hier, um die Liste zu zerteilen und
dann eben im Worst-Case einfach L minus 1.
Das heißt, wir haben hier N log N als Laufzeit und das möchten wir
gerne besser haben.
Jetzt analysieren wir mal, was wir machen können.
Also zum einen können wir eine erwartete Laufzeit ausrechnen, die
besser aussieht.
Wie machen wir das?
Wir überlegen uns folgendes.
Das ist jetzt ein Trick.
Wenn wir so eine Liste haben, dann überlegen wir uns, mit welcher
Wahrscheinlichkeit liegt eigentlich das Pivot-Element in den Rändern
und mit welcher Wahrscheinlichkeit liegt es in der Mitte.
Das heißt, wir nehmen jetzt die Ränder von der sortierten Liste, also
quasi 25% auf der einen Seite und 25% an der anderen Seite und
schneiden die ab.
Und dann können wir sagen, okay, also das Pivot-Element, also die
Wahrscheinlichkeit dafür, dass unser Pivot-Element in diesen Rändern
liegt, ist 50%.
Die Wahrscheinlichkeit dafür, dass es nicht in diesen Rändern liegt,
ist auch 50%.
Das haben wir schön aufgeteilt.
Und damit machen wir weiter.
Wir modifizieren jetzt die Rekurrenzgleichung von da oben und sagen
dann, eigentlich haben wir diesen Worst-Case nur in 50% der Fälle, da
liegt es irgendwo am Rand.
Ohne das jetzt genauer zu sagen, aber halt eben in den Rändern, in
denen der Worst-Case auch liegt.
Und in 50% der Fälle liegt es irgendwo in der Mitte und da kann ich
quasi mindestens ein Viertel wegschneiden.
Da ich quasi hier immer aufteile, quasi in links und rechts, schneide
ich im Prinzip mindestens ein Viertel weg von meinen Enden.
Das heißt, ich habe hier in der Rekurrenzgleichung 3 Viertel N stehen.
Das wären quasi die anderen 50% der Fälle für die erwartete Laufzeit
jetzt.
Jetzt kann ich das Ganze nochmal weiter nach oben abschätzen, indem
ich sage, das Minus 1 nehme ich jetzt hier raus und dann ziehe ich das
auf die andere Seite.
Dann steht im Prinzip sowas da, hier steht immer noch das Gleiche.
Wir sind bei Zeile 4.
Und in Zeile 5, die ist im Prinzip so entstanden, dass man jetzt
einfach nochmal mit 2 durchmultipliziert, dass dieses 0,5
verschwindet.
O von N mit 2 multiplizieren, geht dann halt unter, ist immer noch
linear.
Und was wir jetzt im Prinzip sehen ist, wir teilen das N stärker auf,
als wir den Suchraum,
als wir rekursive Calls haben, wodurch wir jetzt laut Mastertheorem
eine lineare Laufzeit bekommen.
Genau, also erwartete lineare Laufzeit ist schon mal echt gut.
Können wir das auch deterministisch machen?
Ja, das geht, das werde ich kurz anreißen, aber jetzt dann nicht
beweisen, weil das ein bisschen komplex war.
Also, wir können dafür sorgen, dass das Pivot-Element nie in dem
ersten und letzten Viertel liegt.
Und das ist jetzt auch nochmal ein toller Trick, wir handeln uns da
ein paar große Konstanten ein, aber wir kommen am Ende dann auf eine
Linearzeit.
Und zwar gehen wir so vor, dass wir diese ganze Liste in Fünferblöcke
unterteilen.
Also, wir nehmen solche Blöcke von 5 Elementen und sortieren jeden
dieser Blöcke.
Ein Block zu sortieren, der eine feste Länge von 5 hat, das braucht
eine konstante Laufzeit.
Also, hier kann man nachschauen, 7 Vergleiche braucht man, um so einen
Block von 5 Elementen zu sortieren, dann sind wir fertig.
Das heißt, wenn wir jetzt jeden dieser Blöcke sortieren, haben wir im
Prinzip in Linearzeit alle Blöcke sortiert.
Wir haben n Fünftel Blöcke mal 7 Vergleiche, das heißt wir haben n
Fünftel Fünferblöcke sortiert.
Jetzt nehmen wir aus jedem dieser Fünferblöcke das mittlere Element
raus, das heißt dann haben wir alle Mediane, jeden Fünferblocks.
Und was wir dann brauchen, ist den Median.
Okay, das ist jetzt rekursiv und deswegen ist es auch schwer zu
analysieren, weil wir jetzt an der Stelle von allen Medianen auch
wieder den Median brauchen und dann kommen wir quasi wieder bei
unserer anderen Funktion an.
Allerdings kann man zeigen, dass wir dann eine lineare Laufzeit haben.
Ja, soviel zu Algorithmen heute.
Jetzt wird es ein bisschen entspannter zum Schluss hin.
Normalerweise schreiben Sie keine Sortieralgorithmen in der Praxis.
Sortieralgorithmen eignen sich gut, um Konzepte der Algorithmik zu
verstehen und einzuführen.
Allerdings werden Sie in der Praxis wahrscheinlich hochoptimierte
Sortieralgorithmen aus der Laufzeitbibliothek Ihrer Wahl aussuchen.
Wir haben hier zum Beispiel in C++ ist implementiert eine Mischung aus
Quicksort, Heapsort und Insertionsort.
Das Kommando hierfür heißt standardsort und Sie geben hier zwei
Iteratoren auf eine Liste rein.
Es gibt auch einen stabilen Sortieralgorithmus, das sieht man hier
nochmal.
Können Sie nachschauen im Internet.
Java hat zwei verschiedene Sortieralgorithmen.
Da gab es auch Beweise dazu, da haben auch Mitarbeiter von unserer
Fakultät mitgearbeitet.
Das sind hier die Links, können Sie auch mal nachschauen, was es dazu
gibt in Java.
Und das ist im Prinzip eigentlich in der Praxis das, was Sie dann auch
verwenden werden.
Zum Schluss nochmal was Fröhliches.
Timo Bingmann, oben bei Sanders, können Sie mal besuchen, gucken wie
er aussieht.
Der hat hier das Sound of Sorting verfasst und visualisiert, kann man
sich bei YouTube anschauen.
Leider konnte ich den Klang jetzt nicht anstellen, ich hoffe, dass das
irgendwie funktioniert.
Hört man das?
Ist jetzt egal, gucken Sie es sich zu Hause an.
Im Prinzip ist es aber schon mal ganz interessant zu sehen, wie das
dann tatsächlich im Speicher aussieht, wenn man so einen Algorithmus
laufen lässt.
Quicksort sieht man hier.
Hier auch wieder, wie der Suchraum schön aufgeteilt wird.
Kommt noch was?
Merge Sort, genau, dann hat man doch auch gerade Merge immer wieder
hier.
Man sieht im Prinzip, im Speicher sieht es ein bisschen anders aus,
man kann den Rekursionsbaum nur erahnen.
Wenn man es hier so sieht, geht es von links nach rechts.
Auf das wollte ich Sie mal aufmerksam machen.
Schauen Sie selber, da gibt es noch mehr.
Ich bin noch eine Weile da, falls Sie Fragen haben, kommen Sie her.
Das war es für heute.