Wir haben heute die letzte Sitzung zum Thema Algorithmik, bevor wir uns ab nächster Woche mit

Komplexität von Problemen befassen. Da gehen schon die ersten Köpfe runter. Viel interessanteres

Gebiet als Algorithmik. Ich erinnere nochmal an das Buch, nachdem wir da vorgehen, damit

sie sich das schon mal beschaffen können. Sanjeev Arora und Boaz Barak, Computational Complexity,

A Modern Approach oder irgendein Untertitel. Wie eingangs angekündigt, legal im Internet verfügbar.

Gut. Das letzte, was wir jetzt aus dem Bereich Algorithmik machen, ist wiederum aus dem Bereich

Sortieren. Und zwar sortieren in linearer Zeit. Ja, das sollte vielleicht so ein bisschen Gemurmel

geben, denn wir haben ja gezeigt, dass das nicht geht. Wir haben gezeigt, dass Sortieralgorithmen

mindestens O von N mal log N brauchen und nicht O von N. Gut, aber ich hatte auch gleich damals

schon angemerkt, das gilt dann, wenn wir unterstellen, dass wir nichts weiter über die Schlüssel wissen.

Wenn wir dagegen zusätzliche Annahmen über die Schlüssel machen können, dann geht das schon.

Also halten wir nochmal hier fest, dass das nicht untergeht. So, also nochmal, das geht nur dann,

wenn wir spezielle Dinge über die Schlüssel wissen, die vielleicht nicht immer gelten.

So, ein ganz einfacher Fall ist der folgende.

Also ein einfacher Fall ist, dass es wenig Schlüssel gibt. Sagen wir Groß-K Stück und wir wissen,

welche das sind. Sagen wir zum Beispiel die Zahlen eben 0 bis K minus 1. In dem Falle

können wir uns einen wirklich gerade zu den trivialen Sortieralgorithmen ausdenken. Und zwar,

indem wir das Verfahren der sogenannten Buckets verwenden. Ja, was müssen wir machen? Ja, also

wenn wir wissen, es gibt nur K Schlüssel, dann stellen wir eben K Eimer bereit und jedes Mal,

wenn ein Element ankommt, schmeißen wir es in den passenden Eimer. Und hinterher stellen wir die Eimer

nebeneinander und dann ist das schon sortiert. Denn es gibt ja eben nur diese K Schlüssel,

wie es innerhalb der Schlüssel sortiert ist. Also bei gleichem Schlüssel ist ja eher ausdrücklich

egal. Das heißt, wir haben hier Sonnenbild. Wir haben hier unsere K Buckets, die schreiben wir

gleich in Array-Notationen. B von 0, B von 1 bis B von K minus 1. Und da haben wir hier irgendwie

so ein Förderband, was hier also unsere Elemente anliefert und die sortieren wir,

also wie sie reinkommen in die passenden Buckets. Ja, ein interessantes Bild,

das hätte ich mir nicht selber ausgedacht. Ja, schreiben wir das mal als Code auf.

So, aus irgendeinem Grunde heißt dieser Algorithmus K-Sort, warum auch immer. Na ja,

gut, zu ehren dieser Zahl K, die da vorkommt, aber der Name dieser Zahl K ist natürlich

Schall und Rauch. Was im Buch so ein bisschen unterschlagen wird, also man sollte diesem

Algorithmus ehrlicherweise die Zahl Schlüssel als Argument mitgeben. Das heißt, hier gehört hin ein

Argument K, das ist eine natürliche Zahl, das ist also die Anzahl Schlüssel, die wir hier verarbeiten.

Und wie immer ist also die Eingabe eine Sequenz von Elementen und auch die Ausgabe eine Sequenz von

Elementen. So, weil das hier die Anzahl Schlüssel sein soll, dürfen wir die Funktion natürlich

korrekterweise nur dann aufrufen, wenn das tatsächlich die in S vorkommenden Schlüssel sind. Das heißt,

wir fangen an mit einem Assume. Wieder in salopperschreibweise, wo wir so tun, als wäre die

Sequenz einer Menge, dann ist das hier Notation für das Bild einer Menge unter einer Abbildung. Ja,

das hier ist also die Menge aller Schlüssel, die in S vorkommen und diese Menge soll enthalten sein

in der Menge der ganzen Zahlen von 0 bis K minus 1. Gut, wir brauchen ja diese Buckets, die müssen

wir uns also deklarieren. Das ist ein Array B, das besteht aus diesen K Buckets, die sind am Anfang

alle leer. Und der Typ von dem Ding ist, gut, es ist wie gesagt ein Array mit K Einträgen und der Typ

der Einträge ist Sequenz of elements. So, dadurch, dass das hier eine Sequenz von Einträgen ist,

in jedem Bucket ist das nicht wirklich ein Eimer. Ja, oder naja, es ist vielleicht ein Eimer in dem

Sinne, dass wir da die Elemente alle, wie sie reinkommen, oben aufeinander aufwärts starten.

Ja, also in diesen Eimern lagern wir also vorstellungsmäßig nicht Bälle, die irgendwie

durcheinander fallen, sondern sagen wir Betonplatten, die wir eine nach der anderen

übereinander schichten. So, wie machen wir das also? Irgendwo mal ein Kommentar hier, wie immer.

Die Einträge von S, die bezeichnen wir, wie in allen Algorithmen dieser Farbe bisher, mit E1 bis E n.

So, und wir gehen dann durch die Liste durch, das heißt wir lassen i von 1 bis n laufen und

gucken uns also immer das it-Element an. Ja, gut, was machen wir mit dem it-Element? Wir schauen,