Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Gut, wir stecken mitten im Sortieren und haben das letzte Mal,

erstmal so, fangen wir jetzt an, die richtigen ersten Basis-Algorithmen kennenzulernen.

Zwei hat man auch schon auf Grafen kennengelernt, diese Steps First Search und Breadth First Search,

also wie ich sozusagen in linearer Laufzeit feststellen kann, ob ein Graph zusammenhängend ist

und nicht nur das, sondern auch die Anzahl Komponenten eines Graphen einfach dadurch bestimmen kann in linearer Laufzeit.

Und dann haben wir jetzt so in Anführungszeichen vielleicht einen kleinen Exkurs, was das Sortieren betrifft.

Diejenigen, die Nebenfachinformatik haben, ich glaube, die sollten das eigentlich alle wissen, hoffe ich doch mal.

Für die Mathematiker interessanterweise kommt es relativ selten, wie man sortiert.

Wir werden aber gleich im nächsten Kapitel, vielleicht schaffen wir das heute auch noch,

vielleicht die erste größere Anwendung kennenlernen, wo man tatsächlich sortieren können muss.

Wobei das können muss, ist ja an sich nicht schwer, wie man sortiert,

weil einfache Algorithmen haben wir das letzte Mal kennengelernt, da ging es rein darum zu sagen,

ich kann ja einfach einmal durchlaufen, mir das Minimum bestimmen, dann habe ich schon mal den Kleinstand,

dann nehme ich von den letzten N-1 wieder das Minimum und so weiter.

Auf die Art und Weise kriegt man ja trivialerweise sozusagen so eine Menge sortiert.

Das andere ist sozusagen, das Bubble Sort war ja ähnlicher Natur.

Was bislang noch offen ist und wo Sie es letztes Mal dann angefangen haben, war sozusagen, geht es denn schneller?

Also geht den Sortieren tatsächlich schneller als N²? Jetzt kann man sagen, was soll es, N² oder N log N oder N oder was auch immer,

aber es macht durchaus für große Größenordnungen einen signifikanten Unterschied.

Vielleicht schauen wir uns das einmal in der Übung an.

Man kann sich das, also an der Tafel ist halt immer ein N² nicht so viel schlimmer als ein N,

aber im Computer ist es durchaus, wenn Sie einen Gigabyte Daten sortieren sollen

und ob Sie jetzt 10 hoch 9 Rechenoperation haben oder 10 hoch 9 zum Quadrat, 10 hoch 18 Rechenoperation haben,

das macht einen signifikanten Unterschied.

Selbst wenn Sie jetzt 10 hoch 6 oder 10 hoch 8 in der Sekunde durchrechnen können,

dann warten Sie im einen Fall halt doch einige Sekunden mehr und manchmal sind das dann mehr Sekunden als wir selber leben.

Da kann so ein Quadrat sehr schnell viel ausmachen.

Deshalb ist es wichtig immer zu gucken für die Basisalgorithmen, auch die, die immer wieder verwendet werden

und dann auch immer wieder sozusagen als Unterroutine, was ist denn, wie kann man die so gut tunen,

dass die sozusagen, dass man da möglichst wenig Laufzeit verlieren, deshalb auch jetzt ein Stück weit dieser X-Kurs übersortieren

und das letzte Mal haben wir angefangen mit dem QuickSort und dieser QuickSort ist ein schönes Beispiel für dreierlei Dinge.

Einmal, dass es, wenn es dumm läuft, nicht besser ist als N², wenn man aber die Sachen im Schnitt sich anguckt

oder im guten Fall, also wenn man sich den günstigsten Fall anguckt, man tatsächlich ein N log N hinkriegt

und dann kann man eine Analyse machen, stochastischer Art, dass man sagt,

wenn man jetzt sozusagen die zu sortierenden Arrays gleich verteilt an dem, wie lang läuft denn der im Schnitt,

also im Durchschnitt über alle möglichen Sortierungen, die auftreten können,

dann wenn wir das heute sehen, dann kommt tatsächlich ein N log N raus.

Also das ist ein Verfahren, der im Durchschnitt gut ist, aber gut, jetzt stört es natürlich immer noch,

die Mathematiker stören das ja meistens oder eigentlich auch berechtigterweise zu sagen,

ja was hilft uns der Schnitt, es kann ja dumm laufen und wir treffen gerade mal einen ungünstigen Fall.

Beim QuickSort hilft da nicht, im ungünstigen Fall haben wir N², aber währenddessen den Hiebsort kennenlernen,

dem ist es egal, ob es ein günstiger oder ungünstiger Fall ist, der wird immer in N log N Laufzeit laufen.

Dann kann man sich anwider die Frage stellen, geht es denn besser als N log N?

Ist denn N log N tatsächlich das Beste, was machbar ist und es ist in der Tat das Beste,

solange man auf paar Weisen Vergleich basiert?

Also wenn immer ich zwei Elemente miteinander vergleichen möchte,

also wenn irgendein Algorithmus, den ich mir überlege, darauf beruht, Elemente miteinander zu vergleichen,

hat er gar keine Chance besser zu laufen als N log N, das schauen wir uns dann mal an.

Das klingt vielleicht erstmal verblüffend, warum es so ist, aber das Argument ist dann doch gar nicht so wild.