マージソート(連結リスト) (Pythonによるアルゴリズムとデータ構造)
本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
前回は、配列によるマージソートについて学びました。
今回は、連結リストによるマージソートについて学んでいきます。
はじめに
前回では配列を使ったマージソートの方法について学びました。
配列によるマージソートでは、以下の欠点があります。
- 作業用の配列として、入力する配列と同じサイズの配列を用意しなければならないため、その分記憶領域を必要とする。
- 作業用の配列へのコピーに要する手間が必要となる。
連結リストによるものでは上記の欠点が改善され、その分速く整列をさせることが可能となります。
Pythonでマージソートを実装してみる
それでは、Pythonで連結リストによるマージソートを実装してみます。
# merge_sort_linked_list.py import time import pickle class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None def add(self, value): new = Node(value) if not self.head: self.head = new return tmp = self.head while tmp.next: tmp = tmp.next tmp.next = new def display(self): tmp = self.head while tmp: print(tmp.value) tmp = tmp.next def merge_list(self, a, b): head = Node(None) p = head while a and b: if a.value <= b.value: p.next = a p = a a = a.next else: p.next = b p = b b = b.next if not a: p.next = b else: p.next = a return head.next def merge_sort_sub(self, node): if not node or not node.next: return node a = node b = node.next if b: b = b.next while b: a = a.next b = b.next if b: b = b.next p = a.next a.next = None return self.merge_list(self.merge_sort_sub(node), self.merge_sort_sub(p)) def merge_sort(self): self.head = self.merge_sort_sub(self.head) with open('sample_data.pkl', 'rb') as f: lst = pickle.load(f) l = LinkedList() for i in lst: l.add(i) start = time.time() l.merge_sort() print("elapsed {} sec".format(time.time() - start))
動作確認
それでは上記で作成したスクリプトを実行してみます。
事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。
自環境で実行した結果を以下にまとめます。
アルゴリズム名 | 所要時間(秒) |
---|---|
Python 組込みメソッド(sort()) | 0.015 |
Bubble Sort | 72.979 |
Selection Sort | 17.747 |
Insertion Sort | 41.236 |
Shell Sort | 0.253 |
Quick Sort | 0.084 |
Merge Sort(List) | 0.168 |
Merge Sort(Linked List) | 0.092 |
結果としては配列によるものよりも速くなりました。
これまでは配列による整列アルゴリズムについて学んできました。
しかし、連結リストでは配列のようにランダムアクセスはできない(シーケンシャルアクセスしかできない)ので、この場合はマージソートのほうが適していると言えます。