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

Самый быстрый способ расставить книги в алфавитном порядке — Чанд Джон

Переводчик: Nataliia Pysemska Редактор: Yekaterina Jussupova

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.

Если каждое из них займёт секунду, весь процесс растянется на 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.

Каждый этап разделения требует примерно 1 280 сравнений.

If your partitions are pretty balanced,

Если ряд разделён более-менее равномерно —

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

на 128 групп по 10 книг, — то вы справитесь за 7 этапов,

or 8,960 seconds.

или 8 960 секунд.

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.

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

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.

Всего лишь ещё один напряжённый день в библиотеке.