無差別に技術をついばむ鳥

今回はソートアルゴリズムの基礎バブルソートをつつくピヨ。バブルソートの考え方は

隣と比べて、隣の方が小さければ交換する。これを全ての要素に対して行えば整列している状態になる。

というものピヨ。この考えは文字では分かりにくいから例を挙げてつつくピヨ。



【例：0〜9がある場合】
簡単な例としてこんなデータを整列する事を想像しよう。

ごちゃごちゃだ・・・
9  3  5  6  2  8  7  0  1  4

バブルソートでは、まずは最初の数値9と３を比べる。そして、３の方が小さいから交換するピヨ。チェーンジ！

まだまだごちゃごちゃだ・・・
3  9  5  6  2  8  7  0  1  4

次は２番目の数値９と５を比べるピヨォ。もちろん５の方が小さいからまたチェーンジ！

9「俺また移動かよ・・・」
3  5  9  6  2  8  7  0  1  4

このようにして最後まですると・・・

9「俺最後まで移動された。これって左遷ってやつかなorz」
3  5  6  2  8  7  0  1  4  9

最後まで来たらまた最初から比較交換するピヨ。

3「俺の方が小さいから交換はできないぜ」
3  5  6  2  8  7  0  1  4  9

このように比較して小さかったら何もしないピヨ。うーんもどかしいぃぃ。
後は同じようにして最後まで行くと・・・
9「おい、インドリ。俺はどうせ最後なんだから放っておいてくれ！」
ごめん、ごめん。このように比較するべき回数は減っていくから最後から決まるアルゴリズムと言えるピヨ。 この辺が初心者には難しいと思うピヨ。言語ごとの実装を用意するから デバッガで１行ごとに実行していく とわかりやすいピヨ。出来上がったらこの下にリンクを追加するピヨ。ちょっと待っててね。


【実装リスト】

• なでしこ・・・ 型固定

トラックバックURL

FC2ブログユーザー専用トラックバックURLはこちら