Effiziente Algorithmen

[Gausi]

Ich finde das Thema "Sortieren" eigentlich ganz gut dafür. Das ist nicht trivial, aber richtig aufgezogen auch interessant - zur Anschauung kann man ja ein Kartenspiel mitnehmen.

Ich würde allerdings nicht Bubblesort und/oder Quicksort nehmen. Als Beispiel zum Einstieg für einen nicht besonders effizienten Sortieralgorithmus würde ich mit "Sortieren durch Auswahl" anfangen. Also "Suche das kleinste Element, und packe es nach vorne. Dann im Rest das kleinste, und packe es an die zweite Stelle." usw.

Als Spaß-Einstieg ggf. noch Bogosort vorweg: "Mische und schaue nach, ob die Reihenfolge stimmt. Wenn nicht, probiere es nochmal."

Und dann würde ich eine Mergesort-Variante nehmen. Die ist auch in O(n*log(n)), und zwar auch im Worst-Case (das ist bei Quicksort nämlich nicht so!).
Der funktioniert so, dass ich schaue, welche Teilfolgen bereits passend sortiert sind. Je zwei aufeinanderfolgende sortierte Teilfolgen werden dann zu einer sortierten Teilfolge "gemischt", in dem jeweils die kleinere Zahl in die neue Folge eingefügt wird. (Kleiner Nachteil dabei: Benötigt mehr Platz).

Suchverfahren gehen natürlich auch. Hier würde ich zusätzlich zur linearen und binären Suche noch die Interpolationssuche hinzunehmen.

Als Bonus könnte man dann noch am Ende die Frage in den Raum werfen, ob es für "jedes Problem" einen "effizienten Algorithmus" gibt, oder ob es zumindest für jedes Problem, bei dem man die richtige Lösung schnell überprüfen kann, einen effizienten Algorithmus zur Findung der Lösung gibt.

Kann man auch als Abstimmung machen Ja/Nein/Weiß-Ich-Nicht. Und die, die sich dann bei "Weiß-Nicht" gemeldet haben, bekommen den Bonuspunkt, denn das weiß noch niemand. Stichpunkt: P-NP-Problem. Aber da ist dann die Definition von "effizient" eine etwas andere (und Bubblesort wäre dann auch in diesem Sinne effizient).

Und falls es doch Quicksort sein soll: Den kann man auch vortanzen.

https://www.youtube.com/watch?v=ywWBy6J5gz8