日常のアルゴリズム | 身長の低い順番に並べる（選択ソート）

選択ソートは、並んでいる値の中から最小値または最大値を選び、決まった位置へ移していく並べ替えのアルゴリズムです。「一番小さいものを探して先頭に置く」という考え方なので、手順を追いやすいのが特徴です。

選択ソートとは

選択ソートでは、まず全体の中から一番小さい値を探します。小さい順に並べたい場合は、その値を先頭に移動します。次に、残りの中から一番小さい値を探し、2番目の位置に移動します。

このように、確定した場所を少しずつ増やしていくのが選択ソートの考え方です。

最初は、全体から最小値を探します。見つかった最小値を先頭に置くことで、先頭の位置が確定します。

次は、まだ確定していない範囲の中から最小値を探します。すでに確定した先頭の値は、もう比較対象に含めません。

これを繰り返すことで、左側から順番に並びが確定していきます。

バブルソートは隣同士を比較して入れ替える方法です。一方、選択ソートは、残っている範囲全体から「次に置くべき値」を選びます。

つまり、バブルソートは値が少しずつ移動していくのに対し、選択ソートは「最小値を見つけて位置を確定する」動きになります。同じ並べ替えでも、考え方が異なります。

選択ソートは、複数のものから一番小さいもの、安いもの、早い日付のものを選び、順番に並べる場面に近い考え方です。たとえば、価格の安い順に商品を並べる、締切が近い順にタスクを並べる、といった場面です。

選択ソートは仕組みが分かりやすい一方、データが増えると比較回数が増えやすい方法です。そのため、アルゴリズムを考えるときは「正しく動くか」だけでなく、「データが増えても使いやすいか」も考える必要があります。