【C言語入門の次】 第12回 クイックソート

https://youtu.be/cmGKUYZpOd0

$\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}{四国めたん:}$ 現状、最速のソート手法のひとつと云われていますわね

$\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}{四国めたん:}$ ここで、適当な値を基準のデータとして選択しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 何でもいいのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ 何でもOKですが、この値の選択方法によって、 クイックソート の速度が変わりますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ プログラマーの腕の見せ所なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、とりあえず今回は概ね真ん中に位置する2を選びますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にソートする範囲の先頭、今回の場合はインデックス0から1、2...と順番に値を基準のデータと比較していきますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ もし、基準のデータよりも大きいか、等しい値が見つかれば、そのインデックスをマークしますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 更にソートする範囲の最後、今回の場合はインデックス5から4、3...と逆順に値を基準のデータと比較していきますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ もし、基準のデータよりも小さいか等しい値が見つかれば、そのインデックスをマークしますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、マークした値を入れ替えますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ これにより基準のデータ2よりも小さい値を配列の先頭に、大きい値を配列の後方に集めることができますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ わかったのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 入れ替え後は基準のデータとの比較、入れ替えを継続しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 次の入れ替えは、インデックス1の値6とインデックス2の値2となるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最終的に基準のデータ2よりも小さい値と大きい値の振り分けが完了しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ でも、まだソートは完全に終わっていないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、基準のデータ2よりも小さいデータは1つだけなので、ソートは完了ですわね

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 一方で、基準のデータ2よりも大きいデータはソートが完了していません

$\footnotesize \textcolor{lime}{ずんだもん:}$ そのとおりなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ですので、その範囲で再度クイックソートをおこなうのですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほど、それの繰り返しで、最終的に全体のソートが完了するのか

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

クイックソートの実装

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

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は配列のデータで クイックソート をおこなってみますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、 クイックソート の説明で明らかなように、再帰関数による実装が判り易いと思いますわ

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

#include <stdio.h>
#include <stdbool.h>

void swap(int data[], int idx1, int idx2) {
  int temp = data[idx1];
  data[idx1] = data[idx2];
  data[idx2] = temp;
  return;
}

void quick_sort(int data[], int top_idx, int last_idx) {
  int base = data[(top_idx + last_idx) / 2];
  if (top_idx < last_idx) {
    int s_idx = top_idx;
    int l_idx = last_idx;
    bool cont = true;
    while (cont) {
      while (data[s_idx] < base) {
        s_idx++;
      }
      while (data[l_idx] > base) {
        l_idx--;
      }
      if (s_idx < l_idx) {
        swap(data, s_idx++, l_idx--);
      } else {
        cont = false;
      }
    }
    quick_sort(data, top_idx, s_idx - 1);
    quick_sort(data, l_idx + 1, last_idx);
  }
  return;
}

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

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、swap関数はインデックス"idx1"と"idx2"で指定した配列のデータを入れ替えますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そして クイックソート はquick_sort関数を再帰呼び出しするようになっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 内部でquick_sort関数を呼び出しているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ quick_sort関数では、まず、基準のデータ"base"を"top_idx"と"last_idx"の範囲の概ね真ん中の位置のデータとしていますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、"top_idx"と"last_idx"の位置関係が同じ位置を指すなど、正常では無い場合には、何もせずに戻りますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ ループは二重になっていて、最初のループはデータの振り分けが完了するまで繰り返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データの振り分けが完了すると、条件"cont"をfalseにするのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 2番目のwhileループ内では、まず、"top_idx"から順番に基準のデータ"base"と配列の値を比較していきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 値が"base"よりも小さい場合にはスキップするのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 結果として"s_idx"が指す配列のデータは"base"よりも等しいか大きい値となりますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ 同様に"last_idx"から逆方向に基準のデータ"base"と配列の値を比較していきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 値が"base"よりも大きい場合にはスキップするのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 結果として"l_idx"が指す配列のデータは"base"よりも等しいか小さい値となりますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ ここで"l_idx"と"s_idx"が同じインデックスを指している場合には、振り分けを終了しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ つまり、"cont"をfalseとして最初のループを終了するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ また、"l_idx"が"s_idx"よりも大きい場合には、それぞれの指している配列の値をswap関数で入れ替えますわ

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

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで、swap関数の引数でs_idx++、l_idx--としているのは、どうしてなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 次のループで同じ位置から"base"との比較をおこなわないようにするためですわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ whileループを抜けた後は、振り分けられた範囲で、再度、quick_sort関数を呼び出しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 再帰呼び出しをするわけだな

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

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ、しっかりとソートができているのだ

標準Cライブラリ

$\footnotesize \textcolor{pink}{四国めたん:}$ ところで、ソートの中では、 クイックソート は非常にポピュラーな存在ですわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そのため、標準Cライブラリでは、qsortという名前で クイックソート の関数が提供されていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 標準で用意されているのは便利なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 実際に クイックソート をおこなう場合には、このような関数を使うのも良いかもしれませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 積極的に使っていくのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、qsortの宣言はこのようになっていますわ

void qsort(
   void *base,
   size_t number,
   size_t width,
   int (*compare)(const void *, const void *)
);

$\footnotesize \textcolor{pink}{四国めたん:}$ "base"は配列へのポインタ、"number"は配列の要素数、"width"は配列のサイズですわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ "compare"は比較用の関数へのポインタですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 関数へのポインタ？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、関数の引数に関数を割り当てることができるのですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしか、関数の引数に関数を割り当てることに関して「【C++言語入門】第25回 クラス中のラムダ式と引数」で解説していたのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ よく覚えていましたわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ まかせるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみにcompare関数では、第1引数と第2引数の比較結果を返すようにしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ どのような値をかえすのだ？

• 0: 第1引数と第2引数が等しい場合
• 負数: 第1引数が第2引数より小さい場合
• 正数: 第1引数が第2引数より大きい場合

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、第1引数と第2引数が等しい場合には0を返しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、第1引数が第2引数より小さい場合には負数を返しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ さらに、第1引数が第2引数より大きい場合には正数を返しますわ

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

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず使ってみましょう

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
  return *(int*)a - *(int*)b;
}

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

$\footnotesize \textcolor{lime}{ずんだもん:}$ compare関数の引数は両方ともにvoidへのポインタなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、実際に渡される値はint型へのポインタとなるので、内部でint型のポインタに キャスト して使用しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ キャスト ？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、変数の型を無理矢理、指定の型に変更する方法ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ そういえば「【C言語超入門】 第21回 大きなサイズの配列と動的メモリ配置」で解説していたのだ

$\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}{四国めたん:}$ 以上で クイックソート を終わりますわ