Мы уже реализовывали функцию merge, которая способна “слить” два отсортированных списка в один.
Чаще всего её применяют в рекурсивном алгоритме сортировки слиянием.
Напишите рекурсивную функцию merge_sort, которая производит сортировку списка.
Примечание
Ваше решение должно содержать только функции.
В решении не должно быть вызовов требуемых функций, за исключением рекурсивных.
Трассировка вызова рекурсивной функции в обработке ответа не учитывается и показана для примера.
Пример
Ввод
result = merge_sort([3, 2, 1])Вывод
# Вызов merge_sort([3, 2, 1])
# Вызов merge_sort([3])
# Вызов merge_sort([2, 1])
# Вызов merge_sort([2])
# Вызов merge_sort([1])
result = [1, 2, 3]Ввод
result = merge_sort([3, 1, 5, 3])Вывод
# Вызов merge_sort([3, 1, 5, 3])
# Вызов merge_sort([3, 1])
# Вызов merge_sort([3])
# Вызов merge_sort([1])
# Вызов merge_sort([5, 3])
# Вызов merge_sort([5])
# Вызов merge_sort([3])
result = [1, 3, 3, 5]Решение
Отличная задача для того, чтобы прочувствовать всю красоту рекурсии. Мы уже умеем сортировать слиянием отсортированные списки, теперь попробуем отсортировать один неотсортированный.
Для того, чтобы решить эту задачу нам надо прийти к двум умозаключениям:
1) любой список можно разбить на примерно равные два списка
2) если каждый из двух списков содержит один или ноль элементов, то можно их отдать на “слияние” и получить отсортированный список, который можно в свою очередь тоже отдать на слияние
Если поразмыслить над этими условиями, то “план войны” становится более-менее понятным.
В момент погружения: Делим списки на части до тех пор пока любая из частей не будет пустой или содержать только один элемент.
В момент всплытия: Сливаем полученные списки.
Поздравляю, вы только что реализовали одну из самых эффективных сортировок!
Посмотреть код
Решение
def merge(left, right):
result = []
pos_left = pos_right = 0
while pos_left < len(left) and pos_right < len(right):
if left[pos_left] < right[pos_right]:
result.append(left[pos_left])
pos_left += 1
else:
result.append(right[pos_right])
pos_right += 1
result += left[pos_left:]
result += right[pos_right:]
return result
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
То есть алгоритм сортировка слиянием это рекурсивный алгоритм?
либо не пойму что такое рекурсивный алгоритм
в части функции merge_sort – да, вспомогательная функция merge нерекурсивна.
Спасибо большое! благодаря вашему ответу смог сам написать код. Правда он проходит только первые два теста. Я исправил код чтобы он работал если в nums будет одно число. Других ситуаций пока нем могу вспомнить.
def merge_sort(nums: list):
“””В части функции merge_sort – да, вспомогательная функция merge нерекурсивна”””
def merge(sequence_1, sequence_2):
pos1 = 0
pos2 = 0
sequence = []
while pos1 < len(sequence_1) and pos2 < len(sequence_2):
if sequence_1[pos1] > sequence_2[pos2]:
sequence.append(sequence_2[pos2])
pos2 += 1
else:
sequence.append(sequence_1[pos1])
pos1 += 1
sequence.extend(sequence_1[pos1:])
sequence.extend(sequence_2[pos2:])
return sequence
first = nums[:1]
last = nums[1:]
if len(last) > 1:
last = merge_sort(last)
res = merge(first, last)
return res
Очень рад этому, какое-то понимание начинает появляться!
Предварительно конечно написал код J. Слияние, но там уже сам не справился))))
а где сортировка first?
res = merge(first, last)
assert merge_sort([3, 1, 5, 3]) == [1, 3, 3, 5]
Проверку проходит
def merge_sort(nums: list):
“””В части функции merge_sort – да, вспомогательная функция merge нерекурсивна”””
def merge(sequence_1, sequence_2):
pos1 = 0
pos2 = 0
sequence = []
while pos1 < len(sequence_1) and pos2 < len(sequence_2):
if sequence_1[pos1] > sequence_2[pos2]:
sequence.append(sequence_2[pos2])
pos2 += 1
else:
sequence.append(sequence_1[pos1])
pos1 += 1
sequence.extend(sequence_1[pos1:])
sequence.extend(sequence_2[pos2:])
return sequence
first = nums[:1]
last = nums[1:]
if len(last) > 1:
last = merge_sort(last)
return merge(first, last)
# assert merge_sort([]) == []
assert merge_sort([2, 1]) == [1, 2]
# assert merge_sort([1, 2, 3]) == [1, 2, 3]
# assert merge_sort([1, 1, 1]) == [1, 1, 1]
# assert merge_sort([-3, -2, -1]) == [-3, -2, -1]
# assert merge_sort([-3, -1, -2]) == [-3, -2, -1]
# assert merge_sort([3]) == [3]
# assert merge_sort([-2, 0, 3, 1, 0, 5, 3, -10]) == [-10, -2, 0, 0, 1, 3, 3, 5]
# assert merge_sort([3, 2, 1]) == [1, 2, 3]
assert merge_sort([3, 1, 5, 3]) == [1, 3, 3, 5]
хочу проверить останется ли форматирование кода
Сергей, скажите, пожалуйста, рационально ли следующее решение (более компактное и, если так можно сказать, без “привязки” к индексам)?
В задаче “Сортировка слиянием” Вы писали, что решение с удалением использованных элементов из списка – очень наглядное, но неэффективное с точки зрения производительности. Прошу прощения за уточнение, но это прямо критично плохо (удаление)? Стоит ли вообще его использовать?
def merge_sort(sp):
if len(sp) <= 1:
return sp
mid = len(sp) // 2
left = merge_sort(sp[:mid])
right = merge_sort(sp[mid:])
return merge(left, right)
def merge(left, right):
sp_new = []
while left and right:
if left[0] < right[0]:
sp_new.append(left.pop(0))
else:
sp_new.append(right.pop(0))
sp_new.extend(left)
sp_new.extend(right)
return sp_new
Вопрос довольно непростой. В общем случае ответ сильно зависит от того какой язык программирования, какая версия этого языка и какой процессор используется. Помимо этого надо учитывать какой объем данных обрабатывается.
В общем случае операция удаления нулевого элемента списка сильно дороже операции удаления последнего элемента.
Поэтому если читабельность важнее производительности (это примерно 80% программ), можно использовать. Если производительность важна, лучше воздержаться.
Спасибо огромное за ответ! Очень-очень все понятно.
Тогда еще вот такой вариант придумался – тоже компактный, но уже без удаления элементов.
def merge_sort(sp):
if len(sp) <= 1:
return sp
mid = len(sp) // 2
left = merge_sort(sp[:mid])
right = merge_sort(sp[mid:])
return merge(left, right)
def merge(left, right):
sp_new = []
while left and right:
if left[0] < right[0]:
sp_new.append(left[0])
left = left[1:]
else:
sp_new.append(right[0])
right = right[1:]
sp_new.extend(left)
sp_new.extend(right)
return sp_new
Здравствуйте. Я не совсем понимаю моменты с погружением, а именно как это все устроенно, что вообще значит. Я уже читал ваше объяснение про это, на простых примерах все ясно, но как дела доходит до подобных задач, то я ничего не понимаю. Объясните пожалуйста на этом примере, ну или на любом другом
На сайте есть статья про погружение и всплытие.Это термины, которыми, на мой взгляд, довольно удобно описывать смысл рекурсии.
Если говорить по пример, то рассмотрим к примеру массив [7 6 5 4 3 2 1].
При погружении мы все, что имеет длину больше 1 делим пополам или примерно пополам:
Таким образом у нас получатся массивы [7 6 5 4] и [3 2 1] к каждому из которых мы можем применить тот же алгоритм, что и к целому массиву.
Рассмотрим ветку [3 2 1] так как она немного интереснее сосдней.
Этот массив делится пополам и получается два [3 2] и [1] к каждой половинке мы примеряем тот же алгоритм (рекурсивно вызываем нашу функцию деления).
Массив [3 2] делится на два – [3] и [2], в то время как массив [1] остается неделимым.
Так как больше делить напополам нечего, мы начинаем всплывать и собирать наши массивы. Напомню, что на предпоследнем уровне наш изначальный массив получает вид
[7 6] [5 4] [3 2] [1]
а на последнем уже
[7] [6] [5] [4] [3] [2]
обратите внимание, что [1] на этот уровень уже не провалился, он остался на предпоследнем.
каждый таким массивом на каждом уровне занимается своя копия нашей функции, которая не имеет представления сколько еще таких массивов существует и кто ими занимается – ей это неважно.
Итак продолжим с нашим [3 2 1]
на этапе всплытия мы встречаем на самом нижнем уровне два массива [3] и [2].
Сравниваем элементы и меньший из них записываем в новый массив (список). Получаем [2]
При этом список который мы обрабатываем получает вид [3] [].
При проверке длины списка мы видим, что один из списков пут, а зхначит другом остались числа большие, чем последнее число нашего результирующего списка и его можно просто приписать к результату. Получаем [2 3] на этом этапе можно всплывать дальше.
Этажом выше нас ждет [1]. таким образом мы имеем два списка [2 3] и [1].
сравниваем первые элементы списков – 1 < 2, а значит в результат мы забираем [1]. оставшиеся списки – [2 3] и []. Так как один из списков пуст, как и в прошлом случае мы просто можем добавить оставшийся список к результату. Он гарантированно был отсортирован на предыдущих этажах нашего алгоритма.в итоге получаем результат [1 2 3] и всплываем выше.
Там нас уже ждет готовый к слиянию [4 5 6 7], который был отсортирован по точно такому же алгоритму при погружении и всплытии в соседней ветке рекурсии.
Итак, мы имеем [1 2 3] и [4 5 6 7]. Мы сравниваем первые элементы списков и меньший забираем в результат
result = [1]
left = [2, 3]
right = [4, 5, 6, 7]
снова сравниваем первые элементы. 2 < 4
result = [1, 2]
left = [3]
right = [4, 5, 6, 7]
после очередной итерации у нас получается пустой список и мы по аналогии с предыдущими шагами просто приписываем оставшийся отсортированный список к результату.
Без предварительной подготовки и опыта, это все равно трудно понять умозрительно, поэтому проще всего проделать это с карточками, на которых можно написать числа и “спуская” их каждый раз на “этаж ниже” на столе посмотреть как это работает в “механике”. когда они все разобьются по одной, можно начать всплывать и собирать их в один массив, всплывая.