バブルソートはソートの中でもアルゴリズムが単純なもののひとつです。
隣り合うデータを比較・交換していくだけなので、プログラムも簡単です。
データを2つ選び、比較して大小関係が正しくなるように交換する、という操作を繰り返す交換ソートのひとつです。
バブルソートは後述するようにソートの中ではかなり遅いほうなのですが,
実はバブルソートの派生アルゴリズムであるコムソートや奇偶転置ソートなどは非常に高速です。
他のアルゴリズムを知る上でも、バブルソートは重要なソートアルゴリズムとなっています。
アルゴリズム
隣り合う要素を比較して、順序が逆であれば入れ替えるだけです。 もう少し詳しく動作を見るために、次のようなデータを考えます。
このデータを昇順で並べることを考えます。 まずは1番めと2番めを比較します。9 > 5なので順番が逆です。 そこでこの2つのデータを入れ替えます。 以降は交換したデータを太字で表しています。
次は2番めと3番めを比較します。また順番がおかしいので入れ替えます。
次は3番めと4番めを比較…という処理を繰り返していくと次のようになります。
8番めと9番めのデータを比較・交換しました。 このデータを見ると、"9"がどんどん右端へ移動していっていることがわかると思います。 水中の泡が水面へ上昇していく様子に似ているのでバブルソートの名前がついているようです。
ここまでの処理を行うと、必ず「最大の値が右端へ移動する」ことがわかります。 ということは、もう右端は処理の対象にする必要がありませんね？ 図では確定したデータ(比較交換の対象にしなくて良いデータ)は灰色で表示しています。
そこで、次は1番めから8番めのデータのみを対象として同じ操作を繰り返します。 バブルソートは、最大(降順の場合は最小)のデータを端へ移動するという操作を繰り返すことによってソートを行うアルゴリズムです。
1番めから8番めのデータに対して比較・交換を行うと次のようになります。
これで2番めに大きい数である8の位置が確定しました。 このとき、8番めと9番めのデータは比較していないことに注意してください。 9番めのデータは既に確定しているので、比較しても意味がありません。
あとは同じような操作を繰り返すことによって並び替えを行うことが出来ます。 まずは1番めから7番めのデータを処理し、次に1番めから6番めのデータを処理…という操作を繰り返していきます。
最後は1番めから2番めの範囲で比較・交換を行って終了です。
高速化テクニック
次のようなデータをバブルソートでソートすることを考えてみましょう。
まずは"9"が一番右端へ移動することはもうおわかりですね？
これで右端のデータが"9"に確定しました。 次に1番めから8番めのデータに対して同じ処理を繰り返します。 ところが、どのデータを比較しても1度も交換が起きないことが分かります。
もしデータの交換が一度も行われなかったら、データが既に整列済みであると決定できます。 そのため、データが交換されたかどうかをチェックすることによって無駄な処理を省くことが可能です。 簡単な改良ですが、ソート対象のデータの性質によっては非常に高速になります。
このように、「ほとんどソート済み」あるいは「ソート済み」のデータに対して 高速に処理できるという性質は、場合によってはとても重要になります。 たとえば、既存のソート済みデータに対して新しいデータを追加したいときなどに効果を発揮します。 また、この性質を利用して他のソートアルゴリズムを改良することも出来ます。 このあたりについては、また別の記事で触れたいと思います。
時間計算量
バブルソートの時間計算量を求めてみましょう。 ここでは、データの個数を 
とします。100個のデータをソートするのなら、 
です。 話がややこしくなるので、先ほどの高速化テクニックは使わないことにします (先のテクニックを使う場合は、最速の場合 )
でソートできます)。
まず一つのデータの位置を確定するのに、 )
回の比較が必要です。 次は比較回数が1回少なくなるので、 )
回の比較が必要です。 これの繰り返しが平均時間計算量になります。
まず、
%20%2B%20(n-2)%20%2B%20...%20%2B%20(n-(n-2))%20%2B%20(n-(n-1))%20%5C%5C%3D%20(n-1)%20%2B%20(n-2)%20%2B...%2B%202%20%2B%201)
これは単に1からn-1までの総和なので、
であることがわかります。 これは等比数列の和を考えると次のように表せますね。
%7D%7B2%7D%20%3D%20%5Cfrac%7Bn%5E2-n%7D%7B2%7D)
以上から、
)
であることがわかります。
空間計算量
空間計算量は内部ソートなので、外部メモリを使わずにソートできます。 必要なメモリはデータn個を格納するための領域のみです。 つまり、空間計算量は
であることがわかります。
まとめ
バブルソートは実際にはほとんど使われません。 強いて言えば実装が簡単なことがメリットです。 しかし挿入ソートはバブルソートと同じくらい単純なアルゴリズムなのに、挿入ソートの方が少し速いので、あくまでもソートアルゴリズムのお手本程度に考えておいてよいでしょう。
ただし、最初の方にも触れましたが、バブルソートの改良アルゴリズムがいくつかあり、そちらは非常に高速にソートできます。 特にコームソート(コムソート, Comb sort)は、バブルソートを少し改良したアルゴリズムですが時間計算量が )
と大幅な改善を実現しています。
ソースコード
C言語
表示/非表示
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXVALUE 100 //ソート対象のデータ数
#define N 10 //要素の最大値
int data[N];
/*
* ソート対象データを乱数で初期化
*/
void init(){
int i;
for(i = 0; i < N; i++){
data[i] = rand() % MAXVALUE;
}
}
/*
* バブルソート
*/
void bubble_sort(){
int i, j;
int tmp;
for(i = 0; i < N - 1; i++){
for(j = 1; j < N - i; j++){
//データを比較して交換
//(不等号を逆にすると降順になります)
if(data[j - 1] > data[j]){
tmp = data[j - 1];
data[j - 1] = data[j];
data[j] = tmp;
}
}
}
}
int main(int argc, char **argv){
int i;
srand((unsigned) time(NULL)); //乱数のシードを設定する
init();
bubble_sort();
for(i = 0; i < N; i++){
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
Java
表示/非表示
public class Main {
final static int N = 10; //ソート対象のデータ数
final static int MAX = 100; //要素の最大値
public static void main(String[] args){
int[] data = new int[N];
init(data);
bubbleSort(data);
for(int i = 0; i < data.length; i++){
System.out.print(data[i] + " ");
}
System.out.println();
}
/**
* ソートするデータを乱数で生成する
*
* @param data 生成したデータを格納する配列
*/
static void init(int[] data){
for(int i = 0; i < data.length; i++){
data[i] = (int)(Math.random() * MAX);
}
}
/**
* バブルソート
*
* @param data ソート対象データ
*/
static void bubbleSort(int[] data){
for(int i = 0; i < data.length - 1; i++){
for(int j = 1; j < data.length - i; j++){
//不等号を逆にすると降順になります
if(data[j - 1] > data[j]){
int tmp = data[j - 1];
data[j - 1] = data[j];
data[j] = tmp;
}
}
}
}
}
