【C言語で】#14 バケツソート【ビンゴを作ろう】

C言語でBINGOを作ろう #14 バケツソート

C言語でBINGOを作ろう!

C言語でBINGOを作ろう!

CUI上で動くビンゴゲームの完成目指してひっそりとプログラムの勉強を始めました。前回は現在時刻を利用して乱数が自動的に設定されるように改造してみました。

しかし、このままでは一度出た数字でも何度でも出てきてしまいます。そう、フェニックスは何度でも（ｒｙ

そこで次は、一度出てきた数字が再度出てこないように改造します。その下準備として、バケツソートを扱います。フェニックスはバケツで倒せるんですね

BINGOの記事一覧はこちら

開発環境

開発環境はこちらをご覧ください。

本記事は以上の開発環境を前提に説明を行います。

バケツソート

ソートとは

ソートとは、何かのルールに従って並べ替えを行うことです。

ソートの代表例としては

・バブルソート

・基本選択法

・基本挿入法

・シェルソート

・クイックソート

・マージソート

・ボゴソート

などがあります。それぞれのソートによって特性が違ってきます。気になる人は調べて実装してみましょう。

バケツソートとは

バケツソート(別名ビンソート)とは、　ランダムに並んだ被っていない数字を並べ替えるソートアルゴリズムの一種です。

手順は以下のような感じです。

１．番号がついた空のバケツを準備する(上がランダムに並んだ数字の列、下がバケツのイメージ)

２．ランダムに並んだ数字を前から順番に取り出し、同じ番号のバケツに水を入れる

３．すべての数字を取り出し終わったら、バケツを番号順に調べる。水が入っていればバケツの番号を数字の列に戻して次のバケツへ。水が入っていなければそのまま次のバケツへ。

4．数字の列を見ると番号順に並んでいる(上が並べ替え後の数字の列)

プログラムで再現する場合、バケツを配列に、水を値にすれば再現できます。順を追ってやってみましょう。

１．空の配列を準備する

まずは並べ替える元の数字の列と、空の配列を準備します。プログラムで書くと↓のようにすればＯＫです。

#include <stdio.h>

int main(void){
  //変数の準備
  int number[] = {7, 4, 2, 9, 0}; //数字の列を準備
  int bucket[10] = {0}; //バケツを作り、要素をすべて0で初期化
  return 0;
}

注意点として、用意する配列の要素数は、並べ替える数字の中の最大値よりも多くないといけません。上記の例では、最大値は9なのでバケツの要素数は10としています。

例えば、「0～99の数字がランダムに10個、被らずに並んでいる数字の列」を並べ替える場合、入っている可能性がある数字の中で一番大きい数字は99です、そのため、配列の要素数は常に100個必要です。(配列は0から数え始めます。100個の配列を作ると0番～99番の配列ができます。)

2．数字の列から数字を取り出す

次に、数字の列から数字を取り出し、同じインデックスの配列に値を入れます。

#include <stdio.h>

int main(void){
  //変数の準備
  int number[] = {7, 4, 2, 9, 0};
  int bucket[10] = {0};
  int i; //ループカウンタ(for文の回数を数えるための変数)
  int length = sizeof(number) / sizeof(number[0]); //数字並んでいる配列numberの要素数を取得
  //数字を取り出す
  for(i = 0; i < length; i++){
    bucket[number[i]] = 1; //bucket[取り出した数字] とすることで、取り出した数字がインデックスになっているbucketを指定している
  }
  return 0;
}

配列number[]から取り出した値を、配列bucket[]のインデックスに指定しています。少しややこしい書き方なので注意してください。
難しい場合は、以下のように書いてもＯＫです。

//bucket[number[i]] = 1; //この1行をコメントアウトして、代わりに下の2行を記述
int tmp = number[i]; //一度、number[i]の数字を変数tmpに取り出して、
bucket[tmp] = 1; //tmpがインデックスになっているbucket[]の値を1にする

3．空の配列を準備する

まずは並べ替える元の数字の列と、空の配列を準備します。プログラムで書くと↓のようにすればＯＫです。

#include <stdio.h>

int main(void){
  //変数の準備
  int number[] = {7, 4, 2, 9, 0};
  int bucket[10] = {0};
  int i; //ループカウンタ
  int j; //ループカウンタ(2つ必要になるので追加)
  int length = sizeof(number) / sizeof(number[0]);
  int bkt_length = sizeof(bucket) / sizeof(bucket[0]); //バケツの要素数を取得
  //数字を取り出す
  for(i = 0; i < length; i++){
    bucket[number[i]] = 1;
  }
  //バケツから数字を戻す
  i = 0;
  j = 0;
  for(j = 0; j < bkt_length; j++){ //bucketの要素数と同じだけfor文を実行
    if(bucket[j] > 0){ //もし、bucketの中身が入っていたら
      number[i++] = j; //バケツの番号をnumber[]の i 番目に戻し、その後 i を1つ進める
    }
  }
  return 0;
}

こちらも、number[i++] = j;という部分が難しいかもしれません。その場合は↓のように書き換えてもＯＫです。

//number[i++] = j; //この1行をコメントアウトして、代わりに下の2行を記述
number[i] = j; //number[i]にjを代入して、
i++; //その後、iを1つ増やす(インクリメント)

4．並べ替えが完了したことを確認するために配列を表示する

1～3の手順でバケツソートによる並べ替えは完了です。しかし、このままでは本当に並べ変わっているのかよくわからないので、最後に表示部分を作ります。

#include <stdio.h>

int main(void){
  //変数の準備
  int number[] = {7, 4, 2, 9, 0};
  int bucket[10] = {0};
  int i; //ループカウンタ
  int j; //ループカウンタ
  int length = sizeof(number) / sizeof(number[0]);
  int bkt_length = sizeof(bucket) / sizeof(bucket[0]);
  //数字を取り出す
  for(i = 0; i < length; i++){
    bucket[number[i]] = 1;
  }
  //バケツから数字を戻す
  i = 0;
  j = 0;
  for(j = 0; j < bkt_length; j++){
    if(bucket[j] > 0){
      number[i++] = j;
    }
  }
  //数字を表示する
  i = 0;
  for(i = 0; i < length; i++){
    printf("number[%d] = %d\n", i, number[i]);
  }
  return 0;
}

これで、バケツソートを無事習得しました。・・・あれ、ちょっと違う

バケツソートの特徴

バケツソートは特徴として以下の点が挙げられます。
・負の数がある場合、メモリ上のあらぬところに触れるため、危険
・バケツ用の配列の要素数は、もとの数字が取りうる中で一番大きな値より多く必要
－＞もし、もとの数字が3個しかなくても、その中に10000が入っていたらバケツは10001個必要(インデックスは0から始まるため)になり、無駄が多くなる

さらに、今回作ったバケツソートっぽいものには、実は数字がダブっていると正しくソートできないという弱点があります。
きちんと作ったバケツソートなら、数字がダブっていても整列可能です。ということで、これが今日の宿題。

おまけ

厳しい修業に耐え無事バケツソートを習得できたので、これでフェニックス数字が何度でも出てくる問題は解決・・・してないよ！！

これでどうやって抽選結果の保存をするんだYO！！

宿題コーナー

気が付けば秋。 宿題のコーナーです。

前回の宿題と解答例

並べ替え(ソート)のアルゴリズムについていくつか調べてくること。あれ、今日の宿題解答例なさそうだからサボっても(ry

ソートの例

・バブルソート

総当たりのように次々に比較して並べ替えていく。要素数に応じて比較を繰り返すため、条件次第だが、一般には早くない。

・クイックソート

ピボットと呼ばれる基準を取って、それより大きいか小さいかで数字を入れ替えていく、条件がそろっていればかなり高速なソート。条件が悪いとバブルソートと同じスピードになる。

・基本選択法

全要素を調べ、小さいもの(または、大きいもの)から順に取り出していく。バブルソートと同じように要素の数に応じて比較を繰り返すため、一般には早くない。

なお、各ソートについての詳細は各自調べること。

今日の宿題

今回作ったバケツソートっぽいものは同じ数字が2回以上出てくるとうまく並べ替えができません。そこで、どうやれば同じ数字が2回以上出てきても並べ替えできるか、考えてみましょう。

次回はバケツソートを応用して出てきた数字を保存します。

BINGOの記事一覧はこちら

実践力が身につくC言語講座 連載リンク

競技プログラミングをイメージしたライブラリ活用講座
競技プログラミング風-標準Cライブラリ入門 連載

アルゴリズムをマスターして技術力アップ！
実践アルゴリズム講座 連載

パズルゲームの解析をテーマにしたC++講座
ゲーム解析プログラミング 連載