Du arbeitest in der Universitätsbibliothek.
Es ist ein ruhiger Nachmittag,
als plötzlich eine Lieferung von 1280 unterschiedlichen Bücher ankommt.
Die Bücher wurden in einer lange, geraden Reihe aufgestellt,
doch sie sind nicht geordnet,
und das automatische Sortiersystem ist kaputt.
Zu allem Übel fängt morgen wieder der Unterricht an,
was bedeutet, dass gleich morgen früh
Studenten scharenweise nach diesen Büchern suchen werden.
Wie schaffst du es alle rechtzeitig zu ordnen?
Du könntest z. B. an einem Ende der Reihe mit dem ersten Buchpaar anfangen.
Wenn die ersten zwei Bücher geordnet sind, dann lass sie so.
Ansonsten, tausche sie.
Sieh dir dann das 2. und 3. Buch an,
wiederhole den Vorgang,
und mach so weiter bis zum Ende der Reihe.
Irgendwann stößt du auf das Buch, das als letztes stehen sollte.
Du tauscht es weiterhin mit den darauffolgenden Büchern,
und rückst es somit an das Ende der Reihe, wo es hingehört.
Dann beginnst du wieder von vorne und wiederholst den Vorgang,
um das zweitletzte Buch an seinen Platz zu bringen.
So machst du weiter, bis alle Bücher sortiert sind.
Diese Methode heißt "Bubblesort".
Sie ist sehr einfach, aber langsam.
Du würdest 1279 Vergleiche in der erste Runde machen,
dann 1278, und so weiter.
Insgesamt wären das 818 560 Vergleiche.
Würde jeder Vergleich nur eine Sekunde benötigen,
dann würde das Verfahren mehr als neun Tage dauern.
Eine zweite Strategie wäre, zuerst nur die ersten beiden Bücher zu ordnen.
Nimm dann das dritte Buch und vergleiche es
mit dem Buch an zweiter Stelle.
Gehört es vor's zweite Buch, tausche sie.
Vergleiche es dann mit dem Buch an erster Stelle,
und tausche die beiden, wenn nötig.
Jetzt hast du die ersten drei Bücher sortiert.
Füge ein Buch nach dem anderen zu der geordneten Bücherreihe hinzu,
indem du es mit den Büchern davor vergleichst und tauschst,
bis es an der richtigen Stelle unter den schon sortierten Büchern steht.
Dieses Verfahren heißt "Insertionsort".
Anders als bei Bubblesort, muss man nicht jedes Buchpaar miteinander vergleichen.
Im Durchschnitt erwarten wir, dass wir jedes Buch
nur mit der Hälfte der Bücher, die davor kommen, vergleichen müssen.
In diesem Fall liegt die Gesamtzahl der Vergleiche
bei 409 280,
und dauert fast fünf Tage.
Du machst immer noch viel zu viele Vergleiche.
Hier eine bessere Idee:
Zuerst wählst du willkürlich ein Buch aus.
Das ist das Trennelement, das du mit jedem anderen Buch vergleichst.
Teile dann die Reihe,
indem du alle Bücher, die vor dem Trennelement stehen, links davon anordnest
und alle die danach kommen, rechts davon.
Du hast gerade sehr viel Zeit gespart,
denn du musst nie wieder die Bücher auf der linken Seite
mit den Büchern auf der rechten Seite vergleichen.
Betrachte jetzt nur die Bücher auf der linken Seite.
Du kannst hier wieder ein Buch als Trennelement wählen,
und die Bücher, die davor und danach kommen, voneinander trennen.
So kannst du immer weitere Unterteilungen erzeugen,
bis du eine Menge kleiner Teilbereiche hast,
die du durch eine andere Sortiermethode, wie Insertionsort, schnell ordnen kannst.
Bei jeder Unterteilung fallen etwa 1280 Vergleiche an.
Wenn deine Aufteilungen relativ gleichmäßig sind,
brauchst du, wenn du die Bücher in 128 Teilbereiche à zehn Bücher teilst,
ca. 7 Runden, oder 8960 Sekunden.
Das Sortieren dieser Teilbereiche braucht jeweils 22 Sekunden.
Alles in allem könntest du mit dieser Methode namens "Quicksort"
die Bücher in unter dreieinhalb Stunden ordnen.
Doch das hat einen Haken:
Sind die Unterteilungen ungleichmäßig,
sparst du keine Zeit.
Glücklicherweise passiert das selten.
Deshalb ist Quicksort eine der effizientesten Strategien,
die heute von Programmierern benutzt wird.
Damit werden in Onlineshops die Waren nach dem Preis geordnet,
oder eine Liste aller Tankstellen in der Nähe eines gegeben Ortes
nach Entfernung sortiert.
In deinem Fall bist du mit dem Ordnen fertig, und hast noch Zeit über.
Wieder ein anspruchsvoller Tag in der Bibliothek.