選択ソートについて、わかりやすくまとめる

選択ソートアルゴリズムについて、わかりやすくまとめたいと思います。

選択ソートは、数列の中から最大または最小の数値を探しだして、その数値と左端の数値を交換することで、 ソートしていくアルゴリズムです。

では、例題で確認してみます。

選択ソートの例題

以下の数列を選択ソートを使ってを昇順に並べて変えてみたいと思います。
昇順に並び替えるので、最小値を選択して数列の左端から並び替えることにします。

5,4,8,7,9

また、対象となっている文字を赤で、ソート済みの数値を緑で表示して、わかりやすくしてみます。

一回目の選択

数列の左端から右端まで最小の値を探していきます。

5,4,8,7,9

左端の値5を最小の値として保存します。
次に右を探索していき、5よりも最小の値があれば、最小の値を更新します。

5,4,8,7,9

5 > 4なので、最小の値が4に変わりました。
次に、8,7,9をチェックしていきますが、最小値は4のままなので、
4と5を交換します。

4,5,8,7,9

これで、最小値がきまり、左端の値が決定しました。
次に、2番目の値つまり5からまた、最小値を探して交換を繰り返していきます。

これが選択ソートになります。

選択ソートの計算量

データの総数をNとすると、
未ソート部分の最小値を探し出すのに、N - 1回、N - 2回, N - 3回、...、1の比較演算を行います。

よって、合計の比較演算回数は、常に(N^2 - N) / 2になるので、 N^2に比例するため、O(N^2)のアルゴリズムになります。