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

right = [2,4,6,7,8,8,10,12,13,14]

newcab=merging(left,right)

Код в листинге 4.4 создает newcab — список, содержащий все элементы left и right, объединенные и упорядоченные. Чтобы убедиться в том, что функция слияния сработала, выполните команду print(newcab).

От слияния к сортировке

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

import math

def mergesort_two_elements(cabinet):

    newcabinet = []

    if(len(cabinet) == 1):

        newcabinet = cabinet

    else:

        left = cabinet[:math.floor(len(cabinet)/2)]

        right = cabinet[math.floor(len(cabinet)/2):]

        newcabinet = merging(left,right)

    return(newcabinet)

В этом коде синтаксис индексирования списков Python используется для разбие­ния сортируемой полки на две: левую и правую. В строках, определяющих left и right, выражения :math.floor(len(cabinet)/2) и math.floor(len(cabinet)/2): обозначают всю первую и всю вторую половину исходной полки соответственно. Эту функцию можно вызвать с любым списком, содержащим один или два элемента, — например, mergesort_two_elements([3,1]) — и убедиться в том, что она успешно возвращает отсортированный результат.

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

def mergesort_four_elements(cabinet):

    newcabinet = []

    if(len(cabinet) == 1):

        newcabinet = cabinet

    else:

        left = mergesort_two_elements(cabinet[:math.floor(len(cabinet)/2)])

        right = mergesort_two_elements(cabinet[math.floor(len(cabinet)/2):])

        newcabinet = merging(left,right)

    return(newcabinet)

cabinet = [2,6,4,1]

newcabinet = mergesort_four_elements(cabinet)

Можно и дальше продолжать писать такие функции, работающие со списками все большего размера. Но настоящий прорыв наступает, когда вы осознаете, что весь процесс можно свернуть с помощью рекурсии. Возьмем функцию из листинга 4.5 и сравним ее с предыдущей функцией mergesort_four_elements().

Листинг 4.5. Реализация функции сортировки слиянием

def mergesort(cabinet):

    newcabinet = []

    if(len(cabinet) == 1):

        newcabinet = cabinet

    else:

    ❶ left = mergesort(cabinet[:math.floor(len(cabinet)/2)])

    ❷ right = mergesort(cabinet[math.floor(len(cabinet)/2):])

        newcabinet = merging(left,right)

    return(newcabinet)

Как видите, функция почти идентична функции mergesort_four_elements(). Принципиальные отличия заключаются в том, что при создании отсортированных списков left и right она не вызывает другую функцию, работающую с меньшими списками. Вместо этого она вызывает сама себя для меньшего списка ❶❷. Сор­тировка слиянием относится к категории алгоритмов «разделяй и властвуй». Мы начинаем с большого несортированного списка. Последовательно разбиваем его на фрагменты все меньшего размера, пока не получим заведомо отсортированные списки из одного элемента, после чего начинаем выполнять их слияние, пока не вернемся к одному большому отсортированному списку. Вы можете вызвать функцию сортировки слиянием для списка любого размера и убедиться в том, что она работает:

cabinet = [4,1,3,2,6,3,18,2,9,7,3,1,2.5,-9]

newcabinet = mergesort(cabinet)

print(newcabinet)

В результате объединения всего кода сортировки слиянием будет получен список 4.6.

Листинг 4.6. Полный код сортировки слиянием

def merging(left,right):

    newcabinet = []

    while(min(len(left),len(right)) > 0):

        if left[0] > right[0]:

            to_insert = right.pop(0)

            newcabinet.append(to_insert)

        elif left[0] <= right[0]:

            to_insert = left.pop(0)

            newcabinet.append(to_insert)