Сортировка слиянием

Структуры данных и алгоритмы на Python

Miriam Antona

Software engineer

Сортировка слиянием

  • Использует стратегию «разделяй и властвуй»
    • Разделение
      • задача делится на более мелкие подзадачи
    • Решение
      • подзадачи решаются рекурсивно
    • Объединение
      • решения подзадач объединяются в итоговый результат
Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Список разделён на две части.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Список разделён на две части. Сформированы два новых списка: первый содержит левую половину исходного списка, второй — правую.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Новые списки разделены на две части.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Показаны новые списки, полученные делением последних разбитых списков.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Новые списки разделены на две части.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Показаны новые списки, полученные делением последних разбитых списков.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Новые списки разделены на две части.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Новые списки разделены на две части.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Элементы последних разбитых списков отсортированы.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Элементы последних разбитых списков объединены и упорядочены.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Элементы последних разбитых списков объединены и упорядочены.

Структуры данных и алгоритмы на Python

Сортировка слиянием — в действии

Схематическое изображение списка с неупорядоченными числами. Элементы последних разбитых списков объединены и упорядочены. Все элементы отсортированы.

Структуры данных и алгоритмы на Python

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

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]
Структуры данных и алгоритмы на Python

Сортировка слиянием — сложность

  • Худший случай: $O(n\log{}n)$
    • существенное улучшение по сравнению с пузырьковой, сортировкой выбором и сортировкой вставками
    • подходит для сортировки больших списков
  • Средний случай: $\Theta(n\log{}n)$
  • Лучший случай: $\Omega(n\log{}n)$
    • другие алгоритмы (например, пузырьковая сортировка, сортировка вставками) имеют лучшую сложность в лучшем случае
  • Пространственная сложность: $O(n)$
    • худший показатель по памяти по сравнению с алгоритмами с $O(1)$
  • Другие варианты алгоритма позволяют снизить эту пространственную сложность
Структуры данных и алгоритмы на Python

Давайте потренируемся!

Структуры данных и алгоритмы на Python

Preparing Video For Download...