選択ソート(基本選択法)とは？最小値をえらんで先頭に持っていくのを繰り返す並び替え方

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

図にするとこんな感じ。

最小値をえらんで先頭に持っていくのを繰り返してデータを並び替えているので。

1番目⇒2番目⇒3番目⇒・・・

みたいに、先頭から順番に値が確定していきます。

選択ソートのやりかた

選択ソートのやりかたは、冒頭に書いた通りですが、再掲します。

今回は、

[9, 32, 17, 1, 4]

の5つの数字について、１～３の手順で選択ソートを最後まで行います。

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あるデータをならびかえましょう！」みたいにデータが多いときは、別のアプローチが必要です。

あれっ・・・？

バブルソートと比較回数も計算量も同じ？

その通りです！

選択ソートの他に覚えておきたい並び替えのアルゴリズム

選択ソートの他にも、いろんなデータの並び替えのアルゴリズムがあるので、覚えておくとよきです(*´ω｀)。

まとめ

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

基本情報のアルゴリズムで、「選択ソート」って単語が出てきたときに。

「地道に最小値を探して、先頭に持っていくのを繰り返す」っていうのを思い出しながら、問題文を読めるようになってくださいまし(-_-;)。