お疲れ様です。サンチョです！
今回は「バブルソート」について触れていきます。
未経験者が躓きやすいポイントなので、少しずつ読み進めていただけたら幸いです。
アルゴリズムとは
英語で書くと「algorithm」で、直訳すると「演算法」とか「算法」です。
「効率よくプログラミングするための手法」と認識しておけば良いです。
今回は「データの並べ替え」を行うための「ソート」について触れてみます。
バブルソート
配列から隣り合った値を取り出し、大きさを比べて値の入れ替えを行うか判断するというものです。
例えば、ソート前の情報が [ 4 ][ 1 ][ 3 ][ 5 ][ 2 ] だったとします。
まず１つ目と２つ目の値を比較して、１つ目が大きければ値を入れ替えます。
続いて、2つ目と3つ目の値を比較して、2つ目が大きければ値を入れ替えます。
…という具合に入れ替えていけば、一番最後のデータが一番大きな値となります。
イメージは以下のとおりです。
ソート前：[４][１][３][５][２]
判定１回目：[４][１][３][４][２]・・・４と１の値を入れ替える
判定２回目：[１][４][３][４][２]・・・４と３の値を入れ替える
判定３回目：[１][３][４][５][２]・・・この場合は入れ替えが発生しない
判定４回目：[１][３][４][５][２]・・・５と２の値を入れ替える
ソート結果：[１][３][４][２][５]・・・最後の値が最大値になる
上記では最大値を洗い出すことができました。
これを繰り返すことで昇順に並べ替えることができます。
実際にやってみよう
５つの要素をもつ配列の中身が「昇順（小さい順）」になるよう改造しましょう。
#include<stdio.h>
int main() {
int data[5] = {4, 1, 3, 5, 2};
}配列と比較が必要になるので、ifとループが必要になりそうですが、いきなり作り始めると混乱しやすいので、やることを整理しながら組み立てていきましょう。
値の入れ替え方法を考える
data[0] = data[1] のように代入してしまうと、data[0]の元の値が失われてしまいます。
この場合は、以下のイメージのように一時的にデータを退避させる変数が必要です。
とりあえずdata[0]とdata[1]の値を入れ替える処理を作成してみたので、コピペして実行してみてください。
#include<stdio.h>
int main() {
int data[5] = { 4, 1, 3, 5, 2 };
int temp; // データ退避用変数
printf("変更前\n");
printf("data[0]の値：%d", data[0]);
printf("data[1]の値：%d", data[1]);
temp = data[0]; // データ退避用変数にdata[0]を代入
data[0] = data[1]; // data[0]にdata[1]を代入
data[1] = temp; // data[1]にデータ退避用変数を代入
printf("\n変更後\n");
printf("data[0]の値：%d", data[0]);
printf("data[1]の値：%d", data[1]);
}イメージを元に配列内の要素同士を比較する方法を考える
今度はデータを入れ替える対象をどうやって指定して行けば良いか考えていきます。
いつもは最初にコピペ用のソースコードを提示しますが、今回は動かすだけで理解できる代物ではないので、思考の流れに沿って説明します。
必要になりそうな処理をイメージする
配列からデータを取り出すので、ループ処理を使えば良いということは想像できると思います。
では、先ほどのイメージを元に、改めてどういう処理が必要になりそうか考えていきましょう。
ソート前：[４][１][３][５][２]
判定１回目：[４][１][３][４][２]・・・４と１の値を入れ替える
判定２回目：[１][４][３][４][２]・・・４と３の値を入れ替える
判定３回目：[１][３][４][５][２]・・・この場合は入れ替えが発生しない
判定４回目：[１][３][４][５][２]・・・５と２の値を入れ替える
ソート結果：[１][３][４][２][５]・・・最後の値が最大値になる
配列は５つの要素を持っている
ということは、5回ループする処理が必要になりそうだということが分かりますね。
#include<stdio.h>
int main() {
int data[5] = { 4, 1, 3, 5, 2 };
int cnt;
for( cnt=0; cnt < 5; cnt++ ){}
｝「現在の要素番号」と「次の要素番号」で比較している
配列の要素を指定する際は、ループに用いているカウンタ変数の値を使いますよね。
仮にカウンタ変数を cnt とするなら、 if文は data[cnt] > data[cnt + 1] となります。
ついでに値の入れ替え処理と、結果表示用のループ処理も書いてしまいましょう。
#include<stdio.h>
int main() {
int data[5] = { 4, 1, 3, 5, 2 }; int cnt; int temp=0; for( cnt=0; cnt < 5; cnt++ ){
if( data[cnt] > data[cnt + 1] ){
/* 値の入れ替え */
temp = data[cnt];
data[cnt] = data[cnt + 1];
data[cnt + 1] = temp;
}
}
/* 結果表示用ループ */
for (cnt = 0; cnt < 5; cnt++) {
printf("data[%d]：%d\n", cnt, data[cnt]);
}
}
何か既にソレっぽくなってきましたが、このままだと「cnt」が「４」になったときにエラーが発生します。
なぜなら data[cnt + 1] としている部分で、存在しない data[5] を参照してしまうからです。
というワケでループが4回しか回らないよう修正してみました。
#include<stdio.h>
int main() {
int data[5] = { 4, 1, 3, 5, 2 };
int cnt;
int temp=0;
for( cnt=0; cnt < 4; cnt++ ){
if( data[cnt] > data[cnt + 1] ){
/* 値の入れ替え */
temp = data[cnt];
data[cnt] = data[cnt + 1];
data[cnt + 1] = temp;
}
}
/* 結果表示用ループ */
for (cnt = 0; cnt < 5; cnt++) {
printf("data[%d]：%d\n", cnt, data[cnt]);
}
}試しに実行すると、配列の中身は [１][３][４][２][５] となって終わりました。
とりあえず冒頭のイメージ部分はこれで実現できることが分かりましたね。
あとは、要素の数だけ同じ処理が繰り返し実行されるよう修正しましょう。
単純に二重ループにしてしまえば良いのです。
※二重ループにする際は、カウンタ変数の書き間違いに気を付けましょう！
#include<stdio.h> int main() { int data[5] = { 4, 1, 3, 5, 2 };int outCnt, inCnt; // カウンタ変数は外側用と内側用が一目で分かる名称に変更！ int temp=0; for( outCnt=0; outCnt < 5; outCnt++ ){ for( inCnt=0; inCnt < 4; inCnt++ ){ if( data[inCnt] > data[inCnt+ 1] ){ /* 値の入れ替え */ temp = data[inCnt]; data[inCnt] = data[inCnt+ 1]; data[inCnt+ 1] = temp; } } } /* 結果表示用ループ */ for (outCnt = 0; outCnt < 5; outCnt++) { printf("data[%d]：%d\n", outCnt, data[outCnt]); } }
これで配列の中身が [１][２][３][４][５] となりました！
しかし、このプログラムにはまだまだ改善の余地があります。
必要な比較回数は４回→３回→２回→１回と減らすことができる
上記のプログラムでは、比較の必要がなくなった部分も比較の対象としています。
これだと効率の悪いプログラムなので改善しましょう！
今回は内側のループ回数を「最大数ひく外側のカウンタ数」とするだけOKです。
#include<stdio.h>
int main() {
int data[5] = { 4, 1, 3, 5, 2 };
int outCnt,inCnt;
int temp=0;
for( outCnt=0; outCnt < 5; outCnt++ ){
/* ループ回数を「最大数ひく外側のカウンタ数」に変更 */
for( inCnt=0; inCnt < 4 - outCnt; inCnt++ ){
if( data[inCnt] > data[inCnt+ 1] ){
/* 値の入れ替え */
temp = data[inCnt];
data[inCnt] = data[inCnt+ 1];
data[inCnt+ 1] = temp;
}
}
}
/* 結果表示用ループ */
for (outCnt = 0; outCnt < 5; outCnt++) {
printf("data[%d]：%d\n", outCnt, data[outCnt]);
}
}
まとめ
今回はバブルソートというアルゴリズムに触れてみました。
簡単にまとめると以下のとおりです。
・アルゴリズムとは「効率よくプログラミングするための手法」である。
・バブルソートとは「配列から隣り合った値を取り出し、大きさを比べて値の入れ替えを行うか判断するもの」
アルゴリズムは形で覚えてしまうと応用が利かなくなるので、思考の流れに沿って説明してみました。
あくまで私が理解した際の流れを紹介しているだけなので、もっと効率の良い考え方はたくさんあると思います。
改善の糸口としたいので「ここが分かりにくかった」という感想や、「こうすれば良い」などのヒントがあれば教えてください！（切実）
では、本日はここまでにしたいと思います。
お疲れ様でした！
コメント