選択ソート

選択ソート

Selection Sort Animation
クラス	ソート
データ構造	配列
最悪計算時間	О(n²)
最良計算時間	О(n²)
平均計算時間	О(n²)
最悪空間計算量	О(n) total, O(1) auxiliary

選択ソート (selection sort) は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。

このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。

アルゴリズム

データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す（厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後（残り）は必ず最大値になるからである）。大小が入れ替わる降順の場合も同様の手法。

実装例

for(i=0; i<n; i++){
    min = i ;
    for(j=i+1; j<n; j++)  
         if(data[min]>data[j])min = j ;
    swap(data[i],data[min]) ;
}

動作例

初期データ: 8 4 3 7 6 5 2 1　

太字はソート完了した部分

1 4 3 7 6 5 2 8 （1回目のループ終了時）

1 2 3 7 6 5 4 8 （2回目のループ終了時）

1 2 3 7 6 5 4 8 （3回目のループ終了時）

1 2 3 4 6 5 7 8 （4回目のループ終了時）

1 2 3 4 5 6 7 8 （5回目のループ終了時）

この例では、一見して、この時点で既にソート完了したとわかる。しかしデータが多数の場合はそうはいかないし、アルゴリズムで「一見して」ソート完了か否か判断できない。アルゴリズム通りに最後まで処理する必要がある。

1 2 3 4 5 6 7 8 （6回目のループ終了時）

1 2 3 4 5 6 7 8 （7回目のループ終了時）

計算時間

「比較回数」は、n(n-1)/2回。「交換回数」は、各ループで最大1回なので、全体では多くともn-1回。バブルソートと比較すると、「比較回数」は同じだが「交換回数」が少ないので、選択ソートの方が高速である。

安定性

初期データ: 2a 3 2b 1 とすると、

1 3 2b 2a （1回目のループ終了時）

1 2b 3 2a （2回目のループ終了時）

1 2b 2a 3 （3回目のループ終了時）

となり、2a, 2bの前後関係が初期データの状態から維持されていない。よって安定ソートではない。