C++の基礎 - ソート

バブルソート

バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。
大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。

1. 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。
2. この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。
3. 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。

バブルソートの実装は簡単であるが、計算量は $O(n^{2})$ となる。
安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。

 #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 = 0; i < n - 1; i++) {
       bool swapped = false;  // 交換が発生したかを記録
 
       for (int j = 0; j < n - 1 - i; j++) {
          // 隣接要素を比較し、必要に応じて交換
          if (arr[j] > arr[j + 1]) {
             int temp   = arr[j];
             arr[j]     = arr[j + 1];
             arr[j + 1] = temp;
             swapped    = true;
          }
       }
 
       // 各ステップでの配列の状態を表示
       cout << "ステップ " << i + 1 << ": ";
       for (int k = 0; k < n; k++) {
          cout << arr[k] << " ";
       }
       cout << endl;
 
       // 交換が発生しなければソート完了
       if (!swapped) {
          break;
       }
    }
 
    cout << "ソート後の配列: ";
    for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
 }

# 出力例:

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

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

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

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

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

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

# 出力例:

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

ステップ 1: 34 64 25 12 22 11 90 50  # 2番目の要素34に注目し、前の要素64と比較する。34 < 64なので、64を右にずらし、34を挿入する
ステップ 2: 25 34 64 12 22 11 90 50  # 3番目の要素25に注目し、前の要素と順に比較する。25は34, 64より小さいため、これらを右にずらし、適切な位置に25を挿入する
ステップ 3: 12 25 34 64 22 11 90 50  # 4番目の要素12に注目し、同様に比較と挿入を行う。12は最小値なので配列の先頭に移動する
ステップ 4: 12 22 25 34 64 11 90 50  # 22を12と25の間に挿入する
ステップ 5: 11 12 22 25 34 64 90 50  # 11を比較しながら移動させて、配列の先頭に挿入する
ステップ 6: 11 12 22 25 34 64 90 50  # 90は既にソート済み部分の要素より大きいため、位置は変わらない
ステップ 7: 11 12 22 25 34 50 64 90  # 50を64と90の間の適切な位置に挿入する

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

マージソート

マージソートは、分割統治法に基づくソートアルゴリズムである。
配列を再帰的に半分に分割して、それぞれをソートした後にマージ (統合) することにより全体をソートする。

1. 配列を半分に分割する。
2. 分割した各部分を再帰的にソートする。
3. ソートされた2つの部分配列をマージして1つの配列にする。

計算量は $O(n\log {n})$ で、クイックソートと同様に効率的なアルゴリズムである。
安定なソートであり、データの偏りに影響されず常に一定の性能を発揮する。
ただし、追加のメモリ空間が必要という特徴がある。

マージソートは大規模なデータセットの処理に適しているが、追加メモリが必要なためメモリ制約が厳しい環境では注意が必要となる。

 #include <iostream>
 
 using namespace std;
 
 // マージを行う関数
 void merge(int arr[], int left, int mid, int right)
 {
    int n1 = mid - left + 1;
    int n2 = right - mid;
 
    // 一時配列の作成
    int L[n1], R[n2];
 
    // データのコピー
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
 
    // マージ処理
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
       if(L[i] <= R[j]) {
          arr[k] = L[i];
          i++;
       }
       else {
          arr[k] = R[j];
          j++;
       }
       k++;
    }
 
    // 残りの要素をコピー
    while (i < n1) {
       arr[k] = L[i];
       i++;
       k++;
    }
 
    while(j < n2) {
       arr[k] = R[j];
       j++;
       k++;
    }
 }
 
 // マージソートを行う再帰関数
 void mergeSort(int arr[], int left, int right)
 {
    if (left < right) {
       int mid = left + (right - left) / 2;
 
       mergeSort(arr, left, mid);      // 左半分をソート
       mergeSort(arr, mid + 1, right); // 右半分をソート
       merge(arr, left, mid, right);   // マージ
 
       // 現在の配列の状態を表示
       cout << "部分ソート (left=" << left << ", right=" << right << "): ";
       for (int i = 0; i < 8; i++) {
          cout << arr[i] << " ";
       }
       cout << endl;
    }
 }
 
 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;
 
    mergeSort(arr, 0, n - 1);
 
    cout << "ソート後の配列: ";
    for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
 }

# 出力例:

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

部分ソート (left=0, right=1): 34 64 25 12 22 11 90 50
部分ソート (left=0, right=2): 25 34 64 12 22 11 90 50
部分ソート (left=3, right=4): 25 34 64 12 22 11 90 50
部分ソート (left=3, right=5): 25 34 64 11 12 22 90 50
部分ソート (left=6, right=7): 25 34 64 11 12 22 50 90
部分ソート (left=3, right=7): 25 34 64 11 12 22 50 90
部分ソート (left=0, right=7): 11 12 22 25 34 50 64 90

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