選択ソート(基本選択法)とは、「最小値をえらんで先頭に持っていくのを繰り返す並び替えの方法」です。
図にするとこんな感じ。

- データのかたまりの最小値をえらぶ
- えらんだ最小値を先頭に持っていく
- 1.でえらんだ値を除いてすべでのデータに対してくり返す
最小値をえらんで先頭に持っていくのを繰り返してデータを並び替えているので。
1番目⇒2番目⇒3番目⇒・・・
みたいに、先頭から順番に値が確定していきます。
選択ソートのやりかた
選択ソートのやりかたは、冒頭に書いた通りですが、再掲します。
- データのかたまりの最小値をえらぶ
- えらんだ最小値を先頭に持っていく
- 1.でえらんだ値を除いてすべでのデータに対してくり返す
念のために言っておくと、左ではなく右から順でも問題なし。最小値でなく、最大値から順番にアプローチしても最終的にはソートができます。
今回は、
[9, 32, 17, 1, 4]
の5つの数字について、1~3の手順で選択ソートを最後まで行います。

1回目(いちばん左の数字の確定)
まず、いちばん左の数字を確定させるために、左から順番に、最小値を探します。
人間が見れば、パッと見て「最小値は”1″だ!」って探すことになりますが。
プログラムにお任せするなら、「最小値」みたいな箱を作っておいて(変数を宣言しておいて)、先頭から順番に数字を比較。

先頭の9からスタート
⇒9<32(最小値を入れ替えない)
⇒9<17(最小値を入れ替えない)
⇒9>1(最小値を入れ替える)
⇒1<4(入れ替えない)
⇒1が最小値
みたいな感じで決めていくと、最小値は”1″です。4番目にある”1″を一番左に持っていきます。

最小値である”1″を一番左に移動させて、最小値の位置は確定です。

2回目(2番目の数字)
次に、2番目の数字を確定させるために、1番目をのぞいた先頭(2番目)から順番に、最小値を探します。
2番目の9からスタート
⇒9<32(最小値を入れ替えない)
⇒9<17(最小値を入れ替えない)
⇒9>4(最小値を入れ替える)
⇒4が最小値
最小値は”4″です。5番目にある”4″を2番目(1番目は確定済み)に持っていきます。

最小値である”4″を2番目に移動させて、2番目の位置は確定です。

3回目(3番目の数字)
次に、3番目の数字を確定させるために、1番目と2番目をのぞいた先頭(3番目)から順番に、最小値を探します。
3番目の9からスタート
⇒9<32(最小値を入れ替えない)
⇒9<17(最小値を入れ替えない)
⇒9が最小値
今回は、最小値と3番目の数字が一致しているので、入れ替えなしで3番目の数字が確定します。

4番目の数字の確定(これで全部確定)
次に、4番目の数字を確定させるために、1番目、2番目、3番目をのぞいた先頭(4番目)から順番に、最小値を探します。
4番目の32からスタート
⇒32>17(最小値を入れ替える)
⇒17が最小値
最小値は”17″なので、5番目にある”17″を4番目に持っていきます。

先頭~4番目の数字すべてが確定したので、末尾の数字も”32″で確定。これですべての数字の並び順が決まりました。

選択ソートの比較回数・計算量
バブルソートの比較回数と計算量(計算にかかる時間)を、さらっと書いておきます(基本情報をうけるだけなら、特に知る必要なし)。
- 【比較回数】n(n-1)/2
- 【計算量(最悪時間計算量)】O(n^2)
比較回数
比較回数は、データ数 n とすると、下記の通り。
(n-1)+(n-2)+・・・+1
※今回の例なら、1回目は、4回数字を比較。2回目は、3回数字を比較しているので、(データの個数ー比較回数)が成り立つ。
これは、初項n-1、末項1、項数n-1の等差数列の和(平均をもとめるのと同じ式)なので
{(n-1)+1}×(n-1)/2=n(n-1)/2
計算量
選択ソートの計算量(最悪時間計算量)は、多重ループするので、O(n^2)です。
※比較回数がn(n-1)/2=(n^2-n)/2で、2乗が出てくる=多重ループである
今回のように、5つくらいなら特に問題ないけど。
「1000あるデータをならびかえましょう!」みたいにデータが多いときは、別のアプローチが必要です。

あれっ・・・?
バブルソートと比較回数も計算量も同じ?

その通りです!
選択ソートの他に覚えておきたい並び替えのアルゴリズム
選択ソートの他にも、いろんなデータの並び替えのアルゴリズムがあるので、覚えておくとよきです(*´ω`)。
- 【バブルソート(基本交換法)】先頭から順にとなり合うデータを比較
- 【挿入ソート(基本挿入法)】整列済みの列を増やしていって未整列の値を挿入
- 【シェルソート】一定間隔おきに取り出した値の列を並び替えて元に戻す
- 【クイックソート】基準値を決めて大小のグループに振り分けて並び替え
- 【ヒープソート】ツリー構造をつくって親と子の大小比較する
まとめ
選択ソート(基本選択法)ときたら、「最小値をえらんで先頭に持っていくのを繰り返す並び替えの方法」のこと。
基本情報のアルゴリズムで、「選択ソート」って単語が出てきたときに。
「地道に最小値を探して、先頭に持っていくのを繰り返す」っていうのを思い出しながら、問題文を読めるようになってくださいまし(-_-;)。
コメント