SE基本情報に出るIT用語

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

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

図にするとこんな感じ。

選択ソート
  1. データのかたまりの最小値をえらぶ
  2. えらんだ最小値を先頭に持っていく
  3. 1.でえらんだ値を除いてすべでのデータに対してくり返す

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

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

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

スポンサーリンク

選択ソートのやりかた

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

  1. データのかたまりの最小値をえらぶ
  2. えらんだ最小値を先頭に持っていく
  3. 1.でえらんだ値を除いてすべでのデータに対してくり返す

念のために言っておくと、左ではなく右から順でも問題なし。最小値でなく、最大値から順番にアプローチしても最終的にはソートができます。

今回は、

[9, 32, 17, 1, 4]

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

数字の初期値_1

1回目(いちばん左の数字の確定)

まず、いちばん左の数字を確定させるために、左から順番に、最小値を探します。

人間が見れば、パッと見て「最小値は”1″だ!」って探すことになりますが。

プログラムにお任せするなら、「最小値」みたいな箱を作っておいて(変数を宣言しておいて)、先頭から順番に数字を比較。

選択ソートの最小値の比較

先頭の9からスタート
⇒9<32(最小値を入れ替えない)
⇒9<17(最小値を入れ替えない)
9>1(最小値を入れ替える)
⇒1<4(入れ替えない)
⇒1が最小値

みたいな感じで決めていくと、最小値は”1″です。4番目にある”1″を一番左に持っていきます。

選択ソートの最小値を探す_1回目

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

選択ソートの確定_1回目

2回目(2番目の数字)

次に、2番目の数字を確定させるために、1番目をのぞいた先頭(2番目)から順番に、最小値を探します。

2番目の9からスタート
⇒9<32(最小値を入れ替えない)
⇒9<17(最小値を入れ替えない)
9>4(最小値を入れ替える)
⇒4が最小値

最小値は”4″です。5番目にある”4″を2番目(1番目は確定済み)に持っていきます。

選択ソートの最小値を探す_2回目

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

選択ソートの確定_2回目

3回目(3番目の数字)

次に、3番目の数字を確定させるために、1番目と2番目をのぞいた先頭(3番目)から順番に、最小値を探します。

3番目の9からスタート
⇒9<32(最小値を入れ替えない)
⇒9<17(最小値を入れ替えない)
⇒9が最小値

今回は、最小値と3番目の数字が一致しているので、入れ替えなしで3番目の数字が確定します。

選択ソート_3回目の確定

4番目の数字の確定(これで全部確定)

次に、4番目の数字を確定させるために、1番目、2番目、3番目をのぞいた先頭(4番目)から順番に、最小値を探します。

4番目の32からスタート
⇒32>17(最小値を入れ替える)
⇒17が最小値

最小値は”17″なので、5番目にある”17″を4番目に持っていきます。

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

あれっ・・・?

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

その通りです!

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

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

  • バブルソート(基本交換法)】先頭から順にとなり合うデータを比較
  • 【挿入ソート(基本挿入法)】整列済みの列を増やしていって未整列の値を挿入
  • 【シェルソート】一定間隔おきに取り出した値の列を並び替えて元に戻す
  • 【クイックソート】基準値を決めて大小のグループに振り分けて並び替え
  • 【ヒープソート】ツリー構造をつくって親と子の大小比較する

まとめ

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

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

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

▼この記事がいいと思ったら、下の画像をクリックしてくれたら励みになります!

にほんブログ村 IT技術ブログ システムエンジニアへ
スポンサーリンク
ひよこSEのつぶやきブログ

コメント

タイトルとURLをコピーしました