バブルソート

バブルソートはリストにおいて基点となる要素とそれ以外の要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。

条件とは値の大小関係です。「値の大きい順(降順)」か「値の小さい順(昇順)」にリストを並び替えます。

このソートを実行すると値の大きいまたは小さい要素が浮かびあがってくるように見えることから、バブル(bubble: 泡)ソートと呼ばれます。

アルゴリズム分析

リストを昇順に整列させる手順。

1. リストから要素をひとつ取り出す - 基点となる要素'A'
2. 要素'A'と次の要素'B'の値を比較する
3. 要素'A'が要素'B'より大きいなら、要素'A'と要素'B'の値を交換する
4. 要素'A'と要素'C'、要素'A'と要素'D'のように各要素との比較/交換をリストの終端まで行う
5. リスト中で最も大きい値を持つ要素または小さい要素が基点となった位置へ浮かびあがる
6. 基点となる要素を次へ進めて(要素'B')リストの終端まで手順2〜6を繰り返す

1.) 1番目の要素と2番目の要素を比較 - 交換しない

    | 1 | 7 | 3 | 5 |

2.) 1番目の要素と3番目の要素を比較 - 交換しない

    | 1 | 7 | 3 | 5 |

3.) 1番目の要素と4番目の要素を比較 - 交換しない

    | 1 | 7 | 3 | 5 |

4.) 2番目の要素と3番目の要素を比較 - 交換する

    | 1 | 7 | 3 | 5 |

5.) 2番目の要素と4番目の要素を比較 - 交換しない

    | 1 | 3 | 7 | 5 |

6.) 3番目の要素と4番目の要素を比較 - 交換する

    | 1 | 3 | 7 | 5 |

6.) ソート完了

    | 1 | 3 | 5 | 7 |

以上のように総当たりで比較を行い、条件に一致する交換を実行することで整列が完了します。

特徴

リストの個数を n とすると、バブルソートは必ず n(n - 1)/2 回のスキャンが行われます。

n 個のリストがある場合、1回目で1番目に軽い(小さい)値がリストの先頭に移動してゆき、2回目のスキャンで2番目に軽い値を浮かびあがらせ、3回目のスキャンで・・・、という具合に n 回のスキャンで n 番目に軽い値を浮かびあがらせるのがバブルソートの特徴です。 (条件を入れ換えると「重い(大きい)値を浮かびあがらせる」と述べることができます)

リストの個数が多くなればなるほど処理速度も遅くなりますが、シンプルなアルゴリズムなのでデータ量が少ないときには手軽に実装できます。

サンプルコード

C言語

配列を昇順に並び替えるバブルソートの実装です。比較対象となる要素は配列の終端から基点となる要素へ移動します。

void bubbleSort(int numbers[], int array_size)
{
  int i, j, temp;

  for (i = 0; i < (array_size - 1); i++) {
    for (j = (array_size - 1); j > i; j--) {
      if (numbers[j-1] > numbers[j]) {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}