Сортування злиттям

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

Miriam Antona

Software engineer

Сортування злиттям

Дотримується підходу divide and conquer
- Divide
  - ділить задачу на менші підзадачі
- Conquer
  - підзадачі розв'язуються рекурсивно
- Combine
  - розв'язки підзадач поєднуються, щоб отримати кінцевий результат

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

Схематичне зображення списку з невпорядкованими числами. Список поділено на дві частини. Є два нові списки: перший містить ліву половину початкового списку, другий — праву.

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — на прикладі

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

Сортування злиттям — реалізація

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]

Сортування злиттям — складність

Найгірший випадок: $O(n\log{}n)$
- суттєве покращення порівняно з bubble sort, selection sort та insertion sort
- придатний для сортування великих списків
Середній випадок: $\Theta(n\log{}n)$
Найкращий випадок: $\Omega(n\log{}n)$
- інші алгоритми (напр., bubble sort, insertion sort) мають кращу складність у найкращому випадку
Просторова складність: $O(n)$
- гірша за алгоритми з $O(1)$ пам'яті
Інші варіанти зменшують цю просторову складність

Давайте потренуємось!

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