バブルソート(Bubble Sort)

ソート基本

バブルソートとは

バブルソートは安定なソートアルゴリズムの一つです。隣り合う要素の大小関係を見て、入れ替えながらソートしていきます。

他のソートには最悪計算時間が\(O(nlogn)\)のものもありますが、バブルソートの計算量は選択ソートと同様に\(O(n^2)\)となっています。

アルゴリズムが理解しやすく、実装も簡単な安定ソートなので、使用されることがしばしばあります。

アルゴリズム

配列の要素数をnとしたとき、以下のように隣接する要素の小さい方が前へ、大きい方が後ろに来るように入れ替えながらソートします。

  1. \(i=0\)とする
  2. \(j=0\)とする
  3. \(j, j+1\)番目の要素同士を比べて、\(j\)番目のほうが大きかったら入れ替える
  4. \(j\)を1増やす
  5. \(j\)が\(n-i-1\)未満なら3.へ戻る
  6. \(i\)を1増やす
  7. \(i\)が\(n-1\)未満なら2.へ戻る。そうでないなら終了する

このアルゴリズムは2重のループ文で表すことができます。内側のループは3.から5.まで、外側のループは2.から7.までのことです。

計算量

2重ループを用いるので、最悪・平均・最善の計算量は全て\(O(n^2)\)になります。

上述のアルゴリズムでは既にソート済みの配列であっても\(O(n^2)\)だけの時間がかかります。しかし、アルゴリズムの一部を変更することで最善の時の計算量が小さくなります。

内側のループで要素の交換を1度でもしたかをチェックすることで、既にソートされているかどうかを確かめることができます。ソートされた時点で終了するようにすれば、ソート済み配列を受け取った際に最善となり計算量は\(O(n)\)です。

問題例: 配列のソート

実際にバブルソートを用いて配列をソートしてみましょう。今回は\(\{15,38,2, 21\}\)という配列を用います。

外側のループ1回目

  1. \(\{15,38,2, 21\}\) の\(15,38\)は入れ替えない
  2. \(\{15,2,38, 21\}\) の\(38,2\)を入れ替える
  3. \(\{15,2,38, 21\}\) の\(38,21\)を入れ替える
  4. \(\{15, 2,21,38\}\) で内側のループ終了(38はもう動かさない)

外側のループ2回目

  1. \(\{15, 2,21,38\}\) の\(15,2\)を入れ替える
  2. \(\{2,15, 21,38\}\) の\(15,21\)は入れ替えない
  3. \(\{2,15, 21,38\}\) で内側のループ終了(21はもう動かさない)

外側のループ3回目

  1. \(\{2,15, 21,38\}\) の\(2,15\)は入れ替えない
  2. \(\{2,15, 21,38\}\) で内側のループ終了(15はもう動かさない)

これでバブルソートが完了しました。

プログラム例

先程の問題を実際にプログラムで解いてみます。

Pythonでの例 (Colaboratory などで確認してみて下さい)

def bubble_sort(arr):
  n = len(arr)
  for i in range(n-1):
    for j in range(n-i-1):
      if arr[j] > arr[j+1]: # 右隣が小さければ入れ替える
        arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [15,38,2, 21]
bubble_sort(arr)
print(arr) #出力は[2, 15, 21, 38]

C++の例

#include <bits/stdc++.h>
using namespace std;
void swap(int *a, int *b) { // 要素のポインタを受け取ってスワップする関数
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
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]); // 要素へのポインタを渡してスワップ
            }
        }
    }
}
void print_arr(int arr[], int n) { // 配列を出力する関数
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main() {
    int arr[] = {15, 38, 2, 21};
    int n = sizeof(arr) / sizeof(arr[0]); // 配列の長さ
    bubble_sort(arr, n);                  // ソートする
    print_arr(arr, n);                    // 出力は 2 15 21 38
    return 0;
}

ソート基本

Posted by cs-learner