📛

マージソートまとめ

2024/10/09に公開

マージソート（Merge Sort）は以下のような特徴を持つソートアルゴリズムです：
基本原理:
分割統治法を用いたアルゴリズムです。
配列を再帰的に二分割し、それぞれをソートした後にマージ（統合）します。
アルゴリズムの流れ:
配列を要素数が1以下になるまで分割します。
分割された小さな配列をソートしながらマージしていきます。
マージの過程で、2つのソート済み配列を1つのソート済み配列に統合します。
性能:
時間計算量: O(n log n) - 最良、平均、最悪のケースすべてで同じ
空間計算量: O(n) - 追加のメモリ空間が必要
特徴:
安定ソート: 同じ値の要素の相対的な順序が保たれます。
外部ソート: 大規模なデータセットを扱う際に有効です。
利点:
予測可能な実行時間（常にO(n log n)）
安定ソートであること
並列処理に適している
欠点:
追加のメモリ空間が必要
小さなデータセットでは他のアルゴリズムより遅い場合がある
応用:
外部ソート
並列ソートアルゴリズム
マージソートは、その安定性と予測可能な実行時間から、大規模データの処理や並列処理が必要な場面で特に有用です。ただし、追加のメモリ空間が必要なため、メモリ制約のある環境では注意が必要です。

 具体的なコード例マージソートの具体的なPythonコード例を以下に示します：
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

# 使用例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("ソート前:", arr)
print("ソート後:", sorted_arr)
このコードの主な特徴は以下の通りです：
merge_sort 関数:
配列を再帰的に分割します。
長さが1以下の場合、そのまま返します（基底ケース）。
配列を半分に分割し、それぞれを再帰的にソートします。
ソートされた2つの部分配列をマージします。
merge 関数:
2つのソート済み配列を1つのソート済み配列にマージします。
両方の配列の先頭要素を比較し、小さい方を結果の配列に追加します。
どちらかの配列が空になるまでこれを繰り返します。
残りの要素を結果の配列に追加します。
このアルゴリズムは安定ソートであり、時間計算量は常に O(n log n) です。ただし、追加のメモリ空間 O(n) を必要とします。

具体的なコード例

Discussion