C++の基礎 - ソート

単純選択法 (選択ソート)

単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。

1. まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。
2. 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。
3. この操作を、配列の最後の要素の手前まで繰り返すことにより、データを昇順 (または降順) に整列することができる。

例えば、{5, 3, 1, 4, 2}という配列をソートする場合、
まず最初の位置から開始して、全体から最小値 (この場合では1) を見つけて、最初の位置 (この場合では5) と交換する。
次に、2番目の位置 (この場合では3) から開始して残りの要素から次の最小値の2を見つけて、3と交換する。
この処理を順々に繰り返す。

単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。
配列の長さをnとすると、計算量は $O(n^{2})$ となる。
また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。
ただし、必要な追加のメモリ容量が少ないというメリットがある。

 #include <iostream>
 
 using namespace std;
 
 int main()
 {
    // 配列 (要素数8) を初期化
    int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50};
    int n = 8;  // 配列のサイズ
 
    cout << "ソート前の配列: ";
    for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
    }
    cout << endl;
 
    // 選択ソートのアルゴリズム
    for (int i = 0; i < n - 1; i++) {
       // 未ソート部分から最小値を探す
       int min_idx = i;
       for (int j = i + 1; j < n; j++) {
          if (arr[j] < arr[min_idx]) {
             min_idx = j;
          }
       }
 
       // 最小値を見つけたら、現在の位置と交換
       if (min_idx != i) {
          int temp     = arr[i];
          arr[i]       = arr[min_idx];
          arr[min_idx] = temp;
       }
 
       // 各ステップでの配列の状態を表示
       cout << "ステップ " << i+1 << ": ";
       for (int k = 0; k < n; k++) {
          cout << arr[k] << " ";
       }
       cout << endl;
    }
 
    cout << "ソート後の配列: ";
    for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
 }

# 出力例:
ソート前の配列: 64 34 25 12 22 11 90 50

ステップ 1: 11 34 25 12 22 64 90 50
ステップ 2: 11 12 25 34 22 64 90 50
ステップ 3: 11 12 22 34 25 64 90 50
ステップ 4: 11 12 22 25 34 64 90 50
ステップ 5: 11 12 22 25 34 64 90 50
ステップ 6: 11 12 22 25 34 50 90 64
ステップ 7: 11 12 22 25 34 50 64 90

ソート後の配列: 11 12 22 25 34 50 64 90