このページでは、ソートアルゴリズムの１つである「バブルソート」について解説していきます。
まずバブルソートの解説を行い、その次にバブルソートを行うC言語のサンプルプログラムの紹介を行います。
また、（他のソートアルゴリズムでも同様ですが）バブルソートは様々な実装方法で実現することができるため、今回は実装方法を変えた色々なバブルソート関数を紹介していきたいと思います。
バブルソートの考え方の解説は、どのプログラミング言語を利用されている方にも理解していただける内容だと思います！
バブルソートとは
まずはバブルソートがどのようなアルゴリズムであるかを解説します。
バブルソートの特徴
バブルソートには下記のような特徴があります。
- ソート速度は遅い
- 使用メモリが少ない（配列一つ分でソートできる）
- アルゴリズムが簡単
ソート速度は遅いですが、個人的には一番「実装が簡単」なソートアルゴリズムだと思っています。考え方も非常にシンプルです。
スポンサーリンク
バブルソートの考え方
ではバブルソートの考え方について解説していきます。今回はデータの集合を “昇順” にソートすることを前提に解説していきます。
バブルソートは、隣り合うデータの大小関係が逆の場合にその隣り合うデータを交換していくことでソートを行うアルゴリズムになります。
「大小関係が逆」とは、例えば昇順にソートする場合であれば、”前側のデータの方が後ろ側のデータよりも大きい” ことを言います。
逆に降順にソートする場合であれば、”前側のデータの方が後ろ側のデータよりも小さい” ことを言います。
で、隣り合うデータで「大小関係が逆」の場合にデータを交換すれば、これらの大小関係が整います。
バブルソートでは、この「隣り合うデータの交換」をデータの集合の “先頭から最後尾まで” 繰り返し行います。前述の通り、この交換は「大小関係が逆」の場合だけ行います。
例えばソートしたいデータの集合が下の図のようなものであるとしましょう。
まずは先頭から１番目のデータと２番目のデータの大小関係を確認し、「大小関係が逆」であればデータを交換します。この例だと「大小関係が逆」なので、データを交換します。
続いては、先頭から２番目のデータと３番目のデータのデータの大小関係を確認し、同様に「大小関係が逆」であればデータを交換します。この例だとデータは交換しなくて良いことになりますね。
以降も、大小関係を確認する「隣り合うデータ」を１つずつずらしながら、データの集合の最後尾まで同様の処理を行います。
交換を行う前のデータの並びと、先頭から最後尾まで上記の交換を行なった後のデータの並びはそれぞれ下の図のようになります。矢印は交換によってどの位置に移動したかを示しています。
見ていただければ分かる通り、小さいデータは前側に、大きいデータは後ろ側に寄せられていることが分かります。
つまり、一段階ソートが進んだと考えられます。
このソート後のデータの集合に対し、先ほどと同様のことを行って見ましょう！つまり、隣り合うデータの交換をデータの集合の先頭から最後尾まで繰り返し行います。
これにより、データの並びが下の図のようになり、また一段階ソートが進んだことが確認できます。
要はこれの繰り返しです。この繰り返しで、ソートをどんどん進めていきます。
で、いずれは隣り合うデータの交換をデータの集合の先頭から最後尾まで行おうとしても、一度も交換が発生しないケースが発生します。
なぜ交換が行われないかというと、「大小関係が逆」となる隣り合うデータの組み合わせが存在しなくなったからです。
つまり、ソートが完了したことになります！なので、この時点でソート処理を終了することができます。
要はバブルソートとは、“大小関係が逆” の隣り合うデータの交換を繰り返すことでソートを行うアルゴリズムになります。
一連の処理の詳細をまとめると、バブルソートとは、下記のように処理を行うことでソートを行うアルゴリズムになります。
- 下記をデータの集合の先頭から最後尾まで１つずつデータをずらしながら繰り返し行う
- 隣り合うデータの大小関係を比較する
- 大小関係が逆の場合：その２つのデータを交換する
- 隣り合うデータの大小関係を比較する
- 一度でも交換が行われたのであれば、1. に戻る
大きい “泡” ほど速く浮かび上がるように、大きいデータほど速くデータの後ろ側に寄せられていくことから「バブルソート」と呼ばれるようです。
ただ、個人的にはですが、バブルソートだと「ソートアルゴリズム名」と「アルゴリズム自体」がパッと結びつかないので、「バブルソート = 交換法」と覚えた方が良いかなぁと思います。
バブルソートのプログラム
では、ここまで解説してきた「バブルソート」を行うプログラムのソースコードを紹介していきたいと思います。
バブルソートプログラムのソースコード
下記がそのソースコードになります。具体的には、bubbleSort 関数がバブルソートを行う関数になります。
おそらくバブルソートの関数としては、かなり “分かりやすく” 実装されていると思います！
/*
* バブルソートを行う関数
* a：ソートしたいデータを格納した配列
* num：ソートしたいデータの個数
*/
void bubbleSort(int a[], int num) {
int exchange; /* 交換回数 */
int i;
int tmp;
do {
exchange = 0;
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < num - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
/* 交換が行われた回数をカウントアップ */
exchange++;
}
}
} while(exchange > 0); /* 交換が発生している間はソート続ける */
}スポンサーリンク
ソースコードの解説
bubbleSort 関数に関して少し解説をしておきます。
bubbleSort 関数は、ほぼバブルソートの考え方で解説した内容をそのまま実装しているだけのものになります。
ポイントを上げるとすると下記の２つだと思います。
for文でのループ範囲- データの交換
- ソート完了の判断（
whileループの継続条件）
for 文でのループ範囲
bubbleSort 関数における for 文は下記のようになっています。
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < num - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 略 */
}
}i の最大値が num - 2 になっているところがポイントです。
ここで i を num - 1 まで増加するように for 文を組んでしまうと、for 内部での a[i + 1] へのアクセス時に配列の外にアクセスし、アクセス違反が発生することになるので注意してください。
i が num - 2 の時には、a[num - 2] と a[num - 1] の交換が行われるので、 i の最大値が num - 2（つまりデータの最後尾の１つ手前）であっても、最後尾のデータも含めて交換を行うことができます。
データの交換
データの交換は下記で行っています。
/* 隣り合うデータの大小関係を確認 */
if (a[i] < a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
/* 交換が行われた回数をカウントアップ */
exchange++;
}隣り合うデータは a[i] とその１つ後ろのデータ（つまり a[i + 1]）として交換を行なっています。
データの交換を行う場合は、交換を行うデータの一方を一旦退避しておく必要がある点に注意してください（上記では tmp に a[i] を退避させています）。
また、「大小関係が逆」であるかどうかは下記で判断しています。
if (a[i] < a[i + 1]) {上記は “昇順にソートする” 場合の判断になりますが、下記のように変更することで降順にソートすることも可能です。
if (a[i] > a[i + 1]) {ソート完了の判断（while ループの継続条件）
また、バブルソートの考え方でも説明した通り、先頭から最後尾の間の全ての隣り合うデータにおいて、交換が一度も発生しなくなったらソートが完了したことになるので、その時点でソートを終了することができます。
そのため、交換が発生した回数を exchange 変数でカウントするようにし、exchange 変数が 0 の時、つまり、先頭から最後尾の間の全ての隣り合うデータにおいて交換が一度も発生しなかった場合は while ループを抜けてソートを終了するようにしています。
バブルソートの様々な実装
で、おそらく上記の bubbleSort 関数は他のサイトさんが公開されている関数とは異なる実装になっていると思います（私は上記の bubbleSort 関数が一番わかりやすい bubbleSort 関数の実装だとは思っていますが…）。
何が言いたいかというと、アルゴリズムを実現するための実装方法は１つではなく、たくさん存在するということです。
ということで、ここではバブルソートの様々な実装を紹介していきたいと思います。
どの実装方法でもバブルソートは実現できますし、一応全てソートができることは確認しています
ただ、効率の良し悪しやコードの分かりやすさの違いもありますし、例えば課題などでバブルソート関数を実装するような場合は、その課題で求められている実装方法が存在する可能性もあります
その場面場面で、どの実装方法が良いかを判断して使い分けることが重要です！
ソート範囲を考慮して効率アップさせる
先ほどお見せした bubbleSort 関数は非常にシンプルで私は好きなのですが、実はバブルソートの特性を考慮するとちょっと無駄な処理を行ってしまっています…。
前述の通り、バブルソートは「隣り合うデータの大小関係が逆の場合に、その２つのデータを交換する」ことでソートをしていくソートアルゴリズムになります。
で、上記を先頭から最後尾のデータまで繰り返せば、昇順にソートする場合は必ず一番大きいデータが最後尾に移動することになります。
なぜなら、隣り合うデータの “前側のデータ” が一番大きいデータなのであれば、必ず「大小関係が逆」になり、データの交換が行われるからです。
そして、データ交換後は、この一番大きいデータがまた次の隣り合うデータの “前側のデータ” となり、またデータの交換が行われます。
つまり、一番大きいデータは一度交換が行われると、それ以降は毎回交換が行われ、最終的に最後尾のデータとなります。
一番大きいデータが最後尾に移動したということは、その時点で一番大きいデータの位置が確定したことになります。ですので、この時点でソートする範囲をデータ１つ分狭めることができます。
そして、この新たなソート範囲に対して先頭から最後尾のデータに対してデータの交換を繰り返せば、今度はそのソート範囲で一番大きいデータ（つまりデータ全体で２番目に大きいデータ）が、そのソート範囲の最後尾に移動します。
この時点で２番目に大きいデータの位置が確定します。つまり、またソートする範囲をデータ１つ分狭めることができます。
こんな感じで、バブルソートでは先頭から最後尾までのデータの交換が完了した際にソートする範囲を１つ狭めることが可能です。
そして、このソート範囲を狭めることで比較回数を減らすことができるので、ソートの効率が向上します。
上記の説明に基づき、バブルソートプログラムのソースコードで紹介した bubbleSort 関数を、先頭から最後尾までの一連のデータの交換が完了する度に “データ１つ分ソート範囲を狭める” ように変更したものが下記になります。
/*
* バブルソートを行う関数
* a：ソートしたいデータを格納した配列
* num：ソートしたいデータの個数
*/
void bubbleSort(int a[], int num) {
int exchange; /* 交換回数 */
int i;
int tmp;
int size; /* ソート範囲のデータの個数 */
/* 最初はソートする範囲のデータの個数 = 全体のデータの個数 */
size = num;
do {
exchange = 0;
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < size - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
/* 交換が行われた回数をカウントアップ */
exchange++;
}
}
/* ソートする範囲をデータ１つ文狭める */
size--;
} while(exchange > 0); /* 交換が発生している間はソート続ける */
}ソート範囲を終了条件にする
また、ソート範囲のデータ数が 1 になった時点でソートが完了することになるので、その時点でソートを完了させることも可能です。
ソート範囲のデータ数をソートの終了条件とした場合、交換回数 = 0 をソートの終了条件にしなくてもソートを完了させることも可能です。
上記に基づき、ソート範囲を考慮して効率アップさせるで紹介した bubbleSort 関数を、ソート範囲のみを終了条件とするように変更したものは下記のようになります。
void bubbleSort(int a[], int num) {
int i;
int tmp;
int size; /* ソート範囲のデータの個数 */
/* 最初はソートする範囲のデータの個数 = 全体のデータの個数 */
size = num;
do {
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < size - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
}
}
/* ソートする範囲をデータ１つ文狭める */
size--;
} while(size > 1); /* ソートする範囲が1になるまでソートを続ける */
}これもシンプルで分かりやすいですね！
ただ交換が発生しなくなっても（つまりソートが完了しても）、一連の処理が最後まで実行されることになるので、その点は若干非効率です。
また「バブルソートの終了条件 = ソート範囲が 1 になるまで」と説明されることも多く、この場合はこの実装（もしくは次の節で紹介している実装）が期待されている可能性も高いです。
最後に交換したデータまでを次のソート範囲とする
ソート範囲を考慮して効率アップさせるで、データの交換を先頭から最後尾のデータまで繰り返すことで、”必ず” 一番大きいデータの位置が確定すると説明しました（つまり一番大きいデータが最後尾に移動する）。
“必ず” 位置が確定するのは「一番大きいデータ」のみなのですが、それ以外のデータでも、たまたま偶然位置が確定する場合があります。
例えば下図のようなデータをソートすることを考えてみましょう。
この場合、データの交換を先頭から最後尾のデータまで繰り返せば、下図のようにソートが一段階進みます。
見ていただければわかるとおり、最後尾から 6 のデータまでは位置が既に確定していますね！
つまり、6 のデータ以降はソートが完了していると考えることができ、次のソートの範囲（データの交換を行う範囲）は “データの先頭から 6 のデータの１つ前まで” のみで良いことになります。
このように、先頭から最後尾のデータまでデータの交換を繰り返すことで、最後尾から複数のデータの位置が一気に確定することがあります。
なので、ソート範囲を考慮して効率アップさせるで説明したようにソート範囲をデータ１つ分狭めるだけでなく、複数のデータ分狭めることができる場合があります。
じゃあ、実際に “どこからのデータがソートが完了しているか” をどうやって判断すれば良いかというと、これは “最後に交換したデータの位置” から判断できます。より具体的には最後に交換したデータの “後ろ側” の位置以降はソートが完了していると判断できます。
昇順ソートの場合、先頭から順に隣り合うデータの交換を行えば、最後に交換したデータの “後ろ側” の位置に「そこまで交換を行なってきた範囲の中で一番大きいデータ」が来ることになります。
また、その最後の交換以降、一度も交換が発生していないということは、最後に交換したデータ以降のデータにおいては、隣り合うデータの組み合わせ全てで「大小関係が既に整っている」と言えます（交換が発生していないので）。
つまり、最後に交換したデータ以降は既にソート済み、つまりデータの位置が確定していると判断できます。
なので、次のソートの範囲を「前回のソート時の最後に交換したデータの “後ろ側” の位置の１つ前まで」とすることが可能です。
そして、このようにソート範囲を狭めていくことで、ソートの効率をアップさせることが可能です。
上記の説明に基づき、ソート範囲を終了条件にするで紹介した bubbleSort 関数において、次のソート範囲を「前回のソートの時の最後に交換したデータの “後ろ側” の位置の１つ前まで」とするように変更したものが下記となります。
/*
* バブルソートを行う関数
* a：ソートしたいデータを格納した配列
* num：ソートしたいデータの個数
*/
void bubbleSort(int a[], int num) {
int i;
int tmp;
int size; /* ソート範囲のデータの個数 */
int last_exchange; /* 交換したデータの後ろ側の位置*/
/* 最初はソートする範囲のデータの個数 = 全体のデータの個数 */
size = num;
do {
/* 一旦0で初期化 */
last_exchange = 0;
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < size - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
/* 交換時の後ろ側のデータの位置を記憶 */
last_exchange = i + 1;
}
}
/* 最後に交換した後ろの位置以降はソート範囲から省く */
size = last_exchange;
} while(size > 1); /* ソートする範囲が1になるまでソートを続ける */
}while ループを for ループで実現する
あとは do while ループの部分を for ループで実現している実装例を紹介されているサイトさんも多いですね！
ソート範囲を終了条件にするで紹介した bubbleSort 関数の do while ループを for ループに置き換えると下記のようになります。
/*
* バブルソートを行う関数
* a：ソートしたいデータを格納した配列
* num：ソートしたいデータの個数
*/
void bubbleSort(int a[], int num) {
int i;
int tmp;
int size; /* ソート範囲のデータの個数 */
/* ソートする範囲を狭めながらソート */
for (size = num; size > 1; size--) {
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < size - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
}
}
}
}再帰呼び出しを用いる
また、２重ループの形を取らなくても、再帰呼び出しを行ってソートするやり方もあります。
バブルソートプログラムのソースコードで紹介した bubbleSort 関数を、再帰呼び出しを用いて実現したものが下記になります。
/*
* バブルソートを行う関数
* a：ソートしたいデータを格納した配列
* num：ソートしたいデータの個数
*/
void bubbleSort(int a[], int num) {
int exchange; /* 交換回数 */
int i;
int tmp;
exchange = 0;
/* 先頭のデータから最後尾の１つ手前のデータまでループ */
for (i = 0; i < num - 1; i++) {
/* 隣り合うデータの大小関係を確認 */
if (a[i] > a[i + 1]) {
/* 大小関係が逆なら２つのデータを交換 */
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
/* 交換が行われた回数をカウントアップ */
exchange++;
}
}
if (exchange > 0) {
/* 交換が発生している間はソート続ける */
bubbleSort(a, num);
}
}まとめ
このページでは、ソートアルゴリズムの１つである「バブルソート」について解説しました。
バブルソートとは、下記のように処理を行うことでソートを行うアルゴリズムになります。
- 下記をデータの集合の先頭から最後尾まで１つずつデータをずらしながら繰り返し行う
- 隣り合うデータの大小関係を比較する
- 大小関係が逆の場合：その２つのデータを交換する
- 隣り合うデータの大小関係を比較する
- 一度でも交換が行われたのであれば、1. に戻る
要は「隣り合うデータの大小関係が逆の場合に、その２つのデータを交換する」を繰り返すことでデータをソートするアルゴリズムになります。
このページでも紹介したように実装自体は非常に簡単に行うことができます。
また様々な方法で実装したバブルソート関数を紹介することで、一つのアルゴリズムを実現するにもいろんな実装が存在することも実感していただけたのでは無いかと思います！
ソートアルゴリズムにはこのバブルソート以外にも様々なものが存在し、本サイトでは、バブルソート以外にも下記のソートについても解説しています。
- クイックソート
- マージソート
- 選択ソート
- 挿入ソート
- ヒープソート
下記リンク先でそれぞれについて解説していますので、他のソートアルゴリズムにも興味のある方は是非こちらも読んでみてください！
クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
挿入ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
ヒープソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
