Python マージソートアルゴリズムのチュートリアル
Python でマージ ソートを実装する方法を学びます。分割統治の並べ替え戦略のインタラクティブなステップバイステップの例。
概要
マージ ソートは、分割統治戦略を利用した非常に効率的な並べ替えアルゴリズムです。ソートされていないリストを小さなサブリストに分割し、それらのサブリストをソートしてから、それらを再び結合します。
このアルゴリズムは、単一要素の部分配列に達するまで、配列を再帰的に半分に分割します。次に、各側の要素を比較し、並べ替えられた順序で配置することによって、並べ替えられた部分配列をマージします。これにより、最適な時間計算量が保証されます。
最初の配列がソートされているか、反転されているか、完全にランダムであるかに関係なく、マージ ソートは O(n log n) 時間で実行されます。ただし、マージフェーズ中にサブリストを保持するには O(n) の追加スペースが必要です。
コードと実行の出力
Python でのマージ ソート アルゴリズムの標準的な再帰実装。
merge_sort.py
エディターで試してみる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):
result = []
i = j = 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
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)端子出力
Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]段階的な実装
- ノード構造によりコピーせずに簡単にマージできるリンク リストの並べ替え
- システム RAM に完全に収まらないファイルの外部ソート ルーチン
- 一致するキーが元の順序を保持する必要がある安定した並べ替えアプリケーション
よくある質問
マージ ソートは安定した並べ替えアルゴリズムですか?
はい、マージソートは安定しています。同一の要素を比較する場合、左側 (元の最初) のサブ配列の要素が最初に配置され、元の相対位置が維持されます。
Python が純粋なマージ ソートではなく Timsort を使用するのはなぜですか?
Python の組み込み `sorted()` は、マージ ソートと挿入ソートを組み合わせたハイブリッド アルゴリズムである Timsort を使用します。すでにソートされたサブセグメントを識別することで現実世界のデータ パターンを最適化し、純粋なマージ ソートよりも高速にレンダリングします。