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

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

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

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

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

シノ

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

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

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

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

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

では、アルゴリズムを。

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

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

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

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

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

では、まずi=0から。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;
    }
}

おわりに

今回は、選択ソートの解説を行った。

次回解説する挿入ソートと似ているので、混同しないよう注意してほしい。

というわけで、次回は挿入ソートだ。

次回の挿入ソートで、単純なソートアルゴリズムは終わりだ。

その後は、余力があれば高速なアルゴリズムも解説しようと思う。