What's the fastest way to alphabetize your bookshelf? - Chand John

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

Übersetzung: Elisabeth Starck Lektorat: Tonia David

You work at the college library.

Du arbeitest in der Universitätsbibliothek.

You're in the middle of a quiet afternoon

Es ist ein ruhiger Nachmittag,

when suddenly a shipment of 1,280 different books arrives.

als plötzlich eine Lieferung von 1280 unterschiedlichen Bücher ankommt.

The books have been dropped of in one long straight line,

Die Bücher wurden in einer lange, geraden Reihe aufgestellt,

but they're all out of order,

doch sie sind nicht geordnet,

and the automatic sorting system is broken.

und das automatische Sortiersystem ist kaputt.

To make matters worse, classes start tomorrow,

Zu allem Übel fängt morgen wieder der Unterricht an,

which means that first thing in the morning,

was bedeutet, dass gleich morgen früh

students will show up in droves looking for these books.

Studenten scharenweise nach diesen Büchern suchen werden.

How can you get them all sorted in time?

Wie schaffst du es alle rechtzeitig zu ordnen?

One way would be to start at one end of the line with the first pair of books.

Du könntest z. B. an einem Ende der Reihe mit dem ersten Buchpaar anfangen.

If the first two books are in order, then leave them as they are.

Wenn die ersten zwei Bücher geordnet sind, dann lass sie so.

Otherwise, swap them.

Ansonsten, tausche sie.

Then, look at the second and third books,

Sieh dir dann das 2. und 3. Buch an,

repeat the process,

wiederhole den Vorgang,

and continue until you reach the end of the line.

und mach so weiter bis zum Ende der Reihe.

At some point, you'll come across the book that should be last,

Irgendwann stößt du auf das Buch, das als letztes stehen sollte.

and keep swapping it with every subsequent book,

Du tauscht es weiterhin mit den darauffolgenden Büchern,

moving it down the line until it reaches the end where it belongs.

und rückst es somit an das Ende der Reihe, wo es hingehört.

Then, start from the beginning and repeat the process

Dann beginnst du wieder von vorne und wiederholst den Vorgang,

to get the second to last book in its proper place,

um das zweitletzte Buch an seinen Platz zu bringen.

and keep going until all books are sorted.

So machst du weiter, bis alle Bücher sortiert sind.

This approach is called Bubble Sort.

Diese Methode heißt "Bubblesort".

It's simple but slow.

Sie ist sehr einfach, aber langsam.

Du würdest 1279 Vergleiche in der erste Runde machen,

You'd make 1,279 comparisons in the first round,

then 1,278, and so on,

dann 1278, und so weiter.

adding up to 818,560 comparisons.

Insgesamt wären das 818 560 Vergleiche.

If each took just one second, the process would take over nine days.

Würde jeder Vergleich nur eine Sekunde benötigen,

dann würde das Verfahren mehr als neun Tage dauern.

A second strategy would be to start by sorting just the first two books.

Eine zweite Strategie wäre, zuerst nur die ersten beiden Bücher zu ordnen.

Then, take the third book and compare it with the book in the second spot.

Nimm dann das dritte Buch und vergleiche es

mit dem Buch an zweiter Stelle.

If it belongs before the second book, swap them,

Gehört es vor's zweite Buch, tausche sie.

Vergleiche es dann mit dem Buch an erster Stelle,

then compare it with the book in the first spot,

and swap again if needed.

und tausche die beiden, wenn nötig.

Now you've sorted the first three books.

Jetzt hast du die ersten drei Bücher sortiert.

Keep adding one book at a time to the sorted sub-line,

Füge ein Buch nach dem anderen zu der geordneten Bücherreihe hinzu,

comparing and swapping the new book with the one before it

indem du es mit den Büchern davor vergleichst und tauschst,

until it's correctly placed among the books sorted so far.

bis es an der richtigen Stelle unter den schon sortierten Büchern steht.

Dieses Verfahren heißt "Insertionsort".

This is called Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

Anders als bei Bubblesort, muss man nicht jedes Buchpaar miteinander vergleichen.

On average, we'd expect to only need to compare each book

Im Durchschnitt erwarten wir, dass wir jedes Buch

nur mit der Hälfte der Bücher, die davor kommen, vergleichen müssen.

to half of the books that came before it.

In that case, the total number of comparisons

In diesem Fall liegt die Gesamtzahl der Vergleiche

would be 409,280,

bei 409 280,

taking almost five days.

und dauert fast fünf Tage.

You're still doing way too many comparisons.

Du machst immer noch viel zu viele Vergleiche.

Here's a better idea.

Hier eine bessere Idee:

First, pick a random book.

Zuerst wählst du willkürlich ein Buch aus.

Call it the partition and compare it to every other book.

Das ist das Trennelement, das du mit jedem anderen Buch vergleichst.

Then, divide the line

Teile dann die Reihe,

by placing all the books that come before the partition on its left

indem du alle Bücher, die vor dem Trennelement stehen, links davon anordnest

and all the ones that come after it on its right.

und alle die danach kommen, rechts davon.

You've just saved loads of time

Du hast gerade sehr viel Zeit gespart,

by not having to compare any of the books on the left

denn du musst nie wieder die Bücher auf der linken Seite

to any of the ones on the right ever again.

mit den Büchern auf der rechten Seite vergleichen.

Betrachte jetzt nur die Bücher auf der linken Seite.

Now, looking only at the books on the left,

you can again pick a random partition book

Du kannst hier wieder ein Buch als Trennelement wählen,

and separate those books that come before it from those that come after it.

und die Bücher, die davor und danach kommen, voneinander trennen.

So kannst du immer weitere Unterteilungen erzeugen,

You can keep creating sub-partitions like this

until you have a bunch of small sub-lines,

bis du eine Menge kleiner Teilbereiche hast,

each of which you'd sort quickly using another strategy, like Insertion Sort.

die du durch eine andere Sortiermethode, wie Insertionsort, schnell ordnen kannst.

Each round of partitioning requires about 1,280 comparisons.

Bei jeder Unterteilung fallen etwa 1280 Vergleiche an.

If your partitions are pretty balanced,

Wenn deine Aufteilungen relativ gleichmäßig sind,

dividing the books into 128 sub-lines of ten would take about seven rounds,

brauchst du, wenn du die Bücher in 128 Teilbereiche à zehn Bücher teilst,

ca. 7 Runden, oder 8960 Sekunden.

or 8,960 seconds.

Sorting these sub-lines would add about 22 seconds each.

Das Sortieren dieser Teilbereiche braucht jeweils 22 Sekunden.

All in all, this method known as QuickSort

Alles in allem könntest du mit dieser Methode namens "Quicksort"

could sort the books in under three and a half hours.

die Bücher in unter dreieinhalb Stunden ordnen.

But there's a catch.

Doch das hat einen Haken:

Your partitions could end up lopsided, saving no time at all.

Sind die Unterteilungen ungleichmäßig,

sparst du keine Zeit.

Luckily, this rarely happens.

Glücklicherweise passiert das selten.

That's why QuickSort is one of the most efficient strategies

Deshalb ist Quicksort eine der effizientesten Strategien,

used by programmers today.

die heute von Programmierern benutzt wird.

They use it for things like sorting items in an online store by price,

Damit werden in Onlineshops die Waren nach dem Preis geordnet,

or creating a list of all the gas stations close to a given location

oder eine Liste aller Tankstellen in der Nähe eines gegeben Ortes

sorted by distance.

nach Entfernung sortiert.

In your case, you're done quick sorting with time to spare.

In deinem Fall bist du mit dem Ordnen fertig, und hast noch Zeit über.

Just another high-stakes day in the library.

Wieder ein anspruchsvoller Tag in der Bibliothek.