C言語でアルゴリズム作り〜バブルソートand scanf〜②

先日、妥協してやらなかった「上限１００個だけどそれ以下なら何個でも入力できるという仕組み」を完成させました！

このコードならちゃんと入力した文字が問題なくソートされて出力されます。

うまく動かなかったプログラムとちゃんと作動するプログラムを比べると、18行目の1個目のfor文「for(i=1;i<n-1;i++)」はiがn-1より小さい間ループし続けるという意味なのですが、「<」この記号ではn-1は含まない事になってしまっていました。

このプログラムでは整数しか扱っていないので実質、iが「n-2」より小さい間という事になっていて、ループが一つ足りない状態で終わってしまっていました。

以下が以前書いたプログラムです。

バブルソートの仕組み

上の図は、バブルソートの一場面です。

基本的には、右から２番目の数とその右隣にある数を比べて、右が大きく（＜）なっていれば何もしない。左が大きく（＞）なっていたら交換する、という動作を繰り返してソートしていきます。

これが、プログラムでいう20~25行目のif文です。

これを繰り返すのですが、ソートしなければならない数（n）だけを頼りに、どことどこの数字を比べるのかを決めるプログラムを書かなければいけません。

数字４つの場合、全ての手順を書くと上の図のようになります。

図のようにソートを完成させるには、右から左まで一回比較しながら通り過ぎればいいのではなく、何度かやらなければいけません。

１周目は、ソートしなければならない数（n）-1回先ほどのif文を実行します。

これによって一番左の数は必ず一番小さい数が来るのでソートにかけられる必要がなくなり、確定となります。

２周目は、一番左の数を排除して考えられるため、ソートしなければならない数（n）-2回です。

これによって一番左の数と左から２番目の数までソートにかけられる必要がなくなり、確定となります。

３周目は１回だけ。というようにソートが完成していきます。

これはプログラムでいうと、19行目のfor文です。

では18行目、一番外のfor文は何かというと、何周するかを決めているfor文です。

ソートしなければならない数（n）が４であれば、３周した後、自動的に最後の１つは確定するので、n-1周です。

そうそう、この図、アルゴリズムの仕組みだけではなく、アルゴリズムの計算量もわかりますね。

計算量は、単純にIf文で比較（＞）が行われる回数です。

それでいうと...だいたいソートしなければならない数（n）の二乗÷２ですね。

図などを書いている間に私自身、バブルソートをより理解しました。

微積の勉強横目にアルゴリズムにハマりそうです笑