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

Fordító: Ádám Kósa Lektor: Zsuzsa Viola

You work at the college library.

Az egyetemi könyvtárban dolgozol.

You're in the middle of a quiet afternoon

Napod már a vége felé közeledik,

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

amikor hirtelen befut egy 1280 különböző könyvből álló szállítmány.

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

A könyveket egy vonalban, egymás mellé rakják le,

but they're all out of order,

de rendezetlen az egész,

and the automatic sorting system is broken.

és az automatikus osztályozó rendszer elromlott.

To make matters worse, classes start tomorrow,

Ha ez még nem lenne elég, holnap tanítási nap,

which means that first thing in the morning,

így az első dolog reggel az lesz,

students will show up in droves looking for these books.

hogy tanulók tömegei fogják ezeket a könyveket keresni.

How can you get them all sorted in time?

Hogyan tudod őket időben elrendezni?

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

Kezdhetnénk úgy, hogy az egyik végéről felveszed az első két könyvet.

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

Ha azok sorrendben vannak, hagyd úgy, ahogy voltak.

Otherwise, swap them.

Máskülönben felcseréljük őket.

Then, look at the second and third books,

Majd jön a második, harmadik pár,

repeat the process,

a folyamat ismétlődik.

and continue until you reach the end of the line.

Ezt egészen addig folytatod, amíg a sor végére érsz.

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

Lesz, hogy az utolsónak szánt könyv kerül a kezedbe,

and keep swapping it with every subsequent book,

és addig teszed a mögötte lévő könyvek után,

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

amíg oda nem érsz, ahová az tartozik, a végére.

Then, start from the beginning and repeat the process

Majd a folyamat újraindul, kezded elölről,

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

hogy az utolsó előtti könyv is helyére kerüljön,

and keep going until all books are sorted.

ez addig megy, míg mindegyik rendben lesz.

This approach is called Bubble Sort.

Ezt a módszert buborékrendezésnek hívjuk.

It's simple but slow.

Egyszerű, viszont lassú.

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

Első körben 1279-szer veted őket össze,

then 1,278, and so on,

majd 1278-szer és így tovább,

adding up to 818,560 comparisons.

összesen 818 560-szor csinálod meg.

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

Ha másodpercenként egyet vetnél össze, a folyamat kilenc napig tartana.

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

A másik módszer az lehetne, hogy az első két könyvvel kezdenél.

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

Majd hozzávennéd a harmadikat, és összevetnéd a második helyen lévővel.

If it belongs before the second book, swap them,

Ha azt a második hely illeti meg, megcseréled őket,

then compare it with the book in the first spot,

majd az első helyen lévővel veted össze,

and swap again if needed.

és ha kell, megint megcseréled.

Now you've sorted the first three books.

Eddig sorba raktad az első három könyvet.

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

Adj hozzá mindig egy könyvet a már rendezettekhez,

comparing and swapping the new book with the one before it

vesd össze és cseréld meg az új könyvet az előtt lévővel,

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

amíg a sorba rakott könyvek között helyére nem kerül.

This is called Insertion Sort.

Ezt beszúrásos rendezésnek hívjuk.

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

A buborékrendezéssel ellentétben itt nem kell minden könyvet összevetni.

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

Arra számíthatunk, hogy átlagosan egy-egy könyvet

to half of the books that came before it.

csak az előttük lévők felével kell összevetni.

In that case, the total number of comparisons

Ebben az esetben az összevetések száma

would be 409,280,

409 280 lenne,

taking almost five days.

majdnem öt napig tartana.

You're still doing way too many comparisons.

Még mindig túl sokszor veted őket össze.

Here's a better idea.

Íme, egy jobb ötlet:

First, pick a random book.

Véletlenszerűen kiveszel egy könyvet.

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

Nevezd el válaszelemnek, és vessük össze mindegyik könyvvel.

Then, divide the line

Majd válaszd szét a sort úgy,

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

hogy a válaszelem előtti könyvek bal oldalra,

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

az utána következők pedig jobb oldalra mennek.

You've just saved loads of time

Rengeteg időt spóroltál,

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

hogy többet nem veted össze a baloldali könyveket

to any of the ones on the right ever again.

a jobboldaliakkal.

Now, looking only at the books on the left,

Most csak a baloldaliakat nézve,

you can again pick a random partition book

újabb válaszelemet vehetsz ki,

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

és elkülönítheted az előtte és az utána jövő könyveket.

You can keep creating sub-partitions like this

Addig osztasz további kisebb válaszelemekre,

until you have a bunch of small sub-lines,

amíg sok-sok kis válaszfal nem lesz,

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

melyek között más módszerrel, pl. beszúrásos rendezéssel rendet teszünk.

Each round of partitioning requires about 1,280 comparisons.

Egy-egy elválasztáshoz 1280 összevetés kell.

If your partitions are pretty balanced,

Ha válaszelemeid egyenlő távolságra rakod,

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

ha minden tizedik könyvhöz teszünk egy válaszfalat, ami 128 darab,

or 8,960 seconds.

úgy hét kör kell vagy 8960 másodperc.

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

A válaszfalak közötti rendezés egyenként 22 másodpercet venne igénybe.

All in all, this method known as QuickSort

Ezzel az ún. gyorsrendezéssel egészében véve

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

három órán belül sorba lehet rakni a könyveket.

But there's a catch.

De van hátulütője.

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

A válaszelemek aránytalanságával nem spórolnál semmit.

Luckily, this rarely happens.

Szerencsére ez ritkán történik.

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

Ezért van, hogy a gyorsrendezés ma az egyik leghatékonyabb,

used by programmers today.

programozók által használt módszer.

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

Például ezzel rakják sorba ár szerint online boltok készletét,

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

vagy benzinkutakat listáznak ki egy adott helytől

sorted by distance.

távolság szerint.

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

Esetedben a rendezés után maradt még időd.

Just another high-stakes day in the library.

Csak egy újabb rázós nap a könyvtárban.