クイックソートとマージソートの実装

ソートアルゴリズムは、データを特定の順序に並べ替えるための手法です。本教材では、クイックソートとマージソートの2つの代表的なソートアルゴリズムについて、Pythonでの実装を通じて理解を深めます。

クイックソート

クイックソートは、分割統治法に基づくソートアルゴリズムです。以下の手順で動作します。

1. 基準となる要素（ピボット）を選ぶ。
2. 配列をピボットを基準に小さい要素と大きい要素に分割する。
3. 分割された部分を再帰的にソートする。

クイックソートの実装

以下にクイックソートの実装を示します。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]  # ピボットを中央の要素に設定
        left = [x for x in arr if x < pivot]  # ピボットより小さい要素
        middle = [x for x in arr if x == pivot]  # ピボットと等しい要素
        right = [x for x in arr if x > pivot]  # ピボットより大きい要素
        return quicksort(left) + middle + quicksort(right)

# 使用例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quicksort(arr)
print("クイックソート結果:", sorted_arr)

コード解説

• quicksort関数は、リストarrを引数に取り、ソートされたリストを返します。
• 基本ケースとして、リストの長さが1以下の場合はそのまま返します。
• ピボットは中央の要素に設定し、リストを3つの部分に分けます。
• left: ピボットより小さい要素
• middle: ピボットと等しい要素
• right: ピボットより大きい要素
• 最後に、再帰的にそれぞれの部分をソートし、結合して結果を返します。

マージソート

マージソートも分割統治法を用いたソートアルゴリズムです。以下の手順で動作します。

1. 配列を半分に分割する。
2. 分割された部分を再帰的にソートする。
3. ソートされた2つの部分をマージ（結合）する。

マージソートの実装

以下にマージソートの実装を示します。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2  # 中央のインデックス
    left_half = merge_sort(arr[:mid])  # 左半分を再帰的にソート
    right_half = merge_sort(arr[mid:])  # 右半分を再帰的にソート

    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    left_index, right_index = 0, 0

    # マージ処理
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    # 残りの要素を追加
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])

    return merged

# 使用例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = merge_sort(arr)
print("マージソート結果:", sorted_arr)

コード解説

• merge_sort関数は、リストarrを引数に取り、ソートされたリストを返します。
• 基本ケースとして、リストの長さが1以下の場合はそのまま返します。
• 配列を中央で分割し、それぞれの部分を再帰的にソートします。
• merge関数は、2つのソートされたリストを引数に取り、それらをマージします。
• merge関数内では、2つのリストを比較しながら新しいリストmergedを作成し、残りの要素も追加します。

まとめ

クイックソートとマージソートは、どちらも効率的なソートアルゴリズムですが、特性や使用する場面が異なります。クイックソートは通常、平均ケースでO(n log n)の時間計算量を持ち、マージソートはO(n log n)ですが、安定なソートが必要な場合に適しています。これらのアルゴリズムを理解し、使い分けることで、より効率的なデータ処理が可能になります。