Pythonのマージソート
入力を再帰的に分割し、整列済みの部分列をマージします。
Pythonのマージソートとは？
入力を再帰的に分割し、整列済みの部分列をマージします。
分割統治法でデータを整列します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
Pythonのマージソートのビジュアライザー
O(n log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
main.py
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))期待される出力
[3, 9, 10, 27, 38, 43, 82]仕組み
時間O(n log n)を保証し、O(n)の追加メモリを使います。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。