Engineering Note

プログラミングなどの技術的なメモ

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

merge sort

本記事は、ソフトバンクパブリッシングから発行されている「定本 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データとして保存しておき、これをロードします。

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

 

データ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

 

 

結果としては配列によるものよりも速くなりました。

これまでは配列による整列アルゴリズムについて学んできました。

しかし、連結リストでは配列のようにランダムアクセスはできない(シーケンシャルアクセスしかできない)ので、この場合はマージソートのほうが適していると言えます。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)