Программисты именуют этот способ довольно логично – сортировкой методом вставок.
Хорошая новость в том, что это, возможно, еще более интуитивно понятный метод, чем пузырьковая сортировка, и у него отнюдь не плохая репутация. Плохая новость в том, что этот способ занимает не меньше времени. Вам все равно приходится ставить на полку по одной книге за раз. Каждый раз нужно просматривать в среднем около половины стоящих на полке книг и находить правильное место для следующей книги. Хотя на практике процесс сортировки методом вставок идет немного быстрее, чем пузырьковая сортировка, мы все равно имеем дело с квадратичным временем. Сортировка более одной книжной полки все равно становится нелегкой задачей.
Прохождение через квадрат: дели и побеждай
После рассмотрения двух абсолютно разумных подходов, которые переходят в плоскость нерационального квадратичного времени, напрашивается вопрос: а существуют ли способы ускорить процесс сортировки?
Вопрос, по сути, о продуктивности. Но если обсудить этот вопрос с программистом, то он становится ближе к метафизике – сродни размышлениям о скорости света, путешествиях во времени, сверхпроводниках и термодинамической энтропии.
Каковы фундаментальные законы и границы вселенной? Что возможно? Что позволено? Так программисты пытаются узреть божьи планы наряду с учеными в области физики частиц и космологии.
Каково минимальное усилие, необходимое для установления порядка?
Возможно ли найти параметр сортировки О(1) (как в случае уборки дома перед приездом компании друзей), по которому можно было бы сортировать любой объем единиц за равное количество времени?
В принципе мы даже не можем утверждать, что процесс сортировки n книг на полке постоянен во времени, поскольку он требует проверки n книг, и это количество, по сути, конечно. Поэтому сортировка книг в условиях временной константы даже не обсуждается.
А если рассмотреть параметр линейного времени О(n), который подобен передаче блюд по кругу за столом, когда удвоение количества объектов удваивает и объем работы? Размышляя о вышеописанных примерах, сложно представить, как же они могут работать. Значение n2 в каждом из этих случаев мы получаем в связи с необходимостью переместить n книг, и работа, которую мы должны проделать при каждом перемещении книги, пропорциональна значению n. Так как же нам уйти от n в степени n и вернуться к самой величине n? При пузырьковой сортировке мы получили значение O(n2) применительно ко времени выполнения задачи, исходя из манипуляций с каждой из n книг и перемещения каждой из них с места на место n раз. В сортировке методом вставок время выполнения задачи было возведено в квадрат, поскольку мы перемещали с места на место n книг и сравнивали их с тем же количеством (n) других книг прежде, чем выбрать место для очередной книги. Применение параметра линейного времени означает, что наши манипуляции с каждой книгой происходят в условиях постоянного времени вне зависимости от количества других книг, среди которых мы должны найти место каждой отдельной книге. Это отнюдь не похоже на правду.
Таким образом, мы знаем, что можем выполнять задачу в условиях квадратичного времени, но, вероятно, не линейного. Возможно, наш лимит находится где-то между линейным и квадратичным временем. Существуют ли какие-либо алгоритмы между линейным и квадратичным, между n и n × n?
Существуют и лежат на поверхности.
Как упоминалось ранее, процессы обработки информации были запущены в США во время проведения переписей населения в XIX веке в результате разработки Германом Холлеритом и впоследствии компанией IBM устройств по сортировке перфокарт. В 1936 году IBM приступила к производству линейки раскладочно-подборочных машин, которые могли объединить две отдельно упорядоченные стопки перфокарт в одну. Если каждая из пачек была разложена в верном порядке, то сам процесс их консолидации был невероятно простым и происходил в линейном времени: необходимо было просто сравнить две верхние карты из каждой стопки между собой, карту с наименьшим порядковым номером переместить в начало новой формируемой пачки и продолжать таким образом до выполнения задачи.
В программе, которую Джон фон Ньюманн написал в 1945 году, чтобы продемонстрировать преимущество ЭВМ с запоминаемой программой, была использована идея подборки и упорядочения перфокарт. Отсортировать две карты легко: просто переложите карту с меньшим порядковым номером поверх второй. И если у вас есть пара стопок по две карты каждая, сложенных в верном порядке, вы таким же способом можете легко сложить их в одну упорядоченную стопку из четырех карт. Повторяя этот прием несколько раз, вы будете получать все бóльшие и бóльшие стопки разложенных в нужном порядке карт. Довольно скоро вы соберете идеально упорядоченную стопку путем финального кульминационного объединения всех карт.
Этот подход сегодня известен как сортировка с объединением – один из легендарных алгоритмов компьютерной науки. Как было сказано в одной газете в 1997 году, «появление этого метода так же значимо в истории теории сортировки, как появление самой сортировки в истории развития программирования».
Все преимущество этого метода заключается в том, что в нем применяется и линейное, и квадратичное время, а именно линейно-логарифмическое время, которое обозначается формулой O(nlog n).
Каждое перекладывание карты удваивает количество отсортированных пачек. Таким образом, чтобы полностью отсортировать n карт, вам необходимо переложить карты количество раз, равное цифре 2, умноженной на себя столько раз, чтобы конечный результат был равен n. Другими словами, это логарифм n по основанию 2.
Вы можете одновременно сортировать до четырех карт в два действия, до восьми карт третьим действием и до шестнадцати с помощью четвертого перекладывания. Подход «дели и побеждай», лежащий в основе метода сортировки с объединением, вдохновил на создание ряда других линейно-логарифмических алгоритмов, которые начали динамично развиваться. Сказать, что линейно-логарифмические алгоритмы – это всего лишь усовершенствованная версия квадратичных, – значит недопустимо занизить их значимость. В случае сортировки количества элементов, которое мы имеем при переписи населения, это промежуток между двадцатью девятью действиями по перекладыванию карт и тремя сотнями миллионов таких действий. Неудивительно, что этот метод выбирают для решения крупномасштабных промышленных задач.
Сортировка с объединением применяется также и в решении задач бытового масштаба. Отчасти причина популярности этого метода лежит в том, что такие сортировки легко выполняются параллельно. Если в ваши планы все еще входит наведение порядка на полке, то решение задачи согласно методу сортировки с объединением будет таким: закажите пиццу и пригласите несколько друзей; затем поделите количество книг поровну между вашими друзьями, и пусть каждый отсортирует свою часть; после этого пусть друзья разобьются по парам и отсортируют книги вдвоем. Процесс необходимо продолжать до тех пор, пока у вас не сложится две стопки книг и вам останется только объединить их в одну и поставить на полку. Только постарайтесь избежать жирных пятен от пиццы на книгах.
