Merge sort

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Merge sort

Využívá strategii rozděl a panuj
- Rozděl
  - problém se rozdělí na menší dílčí problémy
- Panuj
  - dílčí problémy jsou řešeny rekurzivně
- Slučuj
  - řešení dílčích problémů se sloučí do výsledného řešení

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Seznam byl rozdělen na dvě části.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Seznam byl rozdělen na dvě části. Jsou zobrazeny dva nové seznamy – první obsahuje levou polovinu původního seznamu, druhý pravou polovinu.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Nové seznamy byly rozděleny na dvě části.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Jsou zobrazeny nové seznamy s dalšími rozděleními.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Nové seznamy byly rozděleny na dvě části.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Jsou zobrazeny nové seznamy s dalšími rozděleními.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Nové seznamy byly rozděleny na dvě části.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Nové seznamy byly rozděleny na dvě části.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Prvky z posledních rozdělených seznamů byly seřazeny.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Prvky z posledních rozdělených seznamů byly sloučeny a seřazeny.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Prvky z posledních rozdělených seznamů byly sloučeny a seřazeny.

Merge sort – v praxi

Schématické znázornění seznamu s neuspořádanými čísly. Prvky z posledních rozdělených seznamů byly sloučeny a seřazeny. Všechny prvky jsou seřazeny.

Merge sort – implementace

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]

Merge sort – složitost

Nejhorší případ: $O(n\log{}n)$
- výrazné zlepšení oproti bubble sort, selection sort a insertion sort
- vhodný pro řazení velkých seznamů
Průměrný případ: $\Theta(n\log{}n)$
Nejlepší případ: $\Omega(n\log{}n)$
- jiné algoritmy (např. bubble sort, insertion sort) mají lepší složitost nejlepšího případu
Prostorová složitost: $O(n)$
- horší prostorová složitost než u algoritmů s $O(1)$
Jiné varianty tuto prostorovou složitost snižují

Lass uns üben!

Datové struktury a algoritmy v Pythonu