バブルソート

1. バブルソートアルゴリズム
2. バブルソートアルゴリズムの例
3. バブルソートアルゴリズムの実装
4. バブルソートアルゴリズムの複雑さ

バブルソートは単純なソートアルゴリズムです。これは、隣接する要素を繰り返し比較し、順番が間違っている場合はそれらを入れ替えることで動作します。比較を繰り返すことで、最小/最大の要素が配列の最後に向かってバブルアップしていくので、このアルゴリズムはバブルソートと名付けられました。非効率的ではありますが、ソートアルゴリズムの基礎となっています。

バブルソートアルゴリズム

n 個の要素を含むソートされていない配列 A[] があるとしましょう。

上記アルゴリズムのステップ 1 はパスとも呼ばれます。サイズ n の配列をソートするには、n-1 パスが必要です。

バブルソートアルゴリズムの例

配列があるとしましょう。(5,3,4,2,1). これをバブルソートアルゴリズムを用いてソートします。

• 最初のパス

• 2 回目のパス

• 3 回目のパス

• 4 回目のパス

4 回目のパスの後、ソートされた配列が得られます - (1 2 3 4 5).

バブルソートアルゴリズムの実装

#include <iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubble_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

バブルソートアルゴリズムの複雑さ

時間複雑度

• 平均のケース

平均的には、バブルソートの ith パスで n-i 比較が行われます。したがって、n 個のパスがある場合、平均時間の複雑さは次のように与えられます。

(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2

したがって、時間の複雑さは O(n²)のオーダーになります。

• 最悪のケース

最悪のケースは、配列が逆ソートされたときに発生し、最大数の比較とスワップを実行しなければなりません。

最悪のケースの時間的複雑さは、O(n²)です。

• 最良のケース

最良のケースは、配列が既にソートされていて、N 回の比較だけが必要な場合です。

最良の時間的複雑さは O(n) です。

空間計算量

テンポラリ変数以外に余分なメモリを必要としないため、このアルゴリズムの空間複雑度は O(n) です。