その７ 並び替えのアルゴリズム

というわけで、探索にはソートが有効であるということがわかっていただけたでしょうか？

ソートさえしていれば二分探索法が使えるので、大変便利でございますよね。

並び替えも大変なんですか？

それにもいろいろやり方があります。今日はいろんなソートについて勉強します。

ちょっと、外に行ってきます。ソートだけに。

そーとー悪い生徒ですね、やうたん・・・。



バブルソート
バブルソートは、隣接するデータの値を比較して、並べ替えるべきかどうかを判断し、
必要に応じて並べ替える動作を繰り返す手法です。逐次比較することで、最終的に
はデータの先頭から末尾までを順番に整列することができます。

左を小さい数字、右を大きい数字に並び替えるとしますよね。

初　期　８３４６７２１５　
１回目　３４６７２１５８　（８を移動させていく。移動回数７）
２回目　３４６２１５７８　（７を移動。移動回数３）
３回目　３４２１５６７８　（６を移動。移動回数３）
４回目　３２１４５６７８　（４を移動。移動回数２）
５回目　２１３４５６７８　（３を移動。移動回数２）
６回目　１２３４５６７８　（２を移動で終了。移動回数１。合計１８回）

こんなふうに動いていきます。

しらみつぶしですね。

そうだそうだ。

・・・そうでもないんですけど、結果的に小さい数字が右側にあるときに・・・
若干時間がかかる特徴があります。数字を並び替えて実験してみましょう。
（極端な例ですけどね）


初　期　８７６５４３２１　
１回目　７６５４３２１８　（８を移動させていく。移動回数７）
２回目　６５４３２１７８　（７を移動。移動回数６）
３回目　５４３２１６７８　（６を移動。移動回数５）
４回目　４３２１５６７８　（５を移動。移動回数４
５回目　３２１４５６７８　（４を移動。移動回数３）
６回目　２１３４５６７８　（３を移動。移動回数２）
７回目　１２３４５６７８　（２を移動で終了。移動回数１。合計２８回。）


詳しくは基本情報処理技術者試験でやりますので、今回はざーっとでいいですよ！

（つづきます）