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

Vertaald door: Tahlia Flora

You work at the college library.

Je werkt in de mediatheek.

You're in the middle of a quiet afternoon

De middag verloopt rustig

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

totdat er plotseling

1.280 verschillende soorten boeken worden gebracht.

De boeken worden in een lange kaarsrechte rij afgeleverd,

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

but they're all out of order,

maar ze staan niet op alfabet

and the automatic sorting system is broken.

en de automatische sorteermachine is buiten gebruik.

Tot overmaat van ramp start morgen het nieuwe schoojaar

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

en dat betekent dat morgenvroeg

drommen studenten op zoek gaan naar deze boeken.

students will show up in droves looking for these books.

How can you get them all sorted in time?

Hoe ga je ze zo snel mogelijk ordenen?

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

Begin aan de linkerkant met het eerste aantal boeken.

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

Als de eerste twee boeken op alfabetische volgorde staan, laat ze dan zo.

Otherwise, swap them.

Zoniet, ruil ze dan om.

Then, look at the second and third books,

Kijk vervolgens naar het tweede en derde boek,

repeat the process,

doe nu precies hetzelfde

and continue until you reach the end of the line.

en herhaal dit tot het einde van de rij.

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

Ergens kom je het boek tegen die op de laatste plek hoort te staan,

and keep swapping it with every subsequent book,

ruil deze steeds om met elk daaropvolgende boek,

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

richting het eind van de rij totdat het op de juiste plek staat.

Then, start from the beginning and repeat the process

Begin vanaf het begin en herhaal het proces

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

om het een-na-laatste boek op de juiste plek te krijgen

and keep going until all books are sorted.

en ga zo door totdat alle boeken geordend zijn.

This approach is called Bubble Sort.

Dit heet de bubble-sort-methode.

It's simple but slow.

Het is een simpel maar traag proces.

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

Je vergelijkt 1.279 boeken in de eerste ronde,

then 1,278, and so on,

daarna 1.278 en zo verder,

adding up to 818,560 comparisons.

wat resulteert in 818.560 vergelijkingen.

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

Als elke vergelijking één seconde in beslag neemt,

duurt het proces ruim negen dagen.

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

Een tweede strategie is om alleen de eerste twee boeken te ordenen.

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

Pak dan het derde boek en vergelijk deze met het tweede boek.

If it belongs before the second book, swap them,

Als het voor het tweede boek hoort te staan, ruil ze dan om,

then compare it with the book in the first spot,

vergelijk het daarna met het eerste boek

and swap again if needed.

en ruil deze ook om, mocht het nodig zijn.

Now you've sorted the first three books.

Nu heb je de eerste drie boeken geordend.

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

Voeg steeds een boek tegelijk toe aan de geordende sublijn,

comparing and swapping the new book with the one before it

door het nieuwe met het vorige boek te vergelijken en om te ruilen

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

totdat het op de juiste plek staat tussen de boeken die tot nu toe geordend zijn.

Dit heet invoegsortering.

This is called Insertion Sort.

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

Anders dan bij de bubble-sort-methode, wordt niet elk boek met elkaar vergeleken.

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

Gemiddeld genomen hoeven we alleen elk boek te vergelijken

to half of the books that came before it.

met de helft van de voorgaande boeken.

In that case, the total number of comparisons

In dit geval komt dit totaal neer op

would be 409,280,

409.280 vergelijkingen

taking almost five days.

wat ruim vijf dagen in beslag neemt.

Dit zijn nog steeds te veel vergelijkingen.

You're still doing way too many comparisons.

Here's a better idea.

Er is een beter idee.

First, pick a random book.

Kies een willekeurig boek uit.

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

Noem het de boekensteun en vergelijk het met elk ander boek.

Then, divide the line

Verdeel daarna de rij

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

door alle boeken die tot aan de boekensteun horen links te plaatsen

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

en de rest van de boeken rechts te plaatsen.

You've just saved loads of time

Je hebt ontzettend veel tijd bespaard

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

doordat je de boeken aan de linkerkant

to any of the ones on the right ever again.

nooit meer met de boeken aan de rechterkant hoeft te vergelijken.

Now, looking only at the books on the left,

Als je alleen de boeken aan de linkerkant bekijkt,

you can again pick a random partition book

dan kan je weer een willekeurig boek als boekensteun gebruiken

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

en deze boeken links of rechts ervan plaatsen.

You can keep creating sub-partitions like this

Je kan dit soort indelingen blijven maken

until you have a bunch of small sub-lines,

totdat je een groep kleine sublijnen hebt,

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

die je zo snel mogelijk ordent

door een andere strategie toe te passen, zoals invoegsortering.

Each round of partitioning requires about 1,280 comparisons.

Elke sorteerronde bestaat uit minstens 1.280 vergelijkingen.

If your partitions are pretty balanced,

Als je indelingen behoorlijk evenwichtig zijn

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

dan duurt het ruim zeven rondes om de boeken per tien stuks

in 128 sublijnen in te delen

or 8,960 seconds.

of 8.960 secondes.

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

Per sublijn worden er 22 secondes extra toegevoegd.

All in all, this method known as QuickSort

Hoe dan ook, via deze quicksort-methode

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

worden boeken binnen drieënhalf uur gesorteerd.

But there's a catch.

Maar er zit een addertje.

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

Je indelingen kunnen onevenwichtig zijn, waardoor er veel tijd verloren gaat.

Luckily, this rarely happens.

Gelukkig gebeurt dit zelden.

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

Daarom is de quicksort-methode een van de meest efficiënte strategieën

used by programmers today.

die momenteel door programmeurs worden toegepast.

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

Ze passen deze methode toe om producten in een webwinkel op prijs te ordenen

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

of om een overzicht te maken van de dichtstbijzijnde benzinepompen

sorted by distance.

op basis van afstand.

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

In jouw geval heb je snel geordend en genoeg tijd overgehouden.

Just another high-stakes day in the library.

Gewoon weer een productieve dag in de mediatheek.