Алгоритмы неформально. Инструкция для начинающих питонистов - [31]
Сортировка слиянием
Алгоритм сортировки слиянием намного быстрее сортировки методом вставки. Как и сортировка методом вставки, сортировка слиянием состоит из двух частей: одна объединяет два списка (слияние), а другая многократно использует слияние для выполнения фактической сортировки.
Прежде чем переходить к сортировке, рассмотрим сам процесс слияния. Допустим, имеются две полки с папками, каждая из которых отсортирована, но содержимое одной полки не сравнивалось с содержимым другой. Требуется объединить содержимое полок на одной итоговой полке, которая будет полностью отсортирована. Назовем эту операцию слиянием двух отсортированных полок. Как подойти к решению этой задачи?
И снова стоит подумать, как бы вы подошли к решению этой задачи с настоящими полками, прежде чем запускать Python и браться за программирование. Представьте, что вы стоите перед тремя полками: двумя заполненными и отсортированными, содержимое которых требуется объединить, и третьей пустой, на которую будут вставляться папки и которая в конечном счете будет содержать все папки с двух исходных полок. Для удобства будем называть две исходные полки левой и правой (предполагается, что они стоят слева и справа от вас).
Слияние
Чтобы выполнить слияние, возьмем первую папку с каждой из двух исходных полок: с левой полки в левую руку, а с правой полки — в правую. Папка с меньшим номером ставится на новую полку первой. Чтобы определить вторую папку для новой полки, снова возьмем первые папки с левой и правой полок, сравним их и вставим меньшую на последнюю позицию новой полки. Когда левая или правая полка опустеет, мы берем оставшиеся файлы на непустой полке и размещаем их все вместе в конце новой полки. После этого новая полка будет содержать все файлы с левой и правой полки, отсортированные по порядку. В результате содержимое двух исходных полок будет успешно объединено.
В коде Python переменные left и right будут представлять исходные отсортированные полки. Мы также определим список newcabinet, который изначально пуст, а после выполнения будет содержать полный упорядоченный набор всех элементов left и right.
newcabinet = []
Определим исходные списки, которым будут присвоены имена left и right:
left = [1,3,4,4,5,7,8,9]
right = [2,4,6,7,8,8,10,12,13,14]
Для сравнения соответствующих первых элементов списков left и right будут использоваться следующие команды if, которые можно будет выполнить только после заполнения секций --...--:
if left[0] > right[0]:
--...--
elif left[0] <= right[0]:
--...--
Если первый элемент списка left меньше первого элемента списка right, то нужно извлечь этот элемент из левого списка и вставить его в newcabinet, и наоборот. Для выполнения этой операции можно воспользоваться встроенной функцией Python pop(), которая вставляется в команду if следующим образом:
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)
Этот процесс — проверка первых элементов списков left и right и извлечение подходящего элемента в новый список — должен продолжаться, пока на обеих полках стоит хотя бы одна папка. По этой причине команды if включаются в цикл while, который проверяет минимальную длину списков left и right. Пока они содержат хотя бы один элемент, процесс продолжается:
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)
Цикл while продолжает выполняться, пока в списках left или right не закончатся элементы для вставки. В этот момент, если список left пуст, все файлы из right вставляются в конец новой полки в текущем порядке, и наоборот. Итоговая вставка может выполняться следующим образом:
if(len(left) > 0):
for i in left:
newcabinet.append(i)
if(len(right) > 0):
for i in right:
newcabinet.append(i)
Наконец, мы объединяем все эти фрагменты в итоговый алгоритм слияния на Python (листинг 4.4).
Листинг 4.4. Алгоритм слияния двух отсортированных списков
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)
if(len(left) > 0):
for i in left:
newcabinet.append(i)
if(len(right)>0):
for i in right:
newcabinet.append(i)
return(newcabinet)
left = [1,3,4,4,5,7,8,9]
