マージソート

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

Miriam Antona

Software engineer

マージソート

分割統治法に基づく
- 分割
  - 問題をより小さなサブ問題に分ける
- 統治
  - 各サブ問題を再帰的に解く
- 結合
  - サブ問題の解を組み合わせて、最終的な解を導き出す

マージソート - 実行

順不同の番号が並んだリスト。

マージソート - 実行

順不同の番号が並んだリスト。リストが2つに分けられている。

マージソート - 実行

順不同の番号が並んだリスト。リストが2つに分かれている。新しいリストは2つあります。1つ目は元のリストの左半分、2つ目は元のリストの右半分。

マージソート - 実行

順不同の番号が並んだリスト。新しいリストが2つに分割されている。

マージソート - 実行

順不同の番号が並んだリスト。最後に分割されたリストの区分を持つ新しいリストがある。

マージソート - 実行

順不同の番号が並んだリスト。新しいリストが2つに分割されている。

マージソート - 実行

順不同の番号が並んだリスト。最後に分割されたリストの区分を含む新しいリストがある。

マージソート - 実行

順不同の番号が並んだリスト。新しいリストは2つに分割されている。

マージソート - 実行

順不同の番号が並んだリスト。新しいリストが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)$ のアルゴリズムと比べて、最も空間計算量が悪い
派生アルゴリズムで、空間計算量を削減できる

練習しましょう！

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