選択ソート セレクションソート Selection Sort

選択ソートは、ソートアルゴリズムの導入となる最も単純なアルゴリズムの１つです。最も思いつきやすく、直感的なアルゴリズムだと思います。

	各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。
	1.「未ソートの部分」から最小の要素を探します。
	2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。
	1. 2. を未ソートの部分がなくなるまで繰り返します。

1. 初期状態は全ての要素が未ソートの部分に属します。 2. 未ソートの部分から最小値2を選択し、未ソートの部分の先頭7と交換します。 3. 未ソートの部分から最小値3を選択し、未ソートの部分の先頭5と交換します。 4. 未ソートの部分から最小値5を選択し、未ソートの部分の先頭11と交換します。 5. 未ソートの部分から最小値6を選択し、未ソートの部分の先頭8と交換します。 6. 未ソートの部分から最小値7を選択し、未ソートの部分の先頭12と交換します。 7. 未ソートの部分から最小値8を選択し、未ソートの部分の先頭11と交換します。 8. 未ソートの部分から最小値11を選択し、未ソートの部分の先頭12と交換します。 9. ソートが完了します。

#include<iostream>
using namespace std;

#define MAX 100

void selectionSort( int size, int data[]){
    for ( int front = 0; front < size - 1; front++ ){
        // 最小値のインデックスを探す
        int minIndex = front; 
        for ( int j = front + 1; j < size; j++ ){
            if ( data[j] < data[minIndex] ) minIndex = j;
        }
        // 未ソート部分の先頭と最小値を交換
        int tmp = data[front];
        data[front] = data[minIndex];
        data[minIndex] = tmp;
    }
}

Program は、データの数 size　を読み込み、size個の整数を配列 data に読み込んで、配列の要素を選択ソートによって昇順に整列し、それを出力します。プログラムの本体である selectionSort を見てみましょう。07行目の最初の for ループによって、「未ソートの部分の最小値と先頭の要素を交換する処理」を繰り返します。Fig.に示すように、front は未ソートの部分の先頭の要素を指します。次の10行目のforループによって、未ソートの部分から最小値を見つけます。インデックスminIndexが最小値を示すように、minIndexを更新していきます。14-16で、最小値と先頭の要素を交換します。

選択ソートの計算量を考えてみましょう。データの数をnとすると、選択ソートは未ソートの部分の最小値を見つけるためにn-1回、n-2回、n-3回・・・1回の比較演算を行います。よって合計の比較演算の回数は(n²-n)/2となり、選択ソートはO(n²)のアルゴリズムとなります。