マージソートを理解できるようにわかりやすくまとめる

マージソートの考え方や実際のプログラムまで、理解しやすく、忘れないようにまとめたいと思います。

マージソートの擬似言語で書かれたアルゴリズム

マージソートで擬似言語で書くと以下のようなコードになります。
ALDS1_5_Bを参照しています。

/**
  A:ソート対象の配列
  left:配列の左端のindex,
  mid:配列の中間index
  right:配列の右端index
*/
merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  // 2つの配列を作成する
  create array L[0...n1], R[0...n2]
  // 左側
  for i = 0 to n1-1
    L[i] = A[left + i]
  // 右側
  for i = 0 to n2-1
    R[i] = A[mid + i]

  // 番兵を入れる
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  // 2つの部分配列をマージする①
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)

マージソートのアルゴリズム

この擬似言語のアルゴリズムからマージソートは以下の手順で実行されます。

1.指定されたn個の要素を含む部分配列を
それぞれn / 2の要素を含む2つの部分配列に分割する(divide)

2.分割した2つの部分配列をマージソートでソートする(solve)

3.ソートした2つの部分配列をマージする

マージソートはソート済みの2つの部分配列を結合するときのアルゴリズムが鍵になっています。

擬似言語のアルゴリズムでは、①の箇所が該当します。
2つの配列LとRは昇順にソートされていることを前提とし、
LとRのすべての要素が昇順となるようにソート済みの数列を格納するAにコピーしています。

2つの部分配列は、昇順にソートされていることが前提と書きましたが、
マージソートでは、要素数1からスタートし、部分配列を昇順に結合していくので、
2つの部分配列はソートされていることになります。

部分配列LとRはソート済みであることから、擬似言語でのアルゴリズムのコードからわかるように、
計算量は、O(n1 + n2)となります。

マージソートの結合する箇所を図解する

マージソートの要となる結合部分のアルゴリズムを図示してみます。
マージのアルゴリズムは、以下のコードでした。

  // 番兵を入れる
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  // 2つの部分配列をマージする①
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

まず、以下の2つの部分配列L・Rと、結合する整列した配列Aがあるとします。
L:1,6
R:2,3,9
A:***

部分配列のL・Rは要素が2つ以上入っているので、
Aには、すでに整列途中の結果が入っていることになります。

擬似言語のアルゴにあるように、それぞれに番兵(最大の数値今回はSとする)を代入します。

L:1,6,S
R:2,3,9,S

1回目の比較

Lのindex0とRのindex0を比較して、小さい方をA[left]に代入します。

L:1,6,S
R:2,3,9,S

A:1

Lのindex0の値1が挿入されたので、Lのindex対象の変数iを1つ増やします。

2回目の比較

L:1,6,S
R:2,3,9,S

A:1,2

Rの2代入されます。
Rのindex対象の変数jを1つ増やします。

3回目の比較

L:1,6,S
R:2,3,9,S

A:1,2,3

Rの3が代入されます。

4回目の比較

L:1,6,S
R:2,3,9,S

A:1,2,3,6

Lの6が代入されます。
次からLは番兵を指すようになります。

最後の比較

L:1,6,S
R:2,3,9,S

A:1,2,3,6,9

最後の比較になります。
Lは番兵をさすので、Rの9がAに挿入されます。

forループの比較回数は、left to right - 1とleftとrightの合計の要素数になっているため、
ここで比較が終了します。

番兵と比較する要素数で判断することによって、O(n1 + n2)の処理数を実現しています。

mergeSort関数の解説

結合のアルゴリズムがわかったところで、mergeSort関数部分を図解していきます。
mergeSortの擬似言語での関数は以下です。

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)

引数Aには、対象となるソートしたい配列を、
leftには、部分配列の先頭を、rightには、末尾+1のindexを指定します。

left + 1 < right
により、要素が1以下の場合は処理しないようにしています。

mid = (left + right)/2; Merge-Sort(A, left, mid)
Merge-Sort(A, mid, right)

探索する範囲を狭めて、再帰処理を行なっています。
最終的には、Merge-Sortに渡す対象のindexが2つの部分配列の要素数がそれぞれ
1になるようにすることで、昇順に整列する箇所が機能するようにしています。

mergeSortの工程を図解する

では最後にmergeSortの工程を図解します。

数列859263714をマージソートにかけています。
黒矢印が分割する工程を、赤矢印がマージする工程を示しています。

mergeSortの計算量を考える

merge関数の処理の計算量は前述したように0(n1 + n2)になります。

上図にあるように、9個の数を1個になるまで、分割しようとすると、
9 → 5 → 3 → 2 → 1
の4回の分割が必要になり、階層は5になります。

このことから、階層は一般に
$log_{2}n$個になります。

階層階ごとに行われる全てのマージの総計算量はO(n)になるので、
マージソートの計算量はO(nlogn)になります。

参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
マージソートのwikipedia

再帰関数を理解できるように詳しくまとめる

再帰関数についてまとめたいと思います。

再帰関数とは

関数の中で、その関数自身を呼ぶような関数のことを再帰関数といいます。

再帰関数の例としてよくあげられるのは、階乗するようなケースです。
$3!$などの計算のことです。

$3!$のケースを考えると、
$3! = 3 × 2 × 1$
という計算になりますが、この乗算する処理を自身で実行してしまおう
というのが、再帰関数になります。

階乗処理を例とした再帰関数の実装

階乗処理をベースに再帰関数を書いてみたいと思います。

引数に階乗したい数値を入れ、
その階乗した値を返す関数を再帰関数で考えてみます。

factorial(int n ){
  if(n == 1) return 1;
  return n * factorial(n - 1)
}

再帰関数の処理を図式化する

関数だけだと、処理を想像することが難しいので、
図式化したいと思います。

階乗したい数値を4として、factorial関数に代入する様子をみてみます。

再帰関数1回目の処理

factorialに4を代入します。

return 4 × factorial(4 - 1)

ここで、factorial(4 - 1)として自身を呼び出しています。
return処理は行われず、factorial(4 - 1)関数が先に呼ばれます。

再帰関数2回目の処理

factorial(4 - 1)を呼びます。

return 3 × factorial(3 - 1)

factorial(3 - 1)を呼びします。
まだreturnはしていません。

再帰関数3回目の処理

factorial(3 - 1)を呼びます。

return 2 × factorial(2 - 1)

factorial(2 - 1)を呼び出します。
次から展開が変わります。。。

再帰関数4回目の処理

factorial(2 - 1)を呼び出します。

if(n == 1) return 1;

nが1なので、ようやくここで、1をreturnします。
factorial(2 - 1)を呼び出した、3回目の処理にもどります。

factorial(3 - 1)の処理

factorial(2 - 1)の処理結果として1が返ってきたので、 factorial(2 - 1)の処理を呼び出していた、
factorial(3 - 1)のreturnが以下のように返るようになります。

return 2 × 1

次に、factorial(3 - 1)を呼び出していた、
factorial(4 - 1)のreturn処理が行われることになります。

factorial(4 - 1)の処理

factorial(3 - 1)が2 × 1と返ってきたため、 factorial(4 - 1)のreturn部分の処理が行われます。

return 3 × factorial(3 - 1)

つまり

return 3 × 2 × 1

がfactorial(4 - 1)のreturn値になります。
factorial(4 - 1)を呼んだfactorial(4)のreturn値が返ることになります。

factorial(4)の処理

いよいよ、factorial(4)の処理が終わります。

return 4 × factorial(4 - 1)

つまり

return 4 × 3 × 2 × 1

が、最終的な値として、返ってくることになります。

双方向連結リストc++で動的に実装する

双方向連結リストをc++で実装してみたいと思います。
まず、双方向連結リストとは何かに関してまとめます。

双方向連結リストとは

あるデータを持ったノードがあり、そのノードの前方と後方に別のノードが連結しているリストのことです。
数値をデータとして持つノードの双方向連結リストを図で表すとこんな感じです。

□→ ←□2□→ ←□4□→ ←□

□は、繋いでいるデータのメモリアドレスです。

一番最初のデータと一番最後のデータは、空のデータを表すnilを入れます。
参照しても空ということです。

双方向連結リストをc++で実装する

では、c++で双方向リストを実装してみたいと思います。

まず、ノードとなるデータを構造体で定義します。

struct Node{
    int key;
    Node *next,*prev;
};

データとして、int型を定義し、
自身を二つ定義します。
これに、連結リストとなる次のノードと前のノードを代入して、連結リストが作られていきます。

双方向リストの位置を管理する番兵を導入する

定義したノードを生成して、新しく連結リストを作っていくのに、現在の連結リストの位置を管理する必要があります。 そのために、グローバル変数として、番兵を用意します。

// 番兵をグローバル変数として定義する
Node* nil;

// 番兵を生成する
void init(){
    nil = (Node*)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

新しくメモリを割り当てる関数mallocを使って、連結リストのノードを作成しています。 mallocで作成したメモリ領域は必ず、free関数で解放する必要があるので、ノードを削除する関数で、
free関数を必ず呼びましょう。

nil->next = nil
nil->prev = nil
によって、番兵の前と次の要素を自身に設定して、巡回するようにしています。

双方向連結リストに新しいノードを挿入する

位置を管理する番兵を定義したところで、新しいノードのを追加する関数を定義します。
insert関数は、連結リストの先頭にキーを持つノードを挿入する関数です。

void insert(int key){
    // 新しくnode用のメモリを作成
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    // 番兵の次に要素を追加
    node->next = nil->next;
    nil->next->prev = node;
    nil->next = node;
    node->prev = nil;
}

ここがわかりにくいと思うので、挿入していく様子を図解してみます。

ノードが挿入される要素を図解する

1.まず新しくkey3を持つノードを作成します。

□空の先頭□ □3□

2.続いて番兵の設定をして、連結リストが管理できるようにします。

番兵はinit関数により、自身を巡回させているので、下図のようになります。

       prev       next
番兵 ← □番兵□ → 番兵

続いて、挿入していく様子を図にします。

まず、新しく作成したnodeのnextに番兵を指定します。
nil->nextはnilを指していますね。

node->next = nil->next;

□3□ → □番兵□

続いて、nil->next->prev = node
ですが、最初に要素を挿入するときには、nil->next->prevはnilを指しています。
なので、nilのprevにnodeを挿入していることになります。

nil->next->prev = node

□3□ → □番兵□
　   ←

続いて、番兵のnextに作成したノードを設定します。 図では、番兵が2つになっていますが、実際はもちろん一つで、表現するためにそうしています。

nil->next = node

□番兵□ → □3□ → □番兵□
　　　　　　    ← 

最後に、ノードのprevに番兵を設定します。

node->prev = nil;

□番兵□ → □3□ → □番兵□
　　　   ←　　 ←

これで、一回目の挿入が終わりました。

2回目の双方向連結リストへの挿入

では、次にkey5を持つノードを新しく挿入するケースを確認したいと思います。

node->next = nil->next
現在nilのnextには、先ほど作成した3を持つノードが指定されているので、node->nextは
3のノードを指すことになります。

node->next = nil->next


□5□ → □3□ → □番兵□
　　　　 　←

nil->next->prev = node
nil->nextには、3が入っています。 ということは、nil->next->prevは3のprevを指しますね。
3のprevに5のノードを代入します。

nil->next->prev = node;
□5□ → □3□ → □番兵□
　　←　 　←

nil->next = node
nil->nextに5のノードを設定します。

nil->next = node
□番兵□ → □5□ → □3□ → □番兵□
　　　              ←　 　←

node->prev = nil 現在のノードのprevに番兵を指すようにして、巡回させるようにします。

node->prev = nil;
□番兵□ → □5□ → □3□ → □番兵□
　　　   ←       ←　 　←

こんな感じで先頭に挿入することができます。
要素の先頭と最後方には番兵が入ることになり、双方向連結リストの挿入を容易にしてくれます。

双方向連結リストをキーで探索する

リストをキーで検索してみます。

insert関数で図解したように、番兵のnextに先頭の要素が、
最後方のnextに番兵が入っているので、
キーを探すには、番兵のnextから探索し、番兵が見つかれば、
キーをもつ要素が見つからなかったという判断ができそうです。

双方向連結リストをキーで探索するプログラム

それでは、双方向連結リストを探索するプログラムを見ていきます。

Node* searchList(int key){
    // 番兵の先頭から探していく
    Node* cur = nil->next;
    // 番兵でなく、キーが同じでなければ、次の要素を探索する
    while(cur != nil && cur->key != key){
        cur = cur->next;
    }
    // 見つからければ、番兵が返ることになる。
    return cur;
}

双方向連結リストのノードを削除する

続いて、ノードを削除する方法を見ていきましょう。
引数として与えられたノードを削除するプログラムを書きます。

双方向連結リストのノードを削除するプログラム

void deleteNode(Node* n){
    // 番兵のケースは何もしない
    if(n == nil) return;
    n->prev->next = n->next;
    n->next->prev = n->prev;
    free(n);
}

プログラムの様子がイメージしにくい部分があると思うので、
先ほどinsertした図を使用し、プログラムの遷移を表現してみます。

□番兵□ → □5□ → □3□ → □番兵□
　　　   ←       ←　 　←

この連結リストから5のノードを削除するケースを考えてみます。

n->prev->next = n->next
自身のprevの要素のnextが指す位置を自身の次の要素に入れ替えます。
つまり、番兵のnextが3を指すようになります。

n->prev->next = n->next

□番兵□    □5□ → □3□ → □番兵□
　　　   ←       ←　 　←
　　　　　 □番兵□ →　

n->next->prev = n->prev
自身の次の要素のprevが指す位置を自身の前の要素に入れ替えます。 つまり、3ノードのprevが番兵を指すようになります。

n->prev->next = n->next

□番兵□ → □3□ → □番兵□ □5□ 
　　　   ←       ←　 　　

free(n); 最後にどこにも連結しなくなった、ノード5をfree関数によって、削除します。

これで、5を削除しても連結リストが保持されていることが確認できました。

双方向連結リストの先頭のノードを削除する

番兵のnextが先頭のノードを指しているので、deleteNode関数に
nil->nextを渡せばokです。

void deleteFirst(){
    deleteNode(nil->next);
}

双方向連結リストの最後方のノードを削除する

番兵のprevは後方のノードを指しているので、deleteNode関数に
nil->prevを渡せばokです。

void deleteLast(){
    deleteNode(nil->prev);
}

双方向連結リストの特定のキーをもつノードを削除する

先ほど特定キーをもつノードを探し、返す関数を書いたので、その関数を使います。

void deleteKey(int key){
    deleteNode(searchList(key));
}

これで、双方向リストのプログラムが完成しました。

双方向連結リストの計算量を考える

双方向連結リストの計算量を考えてみます。

双方向連結リストの挿入する計算量

プログラムで示した通り、番兵のnextのpointerを繋ぎ変えるだけなので、
O(1)になります。

双方向連結リストから特定の要素を探索する計算量

双方向位連結リストは直列で結ばれているので、
先頭から末端のNまで、探索する必要があります。
なので、O(N)になります。

双方向連結リストから特定の要素を削除する計算量

先頭・最高峰の要素を削除するには、番兵があるので、O(1)の計算量で、
それ以外は、O(N)になります。