Wem diese Überlegung zu mühsam ist, der probiert es einfach aus. Aber sobald man dieses Ergebnis eingesehen hat, wird klar, wie es weiter gehen muss: Der Algorithmus fängt wieder vorne an, vergleicht und sortiert jeweils die nachfolgenden Namen, fährt fort wie im ersten Durchlauf, bis er am vorletzten Namen angekommen ist: Der ist dann auch der vorletzte im Alphabet – mit dem gleichen Argument wie oben. Im dritten Durchlauf ergibt sich als drittletzter Name der alphabetisch richtige. Und so geht es weiter, Durchlauf für Durchlauf, bis die ganze Liste sortiert ist. Genauer: Nach n-1 Durchläufen ist die Liste vollständig geordnet, wenn n die Anzahl der Namen in der Liste (die Länge der Liste) bezeichnet.
Die Erfahrung zeigt, dass schon Grundschulkinder diesen Algorithmus (in der Literatur als „Bubblesort“ bekannt) sehr schnell verstehen können. Der beschriebene Algorithmus spielt in der Praxis keine große Rolle, weil es andere, effizientere Sortieralgorithmen gibt. Er ist aber durchaus geeignet, eine Ahnung von algorithmischem Denken zu vermitteln. Er lässt sich in wenigen Zeilen programmieren.
2. Beispiel Kurze Wege: Bitte stellen Sie sich folgende Aufgabe vor: Finden Sie für eine Rundreise den kürzesten Weg, der eine Anzahl vorgegebener Städte so verbindet, dass jede Stadt genau einmal besucht wird. Auch dies ist ein unmittelbar verständliches Problem; und auch hier kommt man leicht auf folgende algorithmische Idee:
In der Stadt A startend besuche als erste die Stadt (nennen wir sie B) mit der kürzesten Entfernung von A, und dann als zweite die Stadt (C) mit der kürzesten Entfernung von B. Und so weiter: Besuche als nächste jeweils die Stadt mit der kürzesten Entfernung unter allen Städten, die noch nicht besucht worden sind. Am Ende geht es zurück nach A. (Bei gleichen Entfernungen wähle eine der gleich weit entfernten Städte, z.B. gemäß dem Stadtnamen im Alphabet).
Ist der so gefundene Rundreiseweg der kürzest mögliche? Anhand einfacher Beispiele mit wenigen Städten macht man sich leicht klar, dass der Algorithmus nicht unbedingt den kürzesten Gesamtweg liefert. Aber wie findet man den? Eine Möglichkeit ist, alle möglichen Wege auszuprobieren. Bei sechs Städten sind das schon 120 (= 5*4*3*2) Möglichkeiten, da kann man noch alle durchprobieren. Aber bei vielen Städten sind das ungeheuer viele Möglichkeiten: Wenn man annimmt, dass man für das Durchprobieren aller Möglichkeiten bei zehn Städten 0,1 Sekunden Rechenzeit benötigt, bräuchte man für 18 Städte schon mehr als drei Jahre Rechenzeit!
Die Anzahl der Möglichkeiten steigt unvorstellbar schnell (für mathematisch Interessierte: wie n!) an. Wegen dieser Eigenschaft ist das sogenannte Travelling Salesman Problem nicht nur praktisch wichtig, sondern auch in der mathematischen Theorie so prominent: Es ist bis heute kein Algorithmus bekannt, der das Problem für größere Anzahlen von Städten in vertretbarer Rechenzeit optimal löst. Aber akzeptable Lösungen lassen sich mit geeigneten Algorithmen dagegen durchaus berechnen.
Das folgende Beispiel des Page Ranking bei der Google-Suche ist ebenfalls von großer, sehr aktueller und enormer wirtschaftlicher Bedeutung – es war der Ausgangspunkt für den wirtschaftlichen Erfolg von Google. Für dieses Beispiel lässt sich ein einfacher Algorithmus nicht so leicht angeben wie für die beiden vorangehenden Beispiele; es erfolgreich zu behandeln erfordert dann doch schon mehr Mathematik, als wir hier vermitteln können. Was aber geht, ist, sich ein paar elementare algorithmische Prinzipien zu überlegen, die hier eine entscheidende Rolle spielen könnten.
