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

Tłumaczenie: Magdalena Góra Korekta: Ola Królikowska

You work at the college library.

Pracujesz w bibliotece uniwersyteckiej.

You're in the middle of a quiet afternoon

Jest środek spokojnego popołudnia,

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

kiedy nagle przybywa dostawa 1280 książek.

Książki zostały ułożone w jednym, długim rzędzie

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

but they're all out of order,

w losowej kolejności,

and the automatic sorting system is broken.

a automatyczny system do segregacji jest zepsuty.

Co gorsza, jutro zaczynają się zajęcia,

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

co oznacza, że z samego rana

students will show up in droves looking for these books.

książek będą szukać tłumy studentów.

How can you get them all sorted in time?

Jak posortować je na czas?

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

Jeden ze sposobów to rozpoczęcie od pierwszej pary książek z jednego końca.

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

Jeśli dwie pierwsze książki są dobrze ułożone, zostaw je bez zmian.

Otherwise, swap them.

W przeciwnym razie zamień je miejscami.

Then, look at the second and third books,

Teraz spójrz na drugą i trzecią książkę,

repeat the process,

powtórz proces

and continue until you reach the end of the line.

i kontynuuj, aż dotrzesz do końca linii.

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

W końcu natkniesz się na książkę, która powinna być ostatnia.

and keep swapping it with every subsequent book,

Zamieniaj ją z każdą kolejną książką,

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

przesuwając wzdłuż rzędu aż na koniec.

Then, start from the beginning and repeat the process

Następnie zacznij od początku i powtórz cały proces,

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

żeby umieścić przedostatnią książkę na swoim miejscu.

and keep going until all books are sorted.

Kontynuuj, aż książki będą posortowane.

This approach is called Bubble Sort.

Ten sposób to sortowanie bąbelkowe.

It's simple but slow.

Jest łatwe, ale powolne.

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

W pierwszej rundzie byłoby 1279 porównań,

then 1,278, and so on,

w kolejnej 1278 i tak dalej,

adding up to 818,560 comparisons.

co w sumie daje 818 560 porównań.

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

Gdyby każde zajęło tylko sekundę, proces potrwałby ponad dziewięć dni.

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

Inny sposób rozpoczyna się od ułożenia tylko dwóch pierwszych książek.

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

Następnie weź trzecią książkę i porównaj do tej stojącej na drugim miejscu.

If it belongs before the second book, swap them,

Jeśli powinna znaleźć się przed nią, zamień je.

then compare it with the book in the first spot,

Potem porównaj ją do pierwszej książki

and swap again if needed.

i jeśli trzeba, zamień miejscami.

Now you've sorted the first three books.

Trzy pierwsze książki są już posortowane.

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

Dodawaj po jednej nowej książce do posortowanej grupy,

comparing and swapping the new book with the one before it

porównując ją i zamieniając z książką stojącą przed nią,

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

aż trafi na właściwe miejsce.

Ten sposób to sortowanie przez wstawianie.

This is called Insertion Sort.

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

W odróżnieniu od sortowania bąbelkowego nie trzeba porównywać każdej pary książek.

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

Każdą książkę będzie trzeba porównać średnio

to half of the books that came before it.

tylko z połową tych, stojących przed nią.

In that case, the total number of comparisons

W tym przypadku całkowita liczba porównań

would be 409,280,

wyniosłaby 409 280,

taking almost five days.

co zajęłoby prawie pięć dni.

To wciąż zbyt wiele porównań.

You're still doing way too many comparisons.

Here's a better idea.

Oto lepszy pomysł.

First, pick a random book.

Najpierw wybierz przypadkową książkę.

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

Nazwijmy ją przegrodą i porównajmy z pozostałymi książkami.

Then, divide the line

Następnie podzielmy rząd,

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

umieszczając wszystkie książki, które mają znaleźć się przed przegrodą po jej lewej,

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

a te, które powinny stanąć za nią, po jej prawej stronie.

You've just saved loads of time

Właśnie oszczędziliśmy mnóstwo czasu.

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

Już nie będzie trzeba porównywać żadnej z książek po lewej

to any of the ones on the right ever again.

do tych po prawej stronie.

Now, looking only at the books on the left,

Teraz patrząc tylko na książki po lewej stronie,

you can again pick a random partition book

można wybrać przypadkową przegrodę

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

i oddzielić książki, mające stać przed, od tych, które powinny stanąć za nią.

You can keep creating sub-partitions like this

Można dalej tworzyć takie przegrody,

until you have a bunch of small sub-lines,

aż uzyska się wiele małych grup,

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

z których każdą posortuje się, używając innej strategii.

Each round of partitioning requires about 1,280 comparisons.

Każde rozdzielenie wymaga około 1280 porównań.

If your partitions are pretty balanced,

Jeśli segmenty są w miarę równe,

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

podzielenie książek na 128 grup po 10 będzie wymagało około siedmiu rund

or 8,960 seconds.

albo 8960 sekund.

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

Posortowanie każdej grupy zajmie wtedy około 22 sekund.

All in all, this method known as QuickSort

Tak czy inaczej ta metoda znana jako sortowanie szybkie

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

może posortować książki w mniej niż 3,5 godziny.

But there's a catch.

Ale jest haczyk.

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

Segmenty mogą okazać się niesymetryczne, co oznacza brak oszczędności czasu.

Luckily, this rarely happens.

Na szczęście rzadko się to zdarza.

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

Dlatego sortowanie szybkie to jedna z najbardziej wydajnych strategii

used by programmers today.

używanych przez dzisiejszych programistów.

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

Korzysta się z niej do sortowania towarów w sklepie internetowym według ceny

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

albo tworzenia listy pobliskich stacji benzynowych,

sorted by distance.

ułożonych według odległości.

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

Właśnie udało się skończyć szybkie sortowanie przed czasem.

Just another high-stakes day in the library.

Za tobą kolejny pracowity dzień w bibliotece.