バブルソート Bubble Sort

選択ソートはある決められた範囲から、最小値を見つけ要素の交換を行いました。バブルソートは、隣り合う要素の比較のみを繰り返すことによって並び替えを行います。

バブルソートのアルゴリズムを以下に示します。

各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。 未ソートの部分がなくなるまで、以下の処理を繰り返します。 データの先頭から隣どうしを比較して、大小関係が逆ならばそれらを交換していきます。この交換処理を未ソートの部分の末尾まで順番に行います。

バブルソートはその名前からイメージできるように、泡（Bubble）が水面に上がっていくようにデータが動いていきます。上記のアルゴリズムでは、ソートされたデータが配列の後ろから順番に決定されていきます。

具体的な例で、バブルソートの流れを初期状態から見てみましょう。上図に示す処理が終了すると、データの中で一番大きい要素が配列の末尾に移動します。続きの処理を下図に示します。



上図のステップ1.～5.が終了すると、データの中で2番目に大きい要素が配列の後ろから2番目に移動します。以下同様に、ステップ6.～9.、ステップ10.～12.、ステップ13.～14.でそれぞれソート済みの部分に追加されるデータが決まっていきます。

以下のプログラムはは、データの数 size　を読み込み、size個の整数のデータを配列 data に読み込んで、配列の要素をバブルソートによって昇順に整列し、それを出力します。プログラムの本体である bubbleSort を見てみましょう。下図に示すように、07行目の最初のループ変数であるendは未ソートの部分の末尾を示します。08行目のforループによってデータの先頭からendまでの範囲で、隣どうしを比較して逆順ならば交換する処理を繰り返します。この２番目のループが終わると、その範囲のなかで一番大きい値がソートされていない部分の末尾に移動します。

#include<iostream>
using namespace std;

#define MAX 100

void bubbleSort( int size, int data[] ){
    for ( int end = size - 1; end > 0; end-- ){
        for ( int j = 0; j < end; j++ ){
            // 隣どうしを比較して、逆順ならば交換
            if ( data[j+1] < data[j] ){
                int tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

バブルソートの計算量を考えてみましょう。データの数をnとすると、バブルソートは未ソートの部分における隣どうしの比較演算をn-1回、n-2回、n-3回、・・・、1回行います。よって合計の比較演算の回数は(n²-n)/2となり、バブルソートはO(n²)のアルゴリズムとなります。

練習問題