Wie alphabetisierst du dein Bücherregal am schnellsten? - Chand John

Vollständige Lektion unter: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Du arbeitest in der Universitätsbibliothek. Es ist ein ruhiger Nachmittag, als plötzlich eine Lieferung 1280 Bücher ankommt. Die Bücher wurden in einer geraden Reihe aufgestellt, aber leider nicht geordnet, und das automatische Sortiersystem ist kaputt. Wie schaffst du es, die Bücher schnell zu sortieren? Chand John zeigt wie's geht, und erkälrt, wie Algorithmen Bibliothekaren und Suchmaschinen dabei helfen, rasch Informationen zu ordnen.

Lektion von Chand John, Animation von Anton Trofimov.

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.