MochiuWiki : SUSE, EC, PCB

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

← 古い編集
ビジュアルウィキテキスト
 
(同じ利用者による、間の2版が非表示)
1行目: 1行目:
== 概要 ==
== 概要 ==


<br><br>
== バブルソート ==
バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。<br>
大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。<br>
<br>
# 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。
# この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。
# 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。
<br>
バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。<br>
安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。<br>
<br>
<syntaxhighlight lang="c++">
#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;
}
</syntaxhighlight>
<br>
# 出力例:
ソート前の配列: 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
<br><br>
<br><br>


161行目: 238行目:
  ステップ 6: 11 12 22 25 34 64 90 50  # 90は既にソート済み部分の要素より大きいため、位置は変わらない
  ステップ 6: 11 12 22 25 34 64 90 50  # 90は既にソート済み部分の要素より大きいため、位置は変わらない
  ステップ 7: 11 12 22 25 34 50 64 90  # 50を64と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
  ソート後の配列: 11 12 22 25 34 50 64 90
「https://mochiu.net/index.php/C%2B%2Bの基礎_-_ソート」から取得