C言語のバブルソートの実装方法、4選: 比較関数、番兵を使った高速化等
- 作成日: 2021-09-15
- 更新日: 2023-12-26
- カテゴリ: C言語
C言語でバブルソート（単純交換法）を実装する
この記事ではC言語によるバブルソート（単純交換法）の実装について取り上げます。
また、バブルソートについて基本的なことがらを解説したいと思います。
実装では基本的な実装、それからスワップ・フラグを使った実装、番兵を使い高速化を行った実装、比較関数による実装を取り上げます。
具体的には↓の項目を見ていきます。
- バブルソートはソートアルゴリズムの一種です
- バブルソートの発明者は？
- バブルソートは本当に非実用的なのか？
- バブルソートは嫌われ者なのか？
- バブルソートは仕事で使ってもいいものか？
- バブルソートはなぜ学ぶ必要があるのか？
- バブルソートはどんな時に使われるのか？
- バブルソートはどんなアルゴリズムか？
- バブルソートで使われるスワップはどんな技術か？
- C言語によるバブルソートの実装方法
- バブルソートの次に何を学ぶべきか？
実装だけ見たい方は「C言語によるバブルソートの実装方法」をご覧ください。
🦝 < バブルソートの世界へようソロ
関連記事
Bashでバブルソートを実装する: 番兵を使って効率化
バブルソートはソートアルゴリズムの一種です
バブルソートとはいったいなんなのか？ というところですが、結論から言うとバブルソートはソートアルゴリズムの一種です。
「アルゴリズム」とは問題を解決する手順のことを指します。
そして「ソート」とは複数あるオブジェクトを並べ替えるアルゴリズムのことを指します。
バブルソートはそのソートされるさまがバブル（泡）のように見えることからバブルソートと命名されたと言われています。
🐭 < バブルなやつなんだね
実用的なクイックソート、非実用的なバブルソート
ソートアルゴリズムで実用的なソートとして知られているのがクイックソートです。
これは非常に速いソートで、さまざまな言語、ライブラリで用いられています。
いっぽう、クイックソートと対称的なのがバブルソートです。
バブルソートは非常に動作が遅く、非実用的なソートアルゴリズムとしてよく知られています。
できるクイックソートと比べて出来ないのがバブルソートです。
秀才で足が速いのがクイックソートで、勉強が出来なくて足が遅いのがバブルソートです。
バブルソートは実装が簡単
欠点だらけのバブルソートと思われがちですが、もちろん利点もあります。
その利点が実装がしやすいという利点です。
バブルソートのアルゴリズムは非常に単純なため、直感的でわかりやすいのです。
そのためソートの学習用途などに使われることが多々あります。
バブルソートの発明者は？
バブルソートを発明した人は誰なのでしょうか？
残念ながらバブルソートの発明者は不明です。
非常に単純なアルゴリズムのため、発明者と呼ばれる人がいないのが現状なのかもしれません。
🦝 < 自然発生的なアルゴリズムなのね
バブルソートは本当に非実用的なのか？
バブルソートは本当に非実用的なのでしょうか？
実用的な部分はないのでしょうか？
バブルソートをソフトウェアの実装に組み込むのは？
まとめると↓になります。
- バブルソートの最悪計算時間はO(n2)
- O(n2)はどれぐらいの遅さか？
- 実装が簡単なので使いやすいことは使いやすい
バブルソートの最悪計算時間はO(n^2)
バブルソートの計算時間は↓のようになっています。
- 最悪計算時間 ... O(n^2)
- 最良計算時間 ... O(n)
- 平均計算時間 ... O(n^2)
- 最悪空間計算量 ... O(1) auxiliary
注目してもらいたいのが最悪計算時間です。
これはO(n^2)になっています。
このO(n^2)はどれぐらいの遅さなのでしょうか？
O(n^2)はどれぐらいの遅さか？
O(n^2)はどれぐらいの計算量かと言うと、二重のfor文が総当たりで回るぐらいの遅さです。
行列を描画するときに二重のfor文を使うと思いますが、行列の要素を1つずつ描画していく感覚を持ってもらうとわかりやすいかもしれません。
たとえば10 x 10の行列であればその要素数はぜんぶで100になります。
つまり100個の要素を描画する遅さです。
ソートするデータ量が100個の場合、その最悪計算時間は10000個分になるということです。
こう考えるとどれぐらいO(n^2)が遅いのかわかりますね。
実装が簡単なので使いやすいことは使いやすい
バブルソートは確かに遅いのですが、実装が簡単なため使いやすいことは使いやすいです。
速度が必要とされる場面では非実用的なソートアルゴリズムですが、それ以外のケースでは使われることもあります。
ただボトルネックになりやすいアルゴリズムのため、実装に使う場合は他のソートアルゴリズムと交換できるように工夫しておく必要があります。
バブルソートは嫌われ者なのか？
バブルソートは嫌われているのでしょうか？
遅い、非実用的、作者不明と嫌われる要素はたくさん持っていますが、じっさいのところどうなのでしょうか？
とんでもない、それは誤解です
バブルソートが嫌われているという認識は大きな誤解です。
バブルソートは確かにデメリットの多いソートアルゴリズムですが、実装が簡単で安定したソートとしてたくさんの人から好かれているアルゴリズムと言っていいでしょう。
バブルソートは遅いですが実装が簡単で使いやすく、取り回しが容易です。
みんなから愛されているソートアルゴリズム
バブルソートほどたくさんの人に認知され利用されているアルゴリズムはなかなか無いでしょう。
バブルソートは大学の教材などにも利用されるし、しばしばプログラマーの仕事にも使われます。
まさにみんなから愛されているソートアルゴリズムと言ってもいいのがバブルソートです。
バブルソートは仕事で使ってもいいものか？
バブルソートは実用性に疑問点がついていますが、プログラマーの仕事に使われることはあるのか？
使っても良いものなのか？ というところですが、これは使い方によります。
ベタ書きのバブルソートはリプレースが大変
たとえばバブルソートのアルゴリズムをソースコードにベタ書きするとどうなるでしょうか。
そのベタ書きの部分でボトルネックなどが発生した場合に書き直すのが困難になる可能性があります。
そのためバブルソートのアルゴリズムのベタ書きは控えたほうが良いと言えます。
仕事で使うならAPIを定義しよう
仕事で使う場合は、バブルソートの専用を関数を作ってAPIを定義しましょう。
そうすればボトルネックが発生したときにその関数の呼び出し部分をリプレースすれば取り換えできます。
こうしておくとバブルソートを使っても安心です。
バブルソートはなぜ学ぶ必要があるのか？
実用性に疑問符が付いているバブルソートですが、なぜ我々はバブルソートを学ぶ必要があるのでしょうか？
クイックソートなどもっと実用的なソートアルゴリズムを学んだ方が良いのでは？
たしかにクイックソートなどの実用的なソートを学ぶのは大事ですが、バブルソートにはバブルソートの利点があります。
ソートの基本的アルゴリズムとして学ぶ
バブルソートはソートの基本的アルゴリズム、ソートの基礎として学ぶのにうってつけのアルゴリズムです。
そのため学習用途のアルゴリズムとして適しています。
実装が簡単なため、短時間でソートの概要について学ぶことができるし、なんならアルゴリズムの暗記も可能です。
それぐらいコンパクトなアルゴリズムなので、勉強に最適と言うことです。
学習のハードルが低いためアルゴリズム入門の定番
バブルソートはコンパクトなので、学習のハードルが低く、アルゴリズムの入門として適しています。
クイックソートなどは複雑なアルゴリズムのため学習が難しいですが、バブルソートであれば単純なため学習が容易です。
そのためアルゴリズム入門用のアルゴリズムとしても最適というわけです。
バブルソートはどんな時に使われるのか？
バブルソートはどんなときに使われるのでしょうか？
バブルソートの実用範囲は？
バブルソートを使えるシーンはどんな時？
まとめると↓2つです。
- 入社試験や面接でのコーディングの出題として
- 速度を必要としない場面で使う
入社試験や面接でのコーディングの出題として
バブルソートはコンパクトなアルゴリズムで、書こうと思えばすぐに書くことができるため入社試験や面接の出題などでたびたび出されることがあります。
筆者もプロジェクトの面接でバブルソートを実装してみてほしいと言われ、実装した思い出があります。
🦝 < ちなみにその面接には受かりました
アルゴリズムに対する認識があるかどうか、という点を問うのにバブルソートは向いています。
アルゴリズムを学んだことがある人なら必ず実装するであろう基礎的なアルゴリズムだからです。
速度を必要としない場面で使う
あとは速度を必要としない場面で使われることがあります。
バブルソートはとにかく遅いです。そのため大量のデータ処理には向いていません。
しかしデータ量が少なくて、それほど頻繁に呼ばれることがない処理では使われることもあるアルゴリズムです。
ソートも安定しているので安心して使うことができるのも特徴です。
バブルソートはどんなアルゴリズムか？
バブルソートのアルゴリズムは単純です。
たとえば配列aryがあったとします。
この配列を外側のforループで回します。
そして内側にもforループを作ってaryの要素数-1だけ回します。
そして内側のforループで隣り合う要素を比較し、比較が真であれば、つまりどちらかが小さければ（大きければ）その隣り合う要素を交換（スワップ）します。
内側のfor文では先頭から末尾までこのスワップを繰り返します。
そして外側のfor文が終わるまでループを回します。
内側のfor文でスワップが発生しなければ、その配列はすでに整列が完了しているということになります。
そのためこの特徴を利用して最適化することも出来ます。
また、バブルソートは配列の末尾から要素が整列されていく特徴があるため、番兵を使って末尾の要素の比較をスキップして高速化することも可能です。
バブルソートで使われるスワップはどんな技術か？
バブルソートでは「スワップ」という技術を使います。
スワップとは2つの値をたがいに「交換する」技術のことを言います。
たとえばC言語ならスワップは↓のようなものです。
int a = 1, b = 2;
// aとbの値をスワップする
int tmp = a;
a = b;
b = tmp;
printf("a[%d] b[%d]\n", a, b);
// a[2] b[1]
C言語によるバブルソートの実装方法
それではC言語によるバブルソートの実装を見てみたいと思います。
基本的なバブルソート
まずは基本的なバブルソートからです。
なんの最適化もほどこしていない、もっとも原始的なバブルソートです。
#include <stdio.h>
/**
* 原始的なバブルソートを実行する
*
* @param[in|out] ary 配列
* @param[in] arylen 配列の長さ
*/
void bubble_sort(int *ary, int arylen) {
// 外側のfor文
for (int i = 0; i < arylen - 1; i += 1) {
// 内側のfor文
for (int j = 0; j < arylen - 1; j += 1) {
// 隣り合う要素同士を比較
if (ary[j] > ary[j + 1]) {
// スワップの実行
int tmp = ary[j];
ary[j] = ary[j + 1];
ary[j + 1] = tmp;
}
}
}
}
int main(void) {
int ary[] = {4, 2, 3, 1}; // ソート対象のint型の配列
int arylen = sizeof(ary) / sizeof(ary[0]); // 配列の長さ
bubble_sort(ary, arylen); // バブルソートの実行
// バブルソートの結果を出力
for (int i = 0; i < arylen; i += 1) {
printf("%d ", ary[i]);
}
puts("");
return 0;
}
↑のコードをコンパイルして実行すると↓のように出力されます。
1 2 3 4
これは昇順（小さい順）のソートになります。
bubble_sort()内のif文である↓の部分、
// 隣り合う要素同士を比較
if (ary[j] > ary[j + 1])
この比較演算子（>）を変えると昇順と降順を変えることができます。
ためしに比較演算子を<にしてみてください。
ソートの結果は降順（大きい順）になるはずです。
このバブルソートでもソートは可能ですが、一部に無駄があり、まだ効率化が可能です。
スワップ・フラグによる最適化
「スワップ・フラグ」を使うとバブルソートを効率化することができます。
スワップ・フラグはスワップが発生した場合にtrueになるフラグです。
スワップが発生している状態は、まだ配列は整列されていない状態です。
しかしスワップが発生していない状態はすでに配列が整列されている状態です。
そのためスワップ・フラグがfalseの場合は外側のループから抜けることができます。
#include <stdio.h>
#include <stdbool.h>
/**
* スワップ・フラグを使ったバブルソートを実行する
*
* @param[in|out] ary 配列
* @param[in] arylen 配列の長さ
*/
void bubble_sort(int *ary, int arylen) {
bool swapped; // スワップしたかどうかのフラグ
for (int i = 0; i < arylen - 1; i += 1) {
swapped = false; // フラグを折っておく
for (int j = 0; j < arylen - 1; j += 1) {
if (ary[j] > ary[j + 1]) {
int tmp = ary[j];
ary[j] = ary[j + 1];
ary[j + 1] = tmp;
swapped = true; // フラグを立てる
}
}
// フラグが折れたままならスワップが発生していないということになる
// 「スワップが発生していない＝整列されている」ということ
// その場合はループから抜ける
if (!swapped) {
break;
}
}
}
int main(void) {
int ary[] = {4, 2, 3, 1}; // ソート対象のint型の配列
int arylen = sizeof(ary) / sizeof(ary[0]); // 配列の長さ
bubble_sort(ary, arylen); // バブルソートの実行
// バブルソートの結果を出力
for (int i = 0; i < arylen; i += 1) {
printf("%d ", ary[i]);
}
puts("");
return 0;
}
番兵を使ったバブルソート
外側のfor文のカウント変数iは内側のfor文の番兵として使うことができます。
番兵を使うことでさらにバブルソートの効率化が可能です。
ここまで最適化するとコンプリートなバブルソートという感じになります。
#include <stdio.h>
#include <stdbool.h>
/**
* 番兵を使ったバブルソートを実行する
*
* @param[in|out] ary 配列
* @param[in] arylen 配列の長さ
*/
void bubble_sort(int *ary, int arylen) {
bool swapped;
for (int i = 0; i < arylen - 1; i += 1) {
swapped = false;
// arylen - i - 1 でiを番兵にする
for (int j = 0; j < arylen - i - 1; j += 1) {
if (ary[j] > ary[j + 1]) {
int tmp = ary[j];
ary[j] = ary[j + 1];
ary[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
int main(void) {
int ary[] = {4, 2, 3, 1}; // ソート対象のint型の配列
int arylen = sizeof(ary) / sizeof(ary[0]); // 配列の長さ
bubble_sort(ary, arylen); // バブルソートの実行
// バブルソートの結果を出力
for (int i = 0; i < arylen; i += 1) {
printf("%d ", ary[i]);
}
puts("");
return 0;
}
比較関数を使ったバブルソート
隣り合う要素の比較をソート関数の外に出せれば、ユーザーが自由に要素の比較を行うことができます。
要素の比較を自由に行えるということは、降順と昇順のソートをユーザーが切り替えられるということです（比較演算子を切り替えればいいため）。
そういったソート関数の設計をしたい場合は、↓にように関数ポインタを使って比較関数を渡せるようにします。
↓のcompare()というのが比較関数です。
#include <stdio.h>
#include <stdbool.h>
/**
* 比較関数を使ったバブルソートを実行する
*
* @param[in|out] ary 配列
* @param[in] arylen 配列の長さ
*/
void bubble_sort(int *ary, int arylen, bool (*compare)(int, int)) {
bool swapped;
for (int i = 0; i < arylen - 1; i += 1) {
swapped = false;
for (int j = 0; j < arylen - i - 1; j += 1) {
// 比較関数（compare）を使って条件分岐する
if (compare(ary[j], ary[j + 1])) {
int tmp = ary[j];
ary[j] = ary[j + 1];
ary[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
/**
* バブルソートで使われる比較関数
*
* @param[in] left 左の要素
* @param[in] right 右の要素
*/
bool my_compare(int left, int right) {
return left > right;
}
int main(void) {
int ary[] = {4, 2, 3, 1}; // ソート対象のint型の配列
int arylen = sizeof(ary) / sizeof(ary[0]); // 配列の長さ
bubble_sort(ary, arylen, my_compare); // 比較関数を渡してバブルソートの実行
// バブルソートの結果を出力
for (int i = 0; i < arylen; i += 1) {
printf("%d ", ary[i]);
}
puts("");
return 0;
}
↑の場合、my_compare()という関数内の比較演算子を切り替えれば、昇順と降順を切り替えることができます。
バブルソートの次に何を学ぶべきか？
バブルソートの次は何を学ぶべきでしょうか？
ソートアルゴリズムはいろいろありますが、クイックソートについて学ぶといいかもしれません。
バブルソートの次はクイックソートを学ぼう
クイックソートは実用的なバブルソートでソートアルゴリズム界のスーパースターです。
このアルゴリズムについて学べばさらにソートについて理解を深めることが可能になるでしょう。
ソートのアルゴリズムは奥が深い
ソートは配列などの要素を並べ替えるだけのアルゴリズムですが、その奥は深く、さまざまな手法が考案されています。
マージソートや、コムソート、挿入ソートにスリープソートなど。
ソートアルゴリズムにはまればアルゴリズムに関してより一層詳しくなれること間違いなしですね。
おわりに
今回はC言語によるバブルソートの実装について解説しました。
バブルソートと一言で言ってもバリエーションがあり、また実装もお手軽なので試しやすく親しみのあるソートと言えます。
バブルソートは丸暗記もいけるコンパクトさなので、ぜひ丸暗記をおすすめします。
きっと役に立つ日が来ます。
🦝 < バブルソートで並べ替えよう
🐭 < 1億件のデータお願い！
🦝 < あ、パスします