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

cabinet.insert(insert_location,to_insert)

Впрочем, выполнение этого кода еще не приведет к вставке папки в нужную позицию. Необходимо объединить все действия в одну связную функцию. Она объединяет весь приведенный выше код, а также добавляет цикл while. Тот перебирает все папки на полке, начиная с последней и продвигаясь вперед до тех пор, пока не будет найдена правильная позиция insert_location или не будет проверена каждая папка. Окончательная версия кода вставки приведена в листинге 4.1.

Листинг 4.1. Вставка папки с заданным номером на полку

def insert_cabinet(cabinet,to_insert):

  check_location = len(cabinet) - 1

  insert_location = 0

  while(check_location >= 0):

    if to_insert > cabinet[check_location]:

        insert_location = check_location + 1

        check_location = - 1

    check_location = check_location - 1

  cabinet.insert(insert_location,to_insert)

  return(cabinet)

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

newcabinet = insert_cabinet(cabinet,5)

print(newcabinet)

Если выполнить код из листинга 4.1, то он выведет список newcabinet, в котором теперь присутствует новая «папка» 5, вставленная в правильной позиции (между 4 и 6).

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

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

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

В языке Python сначала создаются переменные для двух полок: несортированной и пустой новой:

cabinet = [8,4,6,1,2,5,3,7]

newcabinet = []

Сортировка методом вставки реализуется многократным вызовом функции insert_cabinet() из листинга 4.1. При вызове ей необходимо передать папку, которая предварительно снимается с несортированной полки:

to_insert = cabinet.pop(0)

newcabinet = insert_cabinet(newcabinet, to_insert)

В этом фрагменте используется метод pop(). Он удаляет из списка элемент с заданным индексом. В данном случае из cabinet удаляется элемент с индексом 0. После использования pop()cabinet уже не содержит этот элемент, поэтому он сохраняется в переменной to_insert, чтобы его можно было поместить в newcabinet.

В листинге 4.2 все эти элементы собраны воедино. Мы определяем функцию insertion_sort(), которая перебирает все элементы несортированного списка cabinet и вставляет их один за другим в newcabinet. Наконец, после выполнения списка выводится результат — отсортированная версия sortedcabinet.

Листинг 4.2. Реализация сортировки методом вставки

cabinet = [8,4,6,1,2,5,3,7]

def insertion_sort(cabinet):

  newcabinet = []

  while len(cabinet) > 0:

    to_insert = cabinet.pop(0)

    newcabinet = insert_cabinet(newcabinet, to_insert)

  return(newcabinet)

sortedcabinet = insertion_sort(cabinet)

print(sortedcabinet)

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

Оценка эффективности алгоритма

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