マージソート（連結リスト）（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

前回は、配列によるマージソートについて学びました。

今回は、連結リストによるマージソートについて学んでいきます。

はじめに
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データとして保存しておき、これをロードします。

自環境で実行した結果を以下にまとめます。

**データ20,000個を整列した結果一覧**
アルゴリズム名	所要時間（秒）
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