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

単純挿入法 (挿入ソート)

単純挿入法 (挿入ソート) は、トランプのカードを手に持って整理する時の動作に似たソートアルゴリズムである。

配列を"ソート済み部分"と"未ソート部分"に分けて、未ソート部分から要素を1つずつ取り出し、ソート済み部分の適切な位置に挿入する。

1. まず、配列の先頭要素をソート済みと看做して、2番目の要素から順に処理する。
2. 処理対象の要素 (key) を一時的に保持して、ソート済み部分を後ろから順に走査して、keyより大きい要素は1つ右にずらす。
3. そして、最終的にkeyよりも小さい要素を見つけた位置 (または配列の先頭) の右側にkeyを挿入する。

単純挿入法 (挿入ソート) の特徴として、既にある程度ソートされているデータに対しては効率的に動作する。
これは、ソート済み部分での探索が早く終わるからである。
また、同じ値の要素の相対的な順序が保たれるため、安定なソートである。

計算量においては、最悪の場合で $O(n^{2})$ となるが、ほぼソートされているデータに対しては $O(n)$ に近い性能を示す。

メモリ使用量は、ソートを配列内で直接行うことができるため、追加のメモリをほぼ必要としないというメリットがある。

 #include <iostream>
 
 using namespace std;
 
 int main()
 {
    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 = 1; i < n; i++) {
       int key = arr[i];  // 挿入する値
       int j = i - 1;     // ソート済み部分の末尾
 
       // keyより大きい要素を右にずらす
       while (j >= 0 && arr[j] > key) {
          arr[j + 1] = arr[j];
          j = j - 1;
       }
       arr[j + 1] = key;
 
       // 各ステップでの配列の状態を表示
       cout << "ステップ " << i << ": ";
       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;
 }