バブルソート(Bubble Sort)

2019年11月23日ソート基本

バブルソートとは

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

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

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

アルゴリズム

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

  • \(i=0\) とする。\(n-1\) まで 1ずつ増やして以下を繰り返す
    • \(j=0\) とする。\(n-i-1\) まで 1ずつ増やして以下を繰り返す
      • \(j, j+1\) 番目の要素同士を比べて、\(j\) 番目のほうが大きかったら入れ替える

このアルゴリズムは2重のループ文で表すことができます。

計算量

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での例 

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

ソート基本