Доброго времени суток, читатели, зрители моего канала programmer's notes, любители языка Python. Не забывайте подписываться и писать свои
комментарии к моим статьям и видео.
Сортировка слиянием на языке Python
Сегодня говорим о замечательной сортировке слиянием. Замечательна она тем, что ее легко можно использовать в сочетании с любой другой сортировкой. Отсюда, мне кажется, это один из самых эффективных подходов.
Суть сортировки слиянием заключается в следующем:
1. Разбиваем сортируемый массив на две части, например делением пополам.
2. Каждая из частей сортируется по одному из алгоритмов, например, опять же слиянием. Т.е. процесс деления повторяется.
3. Отсортированные части массива сливаются в один.
Понятно, что в алгоритме слиянием заложена рекурсия, но в нем заложена и возможность на каком-то из этапов использовать другую сортировку. Например, когда размер массива будет меньше некоторого значения. Если же процесс деления продолжить, то мы получим, что в самом конце рекурсии сливаться будут массивы длиной равной 1. И далее процесс пойдет по восходящей линии.
Вариант, когда сортировка слиянием сочетается с другой сортировкой будет представлен в следующей статье, в данной же статье рассмотрим слияние в чистом виде.
Полный текст программы представлен ниже. Сортировка осуществляется функцией m_sort(). Она вызывается рекурсивно до тех пор, пока длина половинок ни станет равна единице. Но самое интересное здесь функция merge() - функция объединяет два отсортированных списка (массива). В сущности основа всего алгоритма именно здесь. Нужно объединить два массива, в общем случае разной длины. В функции три цикла, которые идут один за другим. Первый цикл основной, в нем происходит слияние элементов, путем сравнения их попарно. Слияние осуществляется в массив mab. Понятно, что количество таких пар равно длине наименьшего массива. Остаток в одном из массивов добавляется к mab в одном из циклов ниже. Ясно из двух следующих циклов будет работать только один, так как либо i == la, либо j == lb.
Пока всё...
Предыдущая статья по сортировке...
Следующая статья по сортировке...
Отличного программирования, друзья. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.
