Алгоритмы неформально. Инструкция для начинающих питонистов - [25]

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

Сортировка методом вставки

Представьте, что вас попросили рассортировать все папки в канцелярском шкафу. Каждой папке присвоен номер, и вы должны переставить папки, чтобы папка с наименьшим номером стояла на первом месте, а папка с наибольшим — на последнем. Промежуточные папки должны стоять между ними по порядку.

Какой бы способ вы ни выбрали, его можно описать как алгоритм сортировки. Но еще до того, как вы решили открыть Python с целью написать такой алгоритм, ненадолго остановитесь и подумайте, как бы вы отсортировали такие папки в реальной жизни. Задача может показаться простой, но позвольте вашему внутреннему искателю приключений оценить широкий диапазон возможностей.

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

Вставка в сортировке методом вставки

Начнем с самой задачи вставки. Представьте, что вы стоите перед канцелярским шкафом, в котором папки уже идеально отсортированы. Кто-то подает вам новую папку и просит вставить в правильную (в порядке сортировки) позицию на полке. Как вы будете это делать? Задача может показаться настолько простой, что не требует объяснений, и вообще непонятно, возможно ли такое объяснение. (Что значит — как делать? Просто берете и делаете!) Но в мире алгоритмов каждую операцию, какой бы тривиальной она ни была, необходимо полностью объяснить.

Ниже описан разумный алгоритм вставки одной папки в отсортированную последовательность папок. Мы можем сравнить две папки и определить, что одна папка «больше» другой. Это может означать, что номер, присвоенный одной папке, больше номера другой либо занимает более высокую позицию по алфавиту или другому критерию.

1. Выбрать наибольшую папку на полке. (Начать с конца полки и двигаться к началу.)

2. Сравнить выбранную папку с той, которую нужно вставить.

3. Если выбранная папка меньше вставляемой, то поместить вставляемую папку в следующую позицию после выбранной.

4. Если выбранная папка больше вставляемой, то выбрать следующую папку на полке (ближе к началу).

5. Повторять шаги 2–4, пока папка не будет вставлена или пока вы не сравните ее с каждой существующей папкой. Если папка еще не была вставлена после сравнения со всеми существующими папками, то вставляется в самое начало полки.

Этот метод более или менее совпадает с интуитивным представлением о том, как вставить запись в отсортированный список. При желании также можно начать с начала списка, а не с конца, и применить аналогичный процесс с теми же результатами. Обратите внимание: мы не просто вставляем запись, а вставляем ее в правильной позиции, так что после вставки список остается отсортированным. Мы можем написать сценарий на языке Python, который выполняет этот алгоритм вставки. Сначала определим полку с отсортированными папками. В данном случае она будет представлена списком Python, а папки — обычными числами.

cabinet = [1,2,3,3,4,6,8,12]

Затем определяется «папка» (в данном случае просто число), которую нужно поставить на полку:

to_insert = 5

Мы последовательно перебираем все числа в списке (все папки на полке). Определим переменную check_location. Как было сказано выше, в ней будет храниться позиция проверяемой папки на полке. Начнем от конца полки:

check_location = len(cabinet) - 1

Определим также переменную insert_location. Цель нашего алгоритма — определить правильное значение insert_location, после чего останется только вставить папку в insert_location. Будем считать, что изначально переменная insert_location равна 0:

insert_location = 0

Затем простая команда if проверяет, что вставляемая папка больше папки в позиции check_location. Как только будет обнаружено число, меньшее, чем вставляемое, мы используем его позицию для определения места вставки нового числа. Значение увеличивается на 1, поскольку вставка выполняется в позиции непосредственно за меньшим найденным числом:

if to_insert > cabinet[check_location]:

    insert_location = check_location + 1

Определив правильную позицию insert_location для вставки папки на полку, можно воспользоваться встроенным методом Python insert для работы со спис­ками: