前回は、リンクリストの話を始めた。
リンクリストとは何か、その長所と短所について見てきました。
また、リンクリストの探索、挿入、削除、検索、要素のカウントなど、最もよく使われる方法についても学びました。
最後に、リンクリストを逆引きする方法について学びました。
今回は、前回の続きで、バブルソートとマージソートを使ってリンクリストをソートする方法と、ソートされた2つのリンクリストをマージする方法について説明します。
その前に、前回作成した Node クラスと LinkedList クラスを作成しておく必要があります。
バブルソートによるリンクリストの並べ替え
バブルソートでリンクリストをソートするには、2つの方法があります。
- ノード間でデータを交換する
- ノード間のリンクを変更する
この節では、これら2つの方法がどのように機能するかを見ていきます。
まず、バブルソートアルゴリズムを使って、データを変更することでリンクリストをソートし、次に、バブルソートを使ってリンクを変更することでリンクリストをソートする方法を見ることにする。
データ交換によるリンクリストの並べ替え
データを交換してリンクリストをソートするには、3つの変数 p、q、end を宣言する必要があります。
変数 p は開始ノードで初期化され、end は None に設定されます。
ここで重要なことは、 n 個の要素を持つリストをバブルソートでソートするには、 n-1 回の繰り返しが必要であるということです。
バブルソートを実装するためには、2 つの while ループが必要です。
外側の while ループは、変数 end の値が self.start_node と等しくなるまで実行されます。
内側の while ループは、変数 p が end と等しくなるまで実行される。
外側の while ループの内部では、p の値は最初のノードである self.start_node に設定されます。
内側のwhileループの中では、qの値が p.link に設定されます。
これは、実際には q の隣のノードです。
そして、p と q の値が比較されます。
もし p が q よりも大きければ、両方の変数の値が交換され、p は次のノードである p.ref を指すようになります。
最後に、endに p の値が代入されます。
この処理は、リンクリストがソートされるまで続けられます。
では、このプロセスを例によって理解しましょう。
次のようなリストがあるとする。
8,7,1,6,9
このリストをソートするアルゴリズムを実装してみましょう。
各反復の間に何が起こるか見てみましょう。
バブルソートの目的は、各反復の間に最大の値を最後に押し出すことであり、したがって、すべての反復の終わりに、リストは自動的にソートされます。
ループが実行される前に、 end の値は None に設定されます。
最初の反復処理では、 p に 8、q に 7 がセットされます。
pはqよりも大きいので、値が入れ替わり、pはp.ref` になります。
この時点で、リンクリストは次のようになります。
7,8,1,6,9
この時点では、pはendと等しくないので、ループは継続し、今度はpが8に、qが1になります。
再び p が q よりも大きいので、再び値が入れ替わり、 p は再び p.ref になります。
リストはこのようになります。
7,1,8,6,9
ここでも、pはendと等しくないので、ループは続き、今度はpが8になり、qが6になります。
ここでも p は q よりも大きいので、再び値が交換され、 p は再び p.ref になります。
リストはこのようになります。
7,1,6,8,9
再び p が end と等しくなければ、ループは続き、今度は p が 8、q が 9 になります。
ここで、pはqより大きくないので、値は交換されず、pは p.ref となります。
この時点で、p の参照先は None となり、end も None を指すようになります。
したがって、内側の while ループは中断され、end には p が設定されます。
次の反復処理では、9がすでに終了しているので、ループは8まで実行されます。
この処理は、リストが完全にソートされるまで続けられます。
バブルソートを使ってデータを交換しながらリンクリストをソートするPythonのコードは以下の通りです。
def bub_sort_datachange(self):
end = None
while end != self.start_node:
p = self.start_node
while p.ref != end:
q = p.ref
if p.item > q.item:
p.item, q.item = q.item, p.item
p = p.ref
end = p
前回の記事で作成した LinkedList クラスに bub_sort_dataexchange() メソッドを追加してください。
リンクリストにこのメソッドを追加したら、 make_new_list() 関数を使って任意のノードセットを作成し、 bub_sort_dataexchange() を使ってリストをソートしてください。
traverse_list()` 関数を実行すると、ソートされたリストが表示されるはずです。
リンク修正によるリンクリストの並べ替え ##### リンク修正によるリンクリストの並べ替え
バブルソートは、データを変更する代わりにリンクを変更することで、リンクリストをソートすることもできます。
しかし、この場合、変数 r が追加され、常に p ノードより前のノードに対応するようになります。
リンクを修正することで2つのノードを交換する簡単な例を見てみましょう。
次のような項目からなるリンクリストがあるとする。
10,45,65,35,1
そして、65と35を入れ替えたいと思います。
このとき、pはノード65に対応し、qはノード35に対応する。
変数 r はノード 45 (ノード p の前) に対応することになります。
ここで、ノード p がノード q よりも大きい場合、ここでは p.ref が q.ref に、 q.ref が p に設定されます。
同様に、r.refにはqがセットされます。
これにより、ノード65とノード35が入れ替わります。
次のメソッドは、リンクリストのバブルソートを、リンクを修正することで実装しています。
def bub_sort_linkchange(self):
end = None
while end != self.start_node:
r = p = self.start_node
while p.ref != end:
q = p.ref
if p.item > q.item:
p.ref = q.ref
q.ref = p
if p != self.start_node:
r.ref = q
else:
self.start_node = q
p,q = q,p
r = p
p = p.ref
end = p
前回の記事で作成した LinkedList クラスに bub_sort_linkchange() メソッドを追加してください。
リンクリストにこのメソッドを追加したら、 make_new_list() 関数を使用して任意のノードセットを作成し、 bub_sort_linkchange() を使用してリストをソートしてください。
traverse_list()` 関数を実行すると、ソートされたリストが表示されるはずです。
ソートされたリンクリストのマージ
この節では、ソートされた2つのリンクリストを、結果のリンクリストもソートされるようにマージする方法について説明します。
これを実現するには、2つのアプローチがあります。
個別にソートされたリストを含む新しいリンクリストを作成する方法と、2つのリンクリストのリンクを単純に変更して2つのソートされたリンクリストを結合する方法です。
後者の場合、新しいリンクリストを作成する必要はありません。
まず、新しいリストを作成して 2 つのリンクリストを結合する方法を見てみましょう。
新しいリストを作成して並べ替えられたリンクリストをマージする
まず、新しいリストの助けを借りて2つのソートされたリンクリストをマージする方法を確認するために、アルゴリズムを実行してみましょう。
以下の2つのソートされたリンクリストがあるとします。
list1:
10,45,65,
list2:
5,15,35,68
これらはマージしたい2つのリストです。
アルゴリズムは簡単です。
必要なのは、 p, q, em という 3 つの変数と、空のリスト newlist だけです。
アルゴリズムの最初では、 p が list1 の最初の要素を指し、 q が list2 の最初の要素を指します。
変数 em は空になります。
アルゴリズムの開始時には、次のような値になります。
p = 10
q = 5
em = none
newlist = none
次に、list1 の最初の要素と list2 の最初の要素を比較します。
言い換えると、 p と q の値を比較して、小さい方の値が変数 em に格納され、新しいリストの最初のノードとなります。
emの値はnewlist` の末尾に追加されます。
最初の比較の後、次のような値が得られます。
p = 10
q = 15
em = 5
newlist = 5
qはpよりも小さいので、qの値をem` に格納し、 ‘q’ をひとつ右のインデックスに移動させます。
2回目のパスでは、次のような値になります。
p = 45
q = 15
em = 10
newlist = 5, 10
ここで、pの方が小さいので、pの値を newlist に追加し、em を p にセットして、p を1つ右に移動させます。
次の繰り返しでは、次のようになります。
p = 45
q = 35
em = 15
newlist = 5, 10, 15
同様に、次の繰り返しでは
p = 45
q = 68
em = 35
newlist = 5, 10, 15, 35
そして、次の反復では、再び p が q よりも小さくなるので、次のようになります。
p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45
最後に
p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65
リストの一方が None になったとき、2番目のリストのすべての要素が新しいリストの末尾に追加される。
したがって、最終的なリストは次のようになる。
p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68
二つのソートされたリストをマージするPythonスクリプトは以下の通りである。
def merge_helper(self, list2):
merged_list = LinkedList()
merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node)
return merged_list
def merge_by_newlist(self, p, q):
if p.item <= q.item:
startNode = Node(p.item)
p = p.ref
else:
startNode = Node(q.item)
q = q.ref
em = startNode
while p is not None and q is not None:
if p.item <= q.item:
em.ref = Node(p.item)
p = p.ref
else:
em.ref = Node(q.item)
q = q.ref
em = em.ref
while p is not None:
em.ref = Node(p.item)
p = p.ref
em = em.ref
while q is not None:
em.ref = Node(q.item)
q = q.ref
em = em.ref
return startNode
上のスクリプトでは、merge_helper() と merge_by_newlist() という2つのメソッドを用意しています。
最初のメソッド merge_helper() は、リンクリストをパラメータとして受け取り、リンクリスト自身とパラメータとして渡されたリンクリストである self クラスを merge_by_newlist() メソッドに引き渡します。
merge_by_newlist()メソッドは、2つのリンクリストをマージして新しいリンクリストを作成し、新しいリンクリストの開始ノードを返します。
これら二つのメソッドをLinkedListクラスに追加してください。
2 つの新しいリンクリストを作成し、前のセクションで作成したbub_sort_datachange()またはbub_sort_linkchange()メソッドを用いてソートしてから、merge_by_newlist()` を用いてソートされた 2 つのリンクリストをマージできるかどうか確認してみてください。
リンクの並べ替えによる並べ替え済みリンクリストのマージ
この方法では、2つのソート済みリンクリストの結合を保存するために、新しいリンクリストを使用することはない。
むしろ、2つのリンクリストのリンクは、2つのリンクリストがソートされた方法でマージされるように変更されます。
その方法を簡単な例で見てみましょう。
同じリスト list1 と list2 があるとします。
list1:
10,45,65,
list2:
5,15,35,68
リンクを並べ替えることで、ソートされた状態でマージしたいと思います。
そのためには、変数 p、q、em が必要である。
初期状態では、これらの変数は以下のような値を持っている。
p = 10
q = 5
em = none
newlist = none
次に、 list1 の最初の要素と list2 の最初の要素を比較します。
言い換えると、 p と q の値を比較して、小さい方の値を変数 em に格納し、それが新しいリストの最初のノードとなります。
最初の比較の後、次のような値が得られます。
p = 10
q = 15
start = 5
em = start
最初の反復の後、 q は p よりも小さいので、開始ノードは q の方を向き、 q は q.ref となります。
このとき、emはstartと等しくなります。
この em は常に、マージされたリストの中で新しく挿入されたノードを指します。
p = 45
q = 15
em = 10
pはqよりも小さかったので、変数emは元の値であるpの方を指し、pはp.ref` となります。
p = 45
q = 35
em = 15
qはpよりも小さかったので、emはqの方を指し、qはq.ref` になります。
p = 45
q = 68
em = 35
同様に、ここでは em は q の方を向いています。
p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45
そして、ここで em が指差す先は p になります。
p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65
リストの一方が None になると、2番目のリストの要素が最後に追加されるだけです。
p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68
新しいリストを作らずに二つのリストをマージする関数を含むスクリプトは以下の通りである。
def merge_helper2(self, list2):
merged_list = LinkedList()
merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node)
return merged_list
def merge_by_linkChange(self, p, q):
if p.item <= q.item:
startNode = Node(p.item)
p = p.ref
else:
startNode = Node(q.item)
q = q.ref
em = startNode
while p is not None and q is not None:
if p.item <= q.item:
em.ref = Node(p.item)
em = em.ref
p = p.ref
else:
em.ref = Node(q.item)
em = em.ref
q = q.ref
if p is None:
em.ref = q
else:
em.ref = p
return startNode
上のスクリプトでは、merge_helper2() と merge_by_linkChange() という二つのメソッドを用意しています。
最初のメソッド merge_helper2() は、リンクリストをパラメータとして受け取り、リンクリスト自身である self クラスとパラメータとして渡されたリンクリストを merge_by_linkChange() に渡して、リンクを修正して二つのリンクをマージして、マージしたリストの開始ノードを返します。
これら二つのメソッドを LinkedList クラスに追加してください。
2 つの新しいリンクリストを作成し、前のセクションで作成した bub_sort_datachange() や bub_sort_linkchange() メソッドを使ってソートしてから、 merge_by_newlist() を使ってソートした 2 つのリンクリストをマージできるかどうか確認してみましょう。
この処理を実際に見てみましょう。
以下のスクリプトを使って新しいリンクリストを作成します。
new_linked_list1 = LinkedList()
new_linked_list1.make_new_list()
スクリプトは入力するノードの数を尋ねてきます。
好きなだけノードを入力し、以下のように各ノードに値を追加する。
How many nodes do you want to create: 4
Enter the value for the node:12
Enter the value for the node:45
Enter the value for the node:32
Enter the value for the node:61
次に、上記の作業を繰り返して、別のリンクリストを作成する。
new_linked_list2 = LinkedList()
new_linked_list2.make_new_list()
次に、以下のスクリプトを使って、ダミーのノードをいくつか追加する。
How many nodes do you want to create: 4
Enter the value for the node:36
Enter the value for the node:41
Enter the value for the node:25
Enter the value for the node:9
次のステップは、両方のリストをソートすることである。
次のスクリプトを実行してください。
new_linked_list1. bub_sort_datachange()
new_linked_list2. bub_sort_datachange()
最後に、次のスクリプトで2つのリンクリストをマージします。
list3 = new_linked_list1.merge_helper2(new_linked_list2)
リストが実際にマージされたかどうかを確認するには、次のスクリプトを実行してください。
list3.traverse_list()
出力はこのようになる。
9
12
25
32
36
41
45
61
結論
この記事では、前回の記事の続きを書きました。
データを変更することでマージリストをソートし、さらにリンクを変更する方法を説明しました。
最後に、2つのソートされたリンクリストをマージするさまざまな方法について学びました。
次回は、2重リンクリストの作成方法とその操作について説明します。