Zeitbedarf

(Ostmann & Widmayer, 2017)

Sortiervorgänge sind in der Informatik von großer Bedeutung, denn “Untersuchungen von Computerherstellern und -nutzern zeigen seit vielen Jahren, dass mehr als ein Viertel der kommerziell verbrauchten Rechenzeit auf Sortiervorgänge entfällt” (Ostmann & Widmayer, 2017, S. 79). Es ist daher nicht verwunderlich, dass große Anstrengungen unternommen wurden, möglichst effiziente Verfahren zum Sortieren von Daten zu entwickeln.

Wie effizient ein Algorithmus letztendlich arbeitet, hängt (neben dem Speicherbedarf) im Wesentlichen davon ab, wie lange die Laufzeit ist, um eine Aufgabe zu lösen. Um Lernenden zu vermitteln, wie eine solche Komplexitätsanalyse abläuft, bieten sich Sortieralgorithmen an.

Wie lange es dauert die Liste namens sammlung zu sortieren, hängt sicherlich unter anderem von deren Länge $n$ ab. Und es ist von vornherein klar, dass ein Sortieralgorithmus mindestens $n$ Schritte/Operationen/Vergleiche braucht, um so eine Liste zu sortieren: Denn jedes der $n$ Bücher in unserem Stapel muss mindestens einmal angesehen werden, um es irgendwo einsortieren zu können. Wie sich herausstellen wird, werden immer mehr als $n$ Schritte gebraucht.

Hinzu kommt, dass die Effizienz der Algorithmen, die im Anschluss präsentiert werden, von der Länge $n$ abhängen wird. Der Bubblesort ist beispielsweise besonders gut für kurze Reihungen ($\le 8$) geeignet. Allerdings ist er einer der langsamsten bei längeren Reihungen. Der genaue Zeitbedarf vieler Sortieralgorithmen ist neben der Datenmenge (Länge der Reihung) auch von Anordnung der Reihung abhängig. Ist die Liste schon fast sortiert, so brauchen einige Verfahren weniger Zeit, als wenn die Liste beispielsweise genau in der umgekehrten Reihenfolge vorliegt. Auf der anderen Seite gibt es Verfahren, die mit einer fast sortierten Reihung langsamer arbeiten als mit einer zufälligen Ordnung. Dies ist ein gutes Beispiel dafür, wie sorgfältig Computer große Datenmengen abarbeiten können, allerdings daran scheitern, mitzudenken.