Сортировка слиянием с реализацией на Python | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «ELK»
-16%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив "SQL для анализа данных"
-16%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Сортировка слиянием с реализацией на Python

Алгоритм сортировки слиянием относят к алгоритмам, работающим по принципу «разделяй и властвуй». Он разбивает список на 2 части, каждую разбивает ещё на 2 и так далее, пока не останутся единичные элементы. В результате соседние элементы становятся сортированными парами. Потом эти пары объединяют и сортируют с другими парами. Процесс продолжается, пока не отсортируются все элементы.

Особенности работы

Список рекурсивно разделяется пополам, пока не получатся списки размером в 1 элемент. Массив, состоящий из одного элемента, считают упорядоченным. Соседние элементы сравнивают и соединяют вместе до тех пор, пока не сформируется полный отсортированный список.

Сортировка выполняется путём сравнения наименьших элементов каждого подмассива. При этом первые элементы каждого подмассива сравниваются первыми. Самый маленький элемент перемещается в результирующий массив, а счётчики результирующего массива и подмассива, где взяли элемент, увеличиваются на один.

Реализация на «Пайтон»

Алгоритм реализуется следующим образом:

def merge(left_list, right_list):  
    sorted_list = []
    left_list_index = right_list_index = 0

    # Т. к. длина списков применяется часто, создадим для удобства переменные
    left_list_length, right_list_length = len(left_list), len(right_list)

    for _ in range(left_list_length + right_list_length):
        if left_list_index < left_list_length and right_list_index < right_list_length:
            # Сравниваем первые элементы в начале каждого списка
            # Если 1-й элемент левого подсписка меньше, добавляем его
            # в сортированный массив
            if left_list[left_list_index] <= right_list[right_list_index]:
                sorted_list.append(left_list[left_list_index])
                left_list_index += 1
            # Если 1-й элемент правого подсписка меньше, добавляем его
            # в сортированный массив
            else:
                sorted_list.append(right_list[right_list_index])
                right_list_index += 1

        # Когда достигнут конец левого списка, добавляем элементы правого списка
        # в конец результирующего списка
        elif left_list_index == left_list_length:
            sorted_list.append(right_list[right_list_index])
            right_list_index += 1
        # Когда достигнут конец правого списка, добавляем элементы левого списка
        # в сортированный массив
        elif right_list_index == right_list_length:
            sorted_list.append(left_list[left_list_index])
            left_list_index += 1

    return sorted_list

def merge_sort(nums):  
    # Возвращаем список, когда он состоит из одного элемента
    if len(nums) <= 1:
        return nums

    # Чтобы найти середину списка, применяем деление без остатка
    # Индексы должны быть integer
    mid = len(nums) // 2

    # Сортируем и объединяем подсписки
    left_list = merge_sort(nums[:mid])
    right_list = merge_sort(nums[mid:])

    # Объединяем сортированные списки в результирующий
    return merge(left_list, right_list)

# Проверяем, что всё работает
random_list_of_nums = [120, 45, 68, 250, 176]  
random_list_of_nums = merge_sort(random_list_of_nums)  
print(random_list_of_nums)

Здесь следует отметить, что функция merge_sort() возвращает новый список, а не сортирует существующий. Именно поэтому сортировка слиянием требует больше памяти, чем, к примеру, алгоритмы сортировки выборкой и вставками, алгоритмы пирамидальной и пузырьковой сортировки. Память необходима для создания нового списка такого же размера, что и входной список.

Время сортировки

Как правило, время сортировки слиянием составляет O(n log n).

Источник

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!