「C++の基礎 - ソート」の版間の差分

📢 Webサイト閉鎖と移転のお知らせ

このWebサイトは2026年9月に閉鎖いたします。

移転先はhttps://mochiu.net/index.php?title=C++の基礎 - ソートです。

新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）

← 古い編集

ビジュアルウィキテキスト

@@ 4行目: / 4行目: @@
 == バブルソート ==
-バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。
+バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。<br>
-大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。
+大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。<br>
+<br>
 # 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。
 # この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。
 # 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。
 <br>
-バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。
+バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。<br>
-安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。
+安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。<br>
 <br>
   <syntaxhighlight lang="c++">
@@ 238行目: / 238行目: @@
   ステップ 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
+<br><br>
+== マージソート ==
+マージソートは、分割統治法に基づくソートアルゴリズムである。<br>
+配列を再帰的に半分に分割して、それぞれをソートした後にマージ (統合) することにより全体をソートする。<br>
+<br>
+# 配列を半分に分割する。
+# 分割した各部分を再帰的にソートする。
+# ソートされた2つの部分配列をマージして1つの配列にする。
+<br>
+計算量は <math>O(n \log{n})</math> で、クイックソートと同様に効率的なアルゴリズムである。<br>
+安定なソートであり、データの偏りに影響されず常に一定の性能を発揮する。<br>
+ただし、追加のメモリ空間が必要という特徴がある。<br>
+<br>
+マージソートは大規模なデータセットの処理に適しているが、追加メモリが必要なためメモリ制約が厳しい環境では注意が必要となる。<br>
+<br>
+ <syntaxhighlight lang="c++">
+ #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;
+ }
+ </syntaxhighlight>
+<br>
+ # 出力例:
+ ソート前の配列: 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