C言語教室 解答編 第26回 - と、再帰呼出し
今回はいろいろなソートのうちバブルソートについて取り上げました。
C言語教室 第26回 - いろいろなソート
バブルソートは、あまり効率が良いわけではありませんが、余分なメモリを使うこともないのですし、ロジックがシンプルで一度覚えてしまうと「たしかこうやるんだよね」と思い出すことも出来、あまり大きくないデータの時にはよく使います。
さて、まだ課題をやっていないという方は、是非、挑戦をしてください。また結果をお知らせいただけたら幸いです。
さて、まだ課題を解いていないという方が、うっかり解答を見ないための閑話ですが、ここいらへんで再帰呼び出しについて触れておきます。
再帰呼び出しというのは、関数または手続きの中で自分自身を呼び出すことです。当然ですが、どこかでちゃんと終了して抜け出す条件を満たさないと無限ループになってしまいます。言語によっては再帰呼び出しが禁止されていたり、呼び出せる回数が制限されていることもあります。BASICみたいにグローバル変数しか使えない場合は、呼び出した方と、呼び出されたほうで、同じ変数を使うので、ちょっと工夫が必要だったりします。C言語では呼び出す回数自体は制限されていませんし、コンパイラもチェックしないのですが、実際には使えるスタックのサイズによる制限があります。
再帰
ほどんどの再帰呼び出しは、ループの形に変形することができますし、その逆もしかりです。前回の教室で使ったバブルソートのコードを再帰呼び出しの形に直してみましょう。
#include <stdio.h>
void bubble_sort(int *array, unsigned int n) {
if (n == 1)
return;
for (int i = 0; i < n - 1; i++) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
bubble_sort(array, n - 1);
}
void main() {
int data[] = {5, 3, 1, 2, 4};
unsigned int size = sizeof(data) / sizeof(data[0]);
bubble_sort(data, size);
for (int i = 0; i < size; i++)
printf("%d ", data[i]);
printf("\n");
}このコードのほうが部分的にソートされている部分が徐々に大きくなって全体がソートされるということがわかりやすいかもしれません。どうもピンとこないという方は、以下のサイトで復習してください。
バブルソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
この再帰呼び出しが、他のソートアルゴリズムでは必須となってきます。何か数学的な感じがしますが、要は形を変えたループに過ぎません。終了条件を気にするのも同じといえば同じです。最近の処理系ではスタックサイズにはかなり余裕があるように見えますが、スレッドで走っている時は思いの外、制限がキツイことがあります。またデバッグする都合を考えると、どの程度の深さ（再帰レベル）にいるのかわかるようにしておいたほうが便利です。
そろそろ課題に進みましょう。
課題
文字列の配列をバブルソートで並べ替える関数を書いてください。文字列の大小比較は strcmp を使ってください。なお、文字列全体を入れ替えながらソートすると大変なので文字列へのポインタの配列を用意して、これをソートするようにしてください。
わかってしまえば、整数の時とほとんど変わりません。設問で気にしたのが、char array[] = {“a”, “bb”, “ccc”}; のようにデータを持ってしまうと、値の交換で文字列全体を動かさないとならないので、これを避けて欲しいということでした(文字列の長さも違うのでいろいろ大変)。これは char *array[] にするだけで解決なのですけどね。
#include <stdio.h>
#include <string.h>
void bubbleSort(char **arr, unsigned int n) {
int i, j;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (strcmp(arr[j], arr[j+1]) > 0) {
char *temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void main() {
char *arr[] = {"cat", "dog", "bird", "fish"};
unsigned int n = sizeof(arr)/sizeof(arr[0]);
int i;
printf("Before sorting: ");
for (i = 0; i < n; i++)
printf("%s ", arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("After sorting: ");
for (i = 0; i < n; i++)
printf("%s ", arr[i]);
printf("\n");
}結果は以下の出力です。
Before sorting: cat dog bird fish
After sorting: bird cat dog fish 実は初期化した変数を書き換えてしまっているのが少しばかり気持ちが悪いです。(文字列ではなく)ポインタはスタックに展開されるのか調べていないのですが、static でないから毎回初期化されるとは思います(大丈夫かな？)。宣言で0に初期化したint変数の値を書き換えても何とも思わないのですが、ちょっと違和感はあります。興味を持った方はぜひ深掘りしてください。
さて、今回も答案をいただくことができました。いつもありがとうございます。他の方の答案もお待ちしていますよ。
まずは AyumiKatayama さんからの答案です。
C言語教室 第26回 - いろいろなソート（回答提出）
ソートアルゴリズム自体は教室で使ったものを流用して書いていただいたのですが、素敵な文を並べ替えていただきました。
バブルソートの手順がご記憶のものと合わなかったようで、以下の答案もいただきました。
C言語教室 第26回 - いろいろなソート（回答提出）（続）
人のことは言えませんが、バブルソートを暗記されているなんて素晴らしいです。私は調べ直しました。恐らくですがソート範囲の縮め方が違うだけで、ロジックとしては同じではないかと思います。安定ソートって、同じ値がある時の話ですし、工夫することで回避できると思うので、あまり気にしなくて大丈夫だと思います。
Akio van der Meer さんの答案です。
（答案提出）C言語教室 第26回 - いろいろなソート
あれれ？隣同士ではなくて、先頭と入れ替えているのでバブルソートではなくなってしまっていますね。こちらは選択ソートです。もっとも選択ソートであってもソート自身はちゃんと出来ますけどね。結果が同じだと交換回数を比較しないと気が付かないかもしれません。このデータの場合はたまたまどちらのアルゴリズムでも交換回数がおなじになってしまっていますけど。
（追記）
同じデータをもう１行追加して14個でやったところ、選択ソートの交換回数が33回、バブルソートが45回となりました。やはり平均的には選択ソートの方が交換回数が少ないことが多いみたいです。AyumiKatayama さん、Akio van der Meer さん、ご指摘感謝。
まあ、それはさておき、整列するデータを char*[] にすることに気がつけば、後はいけると思います。ChatGPTも、なかなかうまいことを言ってくれるものですが、人の話を半分しか聞いていないところもあるんですね。
C言語はポインタを恐れなくなるまでが勝負です。とはいえ配列がポインタに化けたり、ポインタが複数あって、それぞれの指し示す型が違ったり、これにconstが付けば訳がわからなくなるのは当然なので、中間状態の値を出力してみたり、適切なtypedefを使うなりしてみると、単に式に括弧がたくさんある程度の感じになりますよ。
最後に関数ポインタはスルーと書かれていましたが、以下の答案もいただきました。
（答案提出）C言語教室 第26回 - いろいろなソート - 関数ポインタ版
関数ポインタって、使うのに型宣言がややこしいのと、どう使うのかが言われないと思いつかないかもしれないのですが、習うより慣れろです。signalを始めいくつかのライブラリ関数で使うことを強要されるので、まずはそこからですかね。関数ポインタで関数を呼ぶと、呼び出し元がどこにあるのかを見失うことがあるので、関数名(または変数名)を工夫するとかして grep できるようにすることをオススメします。
ここで、AyumiKatayama さんからのコメントがあったようで、答案の再提出をいただきました。
（答案再提出）C言語教室 第26回 - いろいろなソート - バブルソートアルゴリズム
念のため Bard君に最初に提出されたコードを食べさせて確認してみました。
※コード自身は省略
で使われているソートアルゴリズムの種類は、選択ソートです。選択ソートでは、配列の中から最小の要素を見つけ、その要素を配列の先頭に移動させていきます。この操作を配列の最後まで繰り返すと、配列は昇順にソートされます。
選択ソートはとても簡単なソートアルゴリズムですが、最悪のケースでは、配列の要素がすべて逆順に並んでいる場合、O(n^2)の計算量がかかります。
選択ソートよりも高速なソートアルゴリズムも存在しますが、選択ソートはとても簡単なアルゴリズムなので、ソートアルゴリズムの入門として学ぶのに適しています。
ちなみに、選択ソートとバブルソートの違いも聞いてみました。
選択ソート と バブルソート は、どちらもソートアルゴリズムの一種です。選択ソートでは、未ソートされた要素の中で最小の要素を探し、ソート済みの要素の最後に追加していくことでソートを行います。バブルソートでは、隣り合った要素を比較し、昇順に並んでいない場合は要素を交換することでソートを行います。
選択ソート と バブルソートの主な違いは、ソートする際の動作です。選択ソートでは、未ソートされた要素の中で最小の要素を探し、ソート済みの要素の最後に追加していくため、ソート済みの要素が多いほど効率的にソートを行うことができます。バブルソートでは、隣り合った要素を比較し、昇順に並んでいない場合は要素を交換するため、ソート済みの要素が多いほど効率が悪くなります。
選択ソート と バブルソートの比較表は以下の通りです。
選択ソート と バブルソート はどちらも、ソートアルゴリズムの基本的な方法です。どちらのアルゴリズムを使用するかは、ソートするデータの量やソート済みの要素の量によって異なります。
ちなみにコードは python ですが、以下に面白い記事がありました。
[Python] バブルソート/選択ソート/挿入ソートの速度比較
いやいや本当にお疲れさまでした。ハマった時は是非ChatGPTにも応援してもらって、今後ともよろしくお願いします。
次回は他のソートアルゴリズムも取り上げ配列ではなくリストをソートしてみます。
ヘッダ画像は、いらすとや さんより
https://www.irasutoya.com/2020/04/blog-post_243.html
#C言語 #答え合わせ #プログラミング講座 #ソート #バブルソート #関数ポインタ #再帰呼び出し #スタック #ループ #ポインタ配列