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

Translator: Iviana Gicheva Reviewer: Anton Hikov

You work at the college library.

Работите в колежанска библиотека.

You're in the middle of a quiet afternoon

В средата на тих, спокоен следобед сте,

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

когато пристига пратка от 1 280 книги.

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

Книгите са сортирани в редица,

but they're all out of order,

но не са подредени,

and the automatic sorting system is broken.

а автоматичната система за подредба не работи.

To make matters worse, classes start tomorrow,

За да станат нещата още по-лоши, занятията започват утре,

which means that first thing in the morning,

което означава, че първото нещо сутринта ще е

students will show up in droves looking for these books.

студентите да дойдат на тълпи, за да търсят тези книги.

How can you get them all sorted in time?

Как можеш да ги подредиш навреме?

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

Един вариант е да започнете от единия край на линията с първата двойка книги.

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

Ако първите две книги са по азбучен ред, ги оставете както са.

Otherwise, swap them.

Ако ли не, ги разместете.

Then, look at the second and third books,

След това, прегледайте втората и третата двойка,

repeat the process,

повторете процеса

and continue until you reach the end of the line.

и продължавайте, докато стигнете до края на редицата.

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

В някакъв момент ще се натъкнете на книга, която трябва да е последна

and keep swapping it with every subsequent book,

и ще продължавате да я разменяте с всяка следваща книга,

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

предвижвайки я към края на линията, докато достигнете мястото ѝ.

Then, start from the beginning and repeat the process

След това, започнете отначало и повторете процеса

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

като подребите втората и последната книга на местата им,

and keep going until all books are sorted.

и продължавайте, докато подредите всички книги.

This approach is called Bubble Sort.

Този метод се нарича "Сортиране на балончета".

It's simple but slow.

Лесен е, но бавен.

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

Първоначално ще направите 1 279 сравнения,

then 1,278, and so on,

след това 1 278 и така нататък,

adding up to 818,560 comparisons.

стигайки до 818 560 сравнения.

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

Ако всяко от тях отнема само 1 секунда, процесът ще отнеме над 9 дни.

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

Втора стратегия би била да се започне чрез сортиране само на първите две книги.

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

След това вземете третата книга и я сравнете с книгата на второто място.

If it belongs before the second book, swap them,

Ако мястото ѝ е преди втората книга, разменете ги,

then compare it with the book in the first spot,

след това я сравнете с книгата на първо място,

and swap again if needed.

и ги разменете отново, ако се налага.

Now you've sorted the first three books.

Сега подредихте първите три книги.

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

Продължете да добавяте по една книга към вече подредените книги,

comparing and swapping the new book with the one before it

сравнявайки и размяйки новата книга с тази преди нея,

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

докато намерите правилното ѝ място сред вече подредените книги.

This is called Insertion Sort.

Това се нарича "Сортиране чрез вмъкване".

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

За разлика от "Сортиране на балончета", не е нужно да сравнявате всеки чифт книги.

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

Средно, очаква се да е необходимо да сравните всяка книга

to half of the books that came before it.

с половината книги преди нея.

In that case, the total number of comparisons

В този случай, общият брой сравнения

would be 409,280,

ще бъде 409 280,

taking almost five days.

отнемайки почти пет дни.

You're still doing way too many comparisons.

Все още се налага да правите прекалено много сравнения.

Here's a better idea.

Ето по-добра идея.

First, pick a random book.

Първо, изберете книга на случаен принцип.

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

Да кажем, че тя е "разделение" и я сравнете с всяка друга книга.

Then, divide the line

След това, разделете линията

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

като сложите всички книги, които трябва да са преди разделението отляво

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

и тези, които са след него, отдясно.

You've just saved loads of time

Спести доста време

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

след като не е нужно изобщо да сравняваш книгите отляво

to any of the ones on the right ever again.

с тези отдясно.

Now, looking only at the books on the left,

Сега, преглеждайки книгите отляво,

you can again pick a random partition book

можеш да избереш друга разделителна книга

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

и да сортираш тези книги, които са преди нея и тези след нея.

You can keep creating sub-partitions like this

Ако продължиш да създаваш подразделения като това,

until you have a bunch of small sub-lines,

докато направиш куп малки подраздели,

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

би сортирал бързо всеки със стратегия като Метода за вмъкване.

Each round of partitioning requires about 1,280 comparisons.

Всеки кръг на разделяне изисква около 1280 сравнения.

If your partitions are pretty balanced,

Ако дяловете ви са почти еднакви,

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

разделяйки книгите на 128 подраздели от по 10, ще ви отнеме около 7 кръга,

или 8960 секунди.

or 8,960 seconds.

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

Сортирането на тези подредове ще добави около 22 секунди на всеки.

All in all, this method known as QuickSort

Като цяло, чрез този метод, известен като "Бързо сортиране",

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

можете да подредите книгите за по малко от 3 часа и половина.

But there's a catch.

Но има уловка.

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

Всички разделения могат да се окажат неравни и да не спестите време.

За щастие това се случва рядко.

Luckily, this rarely happens.

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

Затова "Бързото сортиране" е една от ефективните стратегии,

used by programmers today.

използвани от програмистите днес.

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

Те я прилагат за подреждане на продукти в онлайн магазин по цена,

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

или създаване на списък с всички бензиностанции близо до дадено място,

sorted by distance.

подредени по разстояние.

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

Във вашия случай, сте направили бързо сортиране с остатък от време.

Поредният ден с високи залози в библиотеката.

Just another high-stakes day in the library.