Ich hätte gesagt, wir fangen mal mit einem Rückblick an ganz normal.

Letzte Vorlesung, also gestern haben Sie den QuickSort besprochen.

Das ist ein Effizenter vergleichspassierter Sortieralgerhythmus, der auf dem die beiden Konkernansatz

passiert und zum Sortieren, um diese Unterlisten zu erstellen, ein Pivot-Element verwendet.

Dieses Pivot-Element teilt dann, dass wir übergebende Liste, ins Weisublisten,

die werden dann recursiv sortiert und am Ende kann man eine Sortierte Liste zusammenfassen.

Das ist der QuickSort den wir gestern besprochen haben und den werden Sie ausführlich noch in der Übung,

in den nächsten bewerteten Blatt behandeln dürfen.

Insbesondere werden Sie da sehen, wie das Pivot-Element die Effizienz von dem Verfahren beeinflussen kann.

In den letzten Vorlesung haben wir auch gesehen, welche Laufzeit der Algorithmus hat, nämlich

O von N-Log N, im Best- und Erritch-Case und für den Wörskase O von N Quadrat.

So was in die Richtung dürfen Sie dann auch in bewerteten Übungsblatt beweisen.

Genau.

Heute werden wir nicht zugleich basierte Sortierverfahren anschauen und damit das Themengebiet

zum Sortieren abschließen und nächste Woche dann übergehen zum nächsten Themengebiet,

was voraussichtlich die einführenden Grafen sein wird und dann Graf-Alberutmen.

Die Literaturzeutigen-Volle-Lisung ist im großen Teil der Comin, also die Einführung in die Algorithmen,

die wir das Ganze im Best-Über verwenden, in dem Fall das Kapitel 8.

Zum Großteil in gewissen Stellen gehe ich über die Literatur noch hinaus

und das werden Sie dann an der Tafel sehen.

Das ist besonders beim Bucket Sort der Fall.

Genau.

Gibt es vorab noch irgendwelche Fragen von Ihnen zu letzter Woche, also zum QuickSort?

Nein.

Dann würde ich sagen, beginnen wir und beginnen mit der Motivation, was wir heute machen wollen

und warum wir uns für nicht vergleichsbasierte Sortieralgerutmen interessieren.

In der Einführungsübung zu sortieren, was sind die unter die in der zweiten Übung?

Haben Sie einen Theorien kennengelernt für den Lower-Bound von vergleichsbasierten Sortierfe von,

das wie folgt aussieht?

Also für jedes Vergleich basierte Sortierverfahren sind im schlechtesten Fall,

oder nicht im schlechtesten Fall, in O von N log N vergleichsobartern notwendig.

Der flächte Fall hier bezieht sich auf wie viele wirklich notwendig sind,

nicht wie viele bei der Wurscase-Analyser auftreten.

Genau.

Das heißt, wir haben hier Omega von N log N als untere Schranke für vergleichsbasierte Sortierverfahren.

Das ist der Lower-Bound, das ist ein Theorem, was im Allgemeinen gilt.

Den Beweist dazu werden Sie in der Übung sehen, der geht im Endeffekt darüber,

dass wir Sortierverfahren auf Baumstrukturen reduzieren können, mitternachtlich darstellen können.

Und dann über die Höhe vom Baum argumentieren können, dass wir nicht schneller als die Abstiegenein machen können,

die wir zum Sortieren brauchen.

Genau. Das ist der Lower-Bound.

Und wir wollen uns heute angucken, wie wir trotzdem schneller sortieren können,

in gewissen Spezialfällen und in gewissen Anderen, als dieser Lower-Bound ist uns zulässt bisher.

Und dafür müssen wir uns angucken, was diesem Theorem, das wir bewiesen haben,

oder wir noch beweisen werden, in der Übung überhaupt zugrunde liegt,

um herauszufinden, wie wir Verfahren bauen können, die trotzdem schneller als Omega von N-Log N sortieren.

Und was wir sehen, wir haben zum einen erst mal dieses Schlagwort vergleichsbasierte Sortierverfahren,

was uns sagt, okay, wir haben irgendeine Art von vorginsweise den Sortierverfahren hinterlegt,

die wir bisher betrachtet haben, für die das hier gilt.

Dann haben wir natürlich in den schlechtesten Fall. Das heißt, also, in der notwendig ist,