【日常のアルゴリズム】身長の低い順番に並んでみる（選択ソート）

選択ソートとは

選択ソートとは並べ替えを行うアルゴリズムです。バブルソートのように比較をしながら並べ替えを行うのですが、「隣同士を比較」していたバブルソートとは異なり、「選択ソート」はその名のとおり「選択したものとすべてを比較」します。

例えば、1から5までの数字がランダムで配置された状態から、最終的に「左から小さい値から大きな値に並び替える」ことをゴールとして並び替え（ソート）を行ってみましょう。

選択ソートでは、まず全体の中から基準とする値をひとつ抽出します。抽出する値は最小値または最大値です。今回は小さい値から大きな値に並び替えることを目的としているので、基準は最小値とし、1を探し、先頭に並び替えます。

同様に、また全体の中から「1の次に大きく」、「その他の値よりも小さな値」を探します。今回の例で言えば、2を探すという行動なのですが、選択ソートでならび変える対象にはどのような値が含まれているのか分からない状態であることが前提です。そのため、探し出す際の条件としては「1の次に大きく」、「その他の値よりも小さな値」と2つの条件の設定が必要となります。

これらを繰り返していけば、最終的に残った値が最大値となり、並べ替えが完了します。

バブルソートと同様になかなか気の遠くなるような作業ですが、アルゴリズムとしては比較的簡単な部類になるので、日常の生活でも「とりあえず片っ端から探す」際にはこのような行動を取っているケースがあるのではないでしょうか。

選択ソートを体験する「背の順ゲーム」

選択ソートの仕組みを理解するために、授業内では「数字の大小を理解」するために「背の順ゲーム」として活用できるかもしれません。

身長は健康診断などで全員が把握している情報です。優劣を決めるものではないので、選択ソートと上手く融合できるでしょう。5人1チームくらいに分けてランダム（例えば出席番号順や五十音順）で並んでもらいます。

あとは、選択ソートの要領でどのチームが早く並べ替えができるのかを競ってみたり、どのグループが一番手順が少なく並べ替えできるのかを予想してみるなどのゲーム性をもたせながら、選択ソートを楽しく体験してみてはいかがでしょうか。

選択ソートは一番動作の遅いアルゴリズム

今回紹介した選択ソートは、ソート（並べ替え）のアルゴリズムとしては一番、結果を出すまでに必要な時間のかかる、要は「動作の遅いアルゴリズム」であると言われています。ですが、バブルソートと比較して背の順ゲームを実施してみたりしながら、アルゴリズムを変えるだけで、同様の結果を出すまでにかかる時間が変わることが体験できます。

ぜひいちど、この比較も含めてチャレンジしてみてください。