知ってるようで知らない「アルゴリズム」をプログラムコードで書いてみたいと思います。
そして、さらに色んな言語で書いてみて、アルゴリズムと言語を同時に勉強してしまおうという企画
初回はソート・アルゴリズムの基本中の基本「バブルソート」をやってみます。
バブルソートについて
有名なアルゴリズムだけど知らない人からすると、「泡」のソートってなんやねん！って事になる。
でも直訳の「泡」で間違いではなく、泡は水の中で下から上に上っていく様子がこのアルゴリズムの語源だそうです。
そして、アルゴリズムを簡単に書くと、デタラメに縦に並んだ数値を上から２つずつ比較して、上の方が大きければ交換をしていく。
何度も繰り返す内に、一番上が最小値、一番下が最大値の昇順状態になるという事です。
画像で説明すると以下の様になる。
ソースコード
// ランダムな数値の配列
var numbers = [2,12,7,16,8,13];
//入れ替えが無くなるまで繰り返す
while(true){
// 上位から順に２つの数値を比較して、小さい数値を左、大きい数値を右にしていく
flg=0;
for(var i=0; i<numbers.length-1; i++){
var num1 = numbers[i];
var num2 = numbers[i+1];
if(num1 > num2){
numbers[i] = num2;
numbers[i+1] = num1;
flg++;
}
}
if(flg===0){break}
}
console.log(numbers);
解説
上記ソースコードをブラウザのコンソール画面にコピペすると結果が出ます。
コメントに書いている箇所は説明しなくてもわかると思いますが、for文は配列を1回繰り返す処理で、while文はfor文を1回行なった時に一度も入れ替えが行われなかったという時にbreakするようにしています。
（いわゆる完成状態という事）
素直に書いたプログラムなので、そんなに難しくはないと思うんですが、もっと効率的に書く方法もあるかもしれません。
後々に効率的なプログラムを思いついた場合は、コメントか、記事の修正をしたいと思います。
そういえば、汎用性を考えると関数にすれば良かった・・・
でも、それはそれ、次回は「バブルソート」を別の言語で書いてみたいと思います。
乞うご期待！！
アルゴリズム過去記事
いろいろなプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿