単純なソートアルゴリズム「選択ソート」を解説！

前回は、バブルソートを解説した。

これは、単純なソートアルゴリズムと呼ばれるソートの一つだ。

今回は、二つ目の選択ソートについて解説していく。

三つ目の挿入ソートとよくごっちゃになるため、気を付けていこう。

シノ

並び替えるときのデータの動きを
しっかり追っていこう！

単純なソートアルゴリズムの一つ「バブルソート」
選択ソートの計算量
選択ソートのサンプルプログラム
おわりに

単純なソートアルゴリズムの一つ「バブルソート」

これは、ソート済みでない部分から最小のデータを見つけ、それをソート済みの一番後ろに移動する、ということを繰り返すソートだ。

先に言ってしまうと、これは安定ではない。

その理由も後で解説しよう。

では、アルゴリズムを。

前回と同じように、入力はn個の要素を持つ配列dataとしよう。

そして、出力も並び替えが終了したdataとする。

iを0からn-2まで1つずつ増やしながら、以下を繰り返す
1. data[i]からdata[n-1]までで最も小さい数を見つけ、その添え字をkとする
2. data[i]とdata[k]を入れ替える
dataを出力する

これまた、具体例を見ていこう。

前回と同じく、以下の配列を並び替えるとしよう。

i	0	1	2	3	4	5
data[i]	5	3	4	1	2	6

ソートする配列

では、まずi=0から。

data[0]からdata[5]までの中で一番小さいのは、data[3]の1だ。

というわけで、k=3となる。

よって、data[0]とdata[3]を入れ替えて、以下のようになる。

i	0	1	2	3	4	5
data[i]	1	3	4	5	2	6

ソート途中経過1

これで、先頭の1はソート済みとなった。

次に、i=1で、ソートする範囲を狭める。

data[1]からdata[5]で一番小さいのは、data[4]の2だ。

なので、data[1]とdata[4]を入れ替える。

i	0	1	2	3	4	5
data[i]	1	2	4	5	3	6

ソート途中経過2

これで、data[1]までが並び替え完了だ。

以降、同じことをどんどん繰り返していく。

途中経過だけお見せしよう。

i	0	1	2	3	4	5
data[i]	1	2	3	5	4	6

ソート途中経過3

i	0	1	2	3	4	5
data[i]	1	2	3	4	5	6

ソート途中経過4

i	0	1	2	3	4	5
data[i]	1	2	3	4	5	6

ソート途中経過5

これで、data[4]までソート完了、かつ残り一つが一番大きいものなので、全体のソートも完了となる。

これが、選択ソートの流れだ。

では、ここで安定でないことの具体例をお見せしよう。

以下のデータを並び替えるとしよう。

i	0	1	2	3
data[i]	9	3	9	2

ソートする配列2

分かりやすいように、一個目の9を赤太字、二個目の9を青太字にしてある。

これを、同じように並び替えてみよう。

i	0	1	2	3
data[i]	2	3	9	9

ソートする配列2 ソート結果

一回で最終的な形になってしまうのだが、このようになる。

9の位置が前後逆転してしまっているのが分かるだろうか。

このように、選択ソートは安定でない。

単なる数値の並び替えであれば問題ないと思うが、他にデータが存在する場合は気を付けよう。

選択ソートの計算量

次に、選択ソートの計算量を見ていこう。

先に、心配な方は計算量も解説しているので、そちらをご参照頂きたい。

計算量とは？プログラムの性能を計ってみよう | Shino’s Mind Archive

実は、回数を見ると、バブルソートと全く同じになっている。

つまり、計算量もバブルソートと同じく\(O(n^2)\)となる。

詳しい計算は、バブルソート編を見て欲しい。

単純なソートアルゴリズム「バブルソート」を解説！ | Shino’s Mind Archive

選択ソートのサンプルプログラム

最後に、参考までに選択ソートのサンプルプログラムを載せておこう。

言語はJavaScript、他の言語でも大体同じになるはずだ。

function selection_sort(arr){
    var n = arr.length;
    for(var i = 0; i < n - 1; i++){
        var k = i;
        for(var j = i; j < n; j++){
            if(arr[k] > arr[j]){
                k = j;
            }
        }
        var tmp = arr[i];
        arr[i] = arr[k];
        arr[k] = tmp;
    }
}