Pythonでマージソートを実装してみました。
マージソートはソートの中で高速ですが、他のソートに比べて少し実装が難しいです。
しかし1つ1つステップを踏んで作ればそんなに難しくありません。
まずはマージソートの中身を順番に解説していきます。
- 整列されていないリストを2つのサブリストに分割する
- 分割したリスト(サブリスト)をマージソートを使って整列させる。(再帰関数)
- 2つのサブリストをマージして1つの整列済みリストにする
次に2つのサブリストをマージする手順をみていきます。
- AとBの先頭の数字を比較し、小さい方をCに追加し追加した値はリストから削除する
- 手順1をどちらか一方のリストが空になるまで繰り返す。
- 残った要素をCの末尾に追加する
以上のステップをそのまま実装すればマージソートは完成ですが、せっかくなので実際の例をみてみましょう。
そのほうがイメージがわきやすいと思います。
1. 整列前のリストです [5,4,6,1,2,7,3] 2. 半分に分割します。 [5, 4, 6, 1] [2, 7, 3] 3. 左側をさらに半分に分割 [5, 4] [6, 1] 4. それぞれ整列させる [5] [4] [6] [1] 5. 右側も半分に分割 [2, 7] [3] 6. それぞれ整列させる [2] [7] 7. 最後にマージして完成! [1, 2, 3, 4, 5, 6, 7]
以下が実装例です。
def MergeSort(num_list): n = len(num_list) if len(num_list) == 1: return num_list #1. 整列されていないリストを2つのサブリストに分割する mid = int(round(n/2)) left = num_list[:mid] right = num_list[mid:] print(left,right) #2. 分割したリスト(サブリスト)を整列する。サブリストもマージソートを使って整列させる。(再帰関数) l = MergeSort(left) r = MergeSort(right) #3. 2つのサブリストをマージして1つの整列済みリストにする return Merge(l,r) # 整列済みリストA、Bを使って、整列済みリストCを作成する def Merge(A,B): C = [] # print("A",A) # print("B",B) # 1. AとBの先頭の数字を比較し、小さい方をCに追加し追加した値はリストから削除する # 2. 手順1をどちらか一方のリストが空になるまで繰り返す。 while (len(A) > 0) and (len(B) > 0): if A[0] < B[0]: C.append(A[0]) del A[0] else: C.append(B[0]) del B[0] # 3. 残った要素をCの末尾に追加する if len(A) > 0: C.extend(A) else: C.extend(B) # print("C",C) return C
おわり。