【C言語入門の次】 第09回 挿入ソート

https://youtu.be/kZ_C2vo36Hw

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

$\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{pink}{四国めたん:}$ データは比較できればOKなので、整数や浮動小数点数だけではなく、文字列などでも問題ありませんわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は整数を例に取りますわね

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

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

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

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、インデックス0は既にソート済みとしますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ インデックス1以下は未ソートのデータとみなしますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、未ソート部分の最初のデータ、つまりインデックス1のデータ6を取り出しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、インデックス0と1をソート済み領域として、取り出したデータを挿入しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 挿入する位置はどこでもいいのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ いいえ、挿入する位置は、ソートの順番が守られる位置としますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ つまりソート済みの領域のデータを順番に見ていく必要があるのか？

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

$\footnotesize \textcolor{lime}{ずんだもん:}$ とりあえず、今回は取り出したデータをそのまま戻すだけになるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 同様に、次の未ソート部分の最初のデータ、つまりインデックス2のデータ2を取り出しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そしてインデックス0～2をソート済み領域として、取り出したデータをソート順が守られるように挿入しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回、取り出したデータ2は、インデックス0の4より小さい値なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、ですので、インデックス0と1のデータをインデックス1と2に移動し、インデックス0に2を挿入しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データを挿入する場所によっては、大量のデータの移動が発生するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それが、このソートの欠点ですわね

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、これを繰り返して、最後のデータの挿入が終了すればソート完了ですわ

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

挿入ソートの実装

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは 挿入ソート を実装してみましょう

#include <stdio.h>

void print_data(int data[], int size) {
  for (size_t i = 0; i < size; i++) {
    printf("%d ", data[i]);
  }
  printf("\n");
  return;
}

void insertion_sort(int data[], int size) {
  for (int i = 1; i < size; i++) {
    int temp = data[i];
    int j = i - 1;
    for (; (j >= 0) && (data[j] > temp); j--) {
      data[j + 1] = data[j];
    }
    data[j + 1] = temp;
    print_data(data, size);
  }
  return;
}

int main(int argc, char* argv[]) {
  int data[] = {4, 6, 2, 5, 1, 3};
  int size = sizeof(data) / sizeof(int);
  print_data(data, size);
  insertion_sort(data, size);
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、print_dataは、ソートの途中で配列のデータの並びを確認するための関数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ これでソート途中の配列の並びを確認できるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数では配列にデータを準備しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 初期値の整数の並びは適当なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そしてinsertion_sort関数で配列中のデータをソートしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ insertion_sort関数は2重のループになっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、外側のループは、ソートされていないデータの最初のインデックスを設定しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、ソートされていない最初のデータを"temp"として退避していますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に内側のループですが、まず、ソートされた領域の最後のインデックスをjとして設定していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なぜjをforループの外で定義しているのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ jをforループの外で定義しているのは、内側のforループ後にjを使うためですわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ ループ内では、jでインデックスされる配列のデータと"temp"を比較しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ "temp"が小さい場合には、配列のデータを1つずらしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ "temp"が大きいか等しい場合には、その配列の場所に"temp"を代入しているのだ

$\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{lime}{ずんだもん:}$ たしかに...