Алгоритмы для жизни: Простые способы принимать верные решения - [31]

Все преимущество этого метода заключается в том, что в нем применяется и линейное, и квадратичное время, а именно линейно-логарифмическое время, которое обозначается формулой O(nlog n).

Каждое перекладывание карты удваивает количество отсортированных пачек. Таким образом, чтобы полностью отсортировать n карт, вам необходимо переложить карты количество раз, равное цифре 2, умноженной на себя столько раз, чтобы конечный результат был равен n. Другими словами, это логарифм n по основанию 2.

Вы можете одновременно сортировать до четырех карт в два действия, до восьми карт третьим действием и до шестнадцати с помощью четвертого перекладывания. Подход «дели и побеждай», лежащий в основе метода сортировки с объединением, вдохновил на создание ряда других линейно-логарифмических алгоритмов, которые начали динамично развиваться. Сказать, что линейно-логарифмические алгоритмы – это всего лишь усовершенствованная версия квадратичных, – значит недопустимо занизить их значимость. В случае сортировки количества элементов, которое мы имеем при переписи населения, это промежуток между двадцатью девятью действиями по перекладыванию карт и тремя сотнями миллионов таких действий. Неудивительно, что этот метод выбирают для решения крупномасштабных промышленных задач.

Сортировка с объединением применяется также и в решении задач бытового масштаба. Отчасти причина популярности этого метода лежит в том, что такие сортировки легко выполняются параллельно. Если в ваши планы все еще входит наведение порядка на полке, то решение задачи согласно методу сортировки с объединением будет таким: закажите пиццу и пригласите несколько друзей; затем поделите количество книг поровну между вашими друзьями, и пусть каждый отсортирует свою часть; после этого пусть друзья разобьются по парам и отсортируют книги вдвоем. Процесс необходимо продолжать до тех пор, пока у вас не сложится две стопки книг и вам останется только объединить их в одну и поставить на полку. Только постарайтесь избежать жирных пятен от пиццы на книгах.

За гранью сравнения: перехитрить алгоритм

В неприметной промзоне неподалеку от города Престон округа Вашингтон, спрятавшись за общим входом в многочисленные офисы, расположился цех чемпиона Национальной библиотеки 2011 и 2013 года по сортировке. Длинный сегментированный конвейер переносит 167 книг в минуту – 85 000 в день – в сканер штрихкодов, где они автоматически перенаправляются к своего рода створкам бомбового отсека, через которые книги выбрасываются в одну из 96 корзин.

Сортировочный центр Престона – один из крупнейших и наиболее эффективных объектов в мире в области книжной сортировки. Центром управляет Библиотечная система округа Кинг. Она соперничает с аналогично оснащенной Публичной библиотекой Нью-Йорка уже четыре года, на протяжении которых организации попеременно передают пальму первенства друг другу. «Библиотека округа Кинг в этом году обойдет нас? – спросил заместитель директора управления библиотеки Нью-Йорка по работе с книжным фондом Сальваторе Магаддино прежде, чем вступить в новую схватку в 2014 году. – Даже не думайте».

С теоретической точки зрения, организация работы в Престонском сортирочном центре тоже не может не впечатлить. Книги, проходящие через его системы, сортируются в условиях линейного времени O(n).

Важно отметить, что линейно-логарифмическое время O(n log n), которое применяется в методе сортировки с объединением, – действительно лучший показатель, которого мы только можем добиться. Было доказано, что если мы хотим полностью отсортировать n элементов посредством прямого сравнительного исследования, то у нас только один выход – сравнивать их O(n log n) количество раз. Это фундаментальный закон Вселенной, и нет способа его обойти.

Но это не значит, что мы можем закончить нашу книгу на алгоритмах сортировки. Потому что иногда вам и не нужен полностью упорядоченный комплект и порой сортировку можно выполнить и без непосредственного сравнения одного элемента с другим.

Два вышеупомянутых принципа, вместе взятые, предусматривают возможность проведения грубых практических сортировок быстрее линейно-логарифмического времени. Этот факт очень наглядно демонстрирует алгоритм, известный как сортировка группировками, который и применяется в Престонском сортировочном центре. При применении этого метода элементы разбиваются на группы по количеству категорий сортировки без проведения межкатегорийной сортировки (это можно сделать позднее). (В компьютерной науке термин «корзина» обозначает фрагмент неупорядоченных данных, но некоторые довольно-таки буквально воспринимают название метода и применяют его в своей работе, как, например, это делают в Библиотечной системе округа Кинг.)

А вот и изюминка этого метода: если вы хотите сгруппировать n единиц в m корзин, то весь процесс займет у вас время, рассчитываемое по формуле O(n · m), – то есть время, прямо пропорциональное количеству категорий, умноженному на количество корзин.

И поскольку количество корзин относительно невелико по сравнению с количеством сортируемых единиц, то «О большое» округлит показатель времени до O(