【C言語入門の次】 第07回 バブルソート

https://youtu.be/6CH4xGorB5Q

$\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{lime}{ずんだもん:}$ ところで 標準Cライブラリ にqsortという関数を見たことがあるのだが...

$\footnotesize \textcolor{pink}{四国めたん:}$ qsortは、高速で安定したソート用の関数ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 既にソート用の関数があるなら、改めて学ぶ必要は無いのではないか？

$\footnotesize \textcolor{pink}{四国めたん:}$ たしかに実用上はqsortを使えばOKですわね

$\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}{四国めたん:}$ 最初は、インデックス0と1のデータを比較しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 6と4が入っているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回はインデックス0から小さい順に整数が並ぶようにしますわね

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

$\footnotesize \textcolor{pink}{四国めたん:}$ その場合、まずインデックス0の整数がインデックス1の整数より大きければデータを入れ替えますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回の場合は、インデックス0が4、インデックス1が6となっているので、データの入れ替えはしないのだ

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

$\footnotesize \textcolor{lime}{ずんだもん:}$ 次はインデックス1と2のデータを比較するのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、インデックス1は6、インデックス2が2となっているので、データを入れ替えますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ これを繰り返し、配列の最後のデータの比較、入れ替えが終わるまで繰り返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回はインデックス5とインデックス4の値を比較するまでなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 結果として、配列の最後、今回の場合はインデックス5のデータが一番大きい値6となりますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ このような入れ替えを再度、インデックス0からおこないますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ ただし、配列の最後は既に最大値が入っていますので、比較、入れ替えの対象からは外しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 今回はインデックス5は除外するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ これを繰り返して、比較、入れ替えのインデックスが0と1のみとなればソートは完了ですわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに、 バブルソート の名前の由来は、ソートの際にデータが泡のように浮いてくるからだそうですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ あぁ、だからインデックス0を一番下にしていたのか...

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、ビジュアルもだいじですわ

バブルソートの実装

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

#include <stdio.h>

#define DATA_SIZE (6)

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

void bubble_sort(int data[]) {
  for (int i = DATA_SIZE - 1; i > 0; i--) {
    for (int j = 0; j < i; j++) {
      if (data[j] > data[j + 1]) {
        int temp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = temp;
      }
      print_data(data);
    }
  }
  return;
}

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

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

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

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

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

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

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

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、外側のループは内側のループの終わりのインデックスを設定していますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 内側のループでは、インデックス0からデータの比較をおこない、次の要素より大きい場合にはデータの入れ替えをおこないますわ

$\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{pink}{四国めたん:}$ ただ、標準Cライブラリのqsort関数を使える場合には、使う場面はないと思いますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ ただ、qsort関数が提供されていないシステムで、少量のデータを扱う場合などには使えるかもしれませんわね

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