Как быстрее всего рассортировать книги на полке?

0
1344
Книжная полка

Под сравнением книг понимается сравнение названий книг в соответствии с алфавитом русского языка (например, книга Фиалки будет стоять после книги Алгебра, так как Ф стоит после А в русском алфавите).

Способ №1

Начать с первых двух книг. Если они в правильном порядке, то оставить все как есть; иначе поменять их местами. Потом сделать то же самое со 2 и 3 книгами. Затем – с 3 и 4, и так далее, пока последняя книга не окажется на своем месте.

Повторять такой процесс пока не отсортируешь все книги. Данный алгоритм называется Сортировка Пузыриком (Bubble Sort). Она простая, но медленная.

На первом круге придется сделать 1 279 сравнений (1 280 книг – 1). На втором – 1 298 и так далее. Таким образом, для выполнения задачи необходимо сделать 818 560 сравнений. Если сравнение двух книг займет 1 секунду, то весь процесс сортировки затянется на 9,5 дней!

Способ №2

Начнем тоже с первых двух книг. Если они не на своем порядке, то меняем их местами. Дальше возьмем третью книгу и сравним её со второй. Если они в правильном порядке, то оставить все как есть; иначе поменять их местами. Если мы поменяли книги, то сравним вторую книгу и первую (см. рисунок).

Способ 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Добавляй по одной книге и сравнивай её сначала с последней добавленной, затем с предпоследней – и так далее, пока не найдешь ей место. Это называется Сортировка Вставками (Insertion Sort). Нам не надо сравнивать книгу с каждой книгой в ряду, а достаточно сравнить её лишь с половиной книг(книгами, которые стояли до неё). Таким образом, всего будет 202 654 сравнения для данного случая (5 дней работы).

Способ №3

А вот идея получше. Возьми одну любую книгу (назовем её делителем). Затем сравни делитель со всеми книгами в ряду. Поставь все книги, которые идут до делителя слева, остальные – справа. Делитель должен быть между левой и правой частями. Ты сохранил кучу времени, так как тебе не надо сравнивать каждую книгу слева с каждой книгой справа.

Теперь можно проделать данный алгоритм отдельно с левой частью и отдельно с правой. Этот метод требует гораздо меньше времени – примерно 11 776 секунд (3,5 часа), поэтому называется Быстрой Сортировкой (Quick Sort).

Анимация, демонстрирующая работу алгоритма быстрой сортировки.
Анимация, демонстрирующая работу алгоритма быстрой сортировки. Горизонтальные линии обозначают делители. — RolandH, Википедия

Он не очень эффективный, если левая и правая части сильно различаются (например, левая часть составляет 92% от общего числа книг), но такое случается редко. QuickSort используется во многих программах для компьютера – для сортировки товаров в интернет-магазинах, для создания списков самых близких кафе и так далее.