Sortowanie przez scalanie

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Sortowanie przez scalanie

Stosuje strategię dziel i zwyciężaj
- Dziel
  - problem dzielony jest na mniejsze podproblemy
- Zwyciężaj
  - podproblemy rozwiązywane są rekurencyjnie
- Łącz
  - rozwiązania podproblemów są łączone w końcowe rozwiązanie

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Lista została podzielona na dwie części.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Lista została podzielona na dwie części. Widoczne są dwie nowe listy: pierwsza zawiera lewą połowę oryginalnej listy, druga – prawą połowę.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Nowe listy zostały podzielone na dwie części.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Widoczne są nowe listy z podziałami ostatnio podzielonych list.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Nowe listy zostały podzielone na dwie części.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Widoczne są nowe listy z podziałami ostatnio podzielonych list.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Nowe listy zostały podzielone na dwie części.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Nowe listy zostały podzielone na dwie części.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Elementy z ostatnio podzielonych list zostały posortowane.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Elementy z ostatnio podzielonych list zostały scalone i uporządkowane.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Elementy z ostatnio podzielonych list zostały scalone i uporządkowane.

Sortowanie przez scalanie – w działaniu

Schematyczna reprezentacja listy z nieuporządkowanymi liczbami. Elementy z ostatnio podzielonych list zostały scalone i uporządkowane. Wszystkie elementy są posortowane.

Sortowanie przez scalanie – implementacja

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]

Sortowanie przez scalanie – złożoność

Przypadek pesymistyczny: $O(n\log{}n)$
- znaczna poprawa względem sortowania bąbelkowego, przez wybór i przez wstawianie
- odpowiednie do sortowania dużych list
Przypadek średni: $\Theta(n\log{}n)$
Przypadek optymistyczny: $\Omega(n\log{}n)$
- inne algorytmy (np. sortowanie bąbelkowe, przez wstawianie) mają lepszą złożoność w przypadku optymistycznym
Złożoność pamięciowa: $O(n)$
- gorsza złożoność pamięciowa niż algorytmy z $O(1)$
Inne warianty zmniejszają tę złożoność pamięciową

Czas na praktykę!

Struktury danych i algorytmy w Pythonie