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

Программисты именуют этот способ довольно логично – сортировкой методом вставок.

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

Прохождение через квадрат: дели и побеждай

После рассмотрения двух абсолютно разумных подходов, которые переходят в плоскость нерационального квадратичного времени, напрашивается вопрос: а существуют ли способы ускорить процесс сортировки?

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

Каковы фундаментальные законы и границы вселенной? Что возможно? Что позволено? Так программисты пытаются узреть божьи планы наряду с учеными в области физики частиц и космологии.

Каково минимальное усилие, необходимое для установления порядка?

Возможно ли найти параметр сортировки О(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 году, «появление этого метода так же значимо в истории теории сортировки, как появление самой сортировки в истории развития программирования».