今回はいろいろなソートのうちバブルソートについて取り上げました。

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言語サンプルプログラム付き）

この再帰呼び出しが、他のソートアルゴリズムでは必須となってきます。何か数学的な感じがしますが、要は形を変えたループに過ぎません。終了条件を気にするのも同じといえば同じです。最近の処理系ではスタックサイズにはかなり余裕があるように見えますが、スレッドで走っている時は思いの外、制限がキツイことがあります。またデバッグする都合を考えると、どの程度の深さ（再帰レベル）にいるのかわかるようにしておいたほうが便利です。

そろそろ課題に進みましょう。

わかってしまえば、整数の時とほとんど変わりません。設問で気にしたのが、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回 - いろいろなソート

あれれ？隣同士ではなくて、先頭と入れ替えているのでバブルソートではなくなってしまっていますね。こちらは選択ソートです。もっとも選択ソートであってもソート自身はちゃんと出来ますけどね。結果が同じだと交換回数を比較しないと気が付かないかもしれません。このデータの場合はたまたまどちらのアルゴリズムでも交換回数がおなじになってしまっていますけど。

まあ、それはさておき、整列するデータを char*[] にすることに気がつけば、後はいけると思います。ChatGPTも、なかなかうまいことを言ってくれるものですが、人の話を半分しか聞いていないところもあるんですね。

C言語はポインタを恐れなくなるまでが勝負です。とはいえ配列がポインタに化けたり、ポインタが複数あって、それぞれの指し示す型が違ったり、これにconstが付けば訳がわからなくなるのは当然なので、中間状態の値を出力してみたり、適切なtypedefを使うなりしてみると、単に式に括弧がたくさんある程度の感じになりますよ。

最後に関数ポインタはスルーと書かれていましたが、以下の答案もいただきました。

（答案提出）C言語教室 第26回 - いろいろなソート - 関数ポインタ版

関数ポインタって、使うのに型宣言がややこしいのと、どう使うのかが言われないと思いつかないかもしれないのですが、習うより慣れろです。signalを始めいくつかのライブラリ関数で使うことを強要されるので、まずはそこからですかね。関数ポインタで関数を呼ぶと、呼び出し元がどこにあるのかを見失うことがあるので、関数名(または変数名)を工夫するとかして grep できるようにすることをオススメします。

ここで、AyumiKatayama さんからのコメントがあったようで、答案の再提出をいただきました。

（答案再提出）C言語教室 第26回 - いろいろなソート - バブルソートアルゴリズム

念のため Bard君に最初に提出されたコードを食べさせて確認してみました。

ちなみに、選択ソートとバブルソートの違いも聞いてみました。

ちなみにコードは python ですが、以下に面白い記事がありました。

[Python] バブルソート/選択ソート/挿入ソートの速度比較

いやいや本当にお疲れさまでした。ハマった時は是非ChatGPTにも応援してもらって、今後ともよろしくお願いします。

次回は他のソートアルゴリズムも取り上げ配列ではなくリストをソートしてみます。

ヘッダ画像は、いらすとや さんより
https://www.irasutoya.com/2020/04/blog-post_243.html

#C言語 #答え合わせ #プログラミング講座 #ソート #バブルソート #関数ポインタ #再帰呼び出し #スタック #ループ #ポインタ配列