【C言語入門の次】 第10回 マージソート

https://youtu.be/5ky6sQkdRLg

$\textcolor{pink}{四国めたん: }$教師役ですわ

$\textcolor{lime}{ずんだもん: }$生徒役なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ こんにちは。四国めたんです

$\footnotesize \textcolor{lime}{ずんだもん:}$ ずんだもんなのだ。こんにちはなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回も ソート のアルゴリズムについてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は マージソート についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

マージソート

マージの基本概念

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで マージ とはなんなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ マージ とは、2つのデータを結合して、1つのデータにする手法ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 マージソート で使う場合には、ソートをおこないつつ結合しますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 具体的には？

$\footnotesize \textcolor{pink}{四国めたん:}$ 結合する際に、2つのデータの先頭を比較して、その大小によってどちらかのデータを取ってくる、と云うことを繰り返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 実際の例を見ていきましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、既にソートされた2つの配列を用意しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、元の2つの配列の先頭データの内、小さい方を新しい配列の先頭に移動しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回の例では、配列1のインデックス0のデータ、1を移動するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、配列1のインデックス1のデータと配列2のインデックス0のデータを比較しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 配列2のインデックス0のデータ、2のほうが小さいのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、ですので、2を新しい配列のインデックス1に移動しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 更に、配列1のインデックス1のデータと配列2のインデックス1のデータを比較しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回も配列2のインデックス1のデータ、3のほうが小さいので、新しい配列のインデックス2に移動するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ これを繰り返して、最終的には配列2のインデックス2のデータ、6を新しい配列のインデックス5に移動すれば マージ が完了しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 新しい配列は、配列1と2をソートされた状態で マージ されているのだ

ランダムなデータにマージソートを

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、ランダムなデータに対して マージソート をおこなう仕組みについてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ おねがいするのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 基本的には、データを一旦バラバラにして、 マージ を繰り返し適用しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よくわからないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 具体的に見ていきましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、ソート前の配列には、整数がバラバラに入っているとしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、配列をおおよそ半分に分割しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ つぎに半分に分けたデータを マージ することで、ソートをおこないますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{lime}{ずんだもん:}$ でも、 マージ するデータは、既にソートされていることが前提ではなかったのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ その通りですわ

$\footnotesize \textcolor{pink}{四国めたん:}$ ですので、 マージ する前に、分割したデータを別々にソートしておくのですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ つまり分割したデータを更に分割して マージ することでソートしておくのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ その通りですわね

$\footnotesize \textcolor{pink}{四国めたん:}$ 最終的には、データのサイズが1になれば、単に マージ するだけでソートできますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ まぁ、サイズが1なら既にソートされていると考えてもOKなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに、 マージ する相手がいない場合には、次の マージ のために取っておきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最終的に、全てのデータがソートされますわ

マージソートの実装

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで、データを一旦バラバラにして組み上げていく手法は、手数が多くて遅いイメージがあるのだが...

$\footnotesize \textcolor{pink}{四国めたん:}$ たしかにそうなのですが、 マージソート は高速なソート手法に分類されますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、意外ですわね

$\footnotesize \textcolor{pink}{四国めたん:}$ ところで、ランダムなデータを マージソート を使ってソートする場合、データを半分に分けてソートして マージ することを繰り返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 再帰関数と相性が良さそうなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ と云うことで、今回は再帰関数を使ってみましょう

マージ関数

$\footnotesize \textcolor{pink}{四国めたん:}$ まずは2つのデータを マージ する関数を実装しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

#include <stdio.h>
#include <string.h>

void merge(int data[], int idx, int size1, int size2, int work[]) {
  int idx1 = idx;
  int idx2 = idx + size1;
  int idx_work = 0;
  int total_byte = sizeof(int) * (size1 + size2);
  while ((size1 > 0) && (size2 > 0)) {
    if (data[idx1] > data[idx2]) {
      work[idx_work++] = data[idx2++];
      size2--;
    } else {
      work[idx_work++] = data[idx1++];
      size1--;
    }
  }
  if (size1 > 0) {
    int size = sizeof(int) * size1;
    memcpy(work + idx_work, data + idx1, size);
  }
  if (size2 > 0) {
    int size = sizeof(int) * size2;
    memcpy(work + idx_work, data + idx2, size);
  }
  memcpy(data + idx, work, total_byte);
  return;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ 基本的に小さい値から順番に並べるように マージ する関数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 引数の"data"はデータが入っている配列ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ "idx"はなんなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ "idx"は配列中の マージ 対象のデータの最初のインデックスですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ "size1"と"size2"はなんなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ マージ するデータのサイズをそれぞれ指定しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ あぁ、 マージ するデータは隣り合っているので、2つのデータのサイズが判れば、 マージ するデータの範囲がわかるのか...

$\footnotesize \textcolor{pink}{四国めたん:}$ ですので、 マージ するデータの先頭のインデックスを"idx1"と"idx2"として計算できますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで"work"配列はなんなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ "work"配列は、 マージ する際にデータを仮置きする領域ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ つまり"data"よりも大きいサイズの配列が必要というわけだな

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、関数中では次にデータを挿入する"work"配列のインデックスを用意していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに、最終的に得られる マージ されたデータのサイズ"total_byte"をバイト単位で取得していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、whileループですが、データを"work"に移す毎に、データの残量として"size1"もしくは"size2"を減らしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ "size1"か"size2"のどちらかが0になれば、whileループは終了なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、残ったデータをmemcpyで"work"に移しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 最後に"work"中のデータを"data"に戻しているのだ

マージソート関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に マージソート 本体の関数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

void merge_sort(int data[], int idx, int size, int work[]) {
  if (size > 1) {
    int half = size / 2;
    int left = size - half;
    merge_sort(data, idx, half, work);
    merge_sort(data, idx + half, left, work);
    merge(data, idx, half, left, work);
  }
  return;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ この関数はいたってシンプルで、引数として渡されたデータの配列"data"中のインデックス"idx"からサイズ"size"分のデータを マージソート しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ワーク領域として配列"work"も指定しているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、指定されたサイズが1以下の場合には、何もせずにリターンしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ まぁ、サイズが1や0ならソートする意味はないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、そして、サイズが2以上の場合には、データ領域をおおむね半分にしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ まぁ、奇数のサイズは完全に半分にはできないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それぞれの領域は、再度merge_sort関数で マージソート をおこない、ソートされた状態にしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後に半分にされたデータ領域をmerge関数で結合することで、ソートが完了しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は、アルゴリズムを簡潔に示すために再帰関数として実装していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 当然ですが、再帰関数としなくても実装は可能ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 再帰関数だとスタックオーバーフローが心配なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ たしかに心配ですが、 マージソート であれば、20段の再帰で100万件程度のデータのソートが可能ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ならば、あまり心配する必要はないのだ

メイン関数

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは、メイン関数でmerge_sortを使ってみましょう

#define DATA_SIZE (6)

int main(int argc, char* argv[]) {
  int data[DATA_SIZE] = {4, 6, 5, 2, 1, 3};
  int work[DATA_SIZE] = {0};
  merge_sort(data, 0, DATA_SIZE, work);
  for (int i = 0; i < DATA_SIZE; i++) {
    printf("%d ", data[i]);
  }
  printf("\n");
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、適当に数値を入れたサイズ6の配列"data"とワーク領域"work"を用意しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 引数に値を指定してmerge_sortを呼び出しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 最後に"data"内の整数を出力して、ソートされていることを確認しているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実行してみましょう

まとめ

$\footnotesize \textcolor{pink}{四国めたん:}$ お疲れさまでした

$\footnotesize \textcolor{lime}{ずんだもん:}$ おつかれさまなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 以上で マージソート を終了しますわ