マージソート

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software engineer

マージソート

分割統治法に従う
- 分割
  - 問題をより小さな部分問題に分ける
- 統治
  - 部分問題を再帰的に解く
- 結合
  - 部分問題の解を結合して最終解を得る

マージソート - 実行例

無作為な数のリストの概略図。

マージソート - 実行例

無作為な数のリストの概略図。リストが二分割されている。

マージソート - 実行例

無作為な数のリストの概略図。リストが二分割されている。新しい2つのリストの一方は元の左半分、もう一方は右半分を持つ。

マージソート - 実行例

無作為な数のリストの概略図。新しいリストが二分割されている。

マージソート - 実行例

無作為な数のリストの概略図。前回分割したリストをさらに分割した新しいリストがある。

マージソート - 実行例

無作為な数のリストの概略図。新しいリストが二分割されている。

マージソート - 実行例

無作為な数のリストの概略図。前回分割したリストをさらに分割した新しいリストがある。

マージソート - 実行例

無作為な数のリストの概略図。新しいリストが二分割されている。

マージソート - 実行例

無作為な数のリストの概略図。新しいリストが二分割されている。

マージソート - 実行例

無作為な数のリストの概略図。最後に分割したリストの要素が整列されている。

マージソート - 実行例

無作為な数のリストの概略図。最後に分割したリストの要素がマージされ、順序付けられている。

マージソート - 実行例

無作為な数のリストの概略図。最後に分割したリストの要素がマージされ、順序付けられている。

マージソート - 実行例

無作為な数のリストの概略図。最後に分割したリストの要素がマージされ、順序付けられている。すべての要素が整列済み。

マージソート - 実装

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)$
- バブルソート、選択ソート、挿入ソートより大幅に高速
- 大規模リストの整列に適する
平均計算量: $\Theta(n\log{}n)$
最良計算量: $\Omega(n\log{}n)$
- 他の手法（例: バブル、挿入）は最良時により良い場合あり
空間計算量: $O(n)$
- $O(1)$ の手法よりも空間を要する
変種により空間計算量を削減可能

Passons à la pratique !

Pythonで学ぶデータ構造とアルゴリズム