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

バブルソートはリストにおいて隣り合うふたつの要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。

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

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

アルゴリズム分析

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

先頭の要素'A'と隣り合う次の要素'B'の値を比較する
要素'A'が要素'B'より大きいなら、要素'A'と要素'B'の値を交換する
先頭の要素を'B'に移し、要素'B'と隣り合う要素'C'の値を比較/交換する
先頭の要素を'C','D','E'...と移動しながら比較/交換をリストの終端まで繰り返す
最も大きい値を持つ要素がリストの終端へ浮かびあがる
リストの終端には最も大きな値が入っているので、リストの終端の位置をずらして(要素数をひとつ減らして)手順1〜6を繰り返す

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

図解

特徴

リストの個数を 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;
      }
    }
  }
}

バブルソートのデモンストレーションプログラム: bubble_sort.c

Python

リストの先頭から値を比較していき、昇順に並べ替えます。一番内側のループが終了すれば最大値がリストの終端に移動するので、次のループではリストの要素数をひとつ減らして比較していきます。

def bubblesort(l):
    for index in xrange(len(l)-1, 0, -1):
        for low in xrange(index):
            if l[low] > l[low+1]:
                tmp = l[low+1]
                l[low+1] = l[low]
                l[low] = tmp
    return l

if __name__ == '__main__':
    from random import shuffle
    l = range(15)
    lcopy = l[:]
    shuffle(l)
    print('Unsorted')
    print l
    assert l != lcopy
    print ('Sorted')
    print bubblesort(l)
    assert l == lcopy