では、前に開示しましたコードを使って4つのソートアルゴリズムを確認してゆきましょう。
矢張り最初に登場願うのは最もストレートなソートアルゴリズムである「バブルソート」でしょう。詳しくお知りになりたい方はリンクのwikiの説明もご覧ください。
////////////////
// Bubble Sort
////////////////
/*
n個の整数配列dataを総て順に比較、交換し、配列の最後から大きい順に並べる
通称「馬鹿ソート」
*/
void bubblesort(int* data, int n) {
int i, j, temp;
for(i = n - 1; i > 0; i--) { //配列の末尾から先頭へ
for(j = 0; j < i; j++) { //配列の先頭から末尾へ
if(data[j] > data[j + 1]) { //次の配列要素の方が小さければ交換する
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
} //その結果iに最大の要素が置かれる
}
}
上のコードを使って簡単に説明するとすれば、この方法は「dataという場所に並んでいる、n人の選手(整数)の勝ち抜き戦をn - 1回(最後は一人になるので相手がいない為)行う」方法と言えます。
より具体的に見てみましょう。簡単な例として
配列 = {2, 7, 3, 5, 4, 0, 6, 1, 8};
要素数 9
を想定します。
1.外側のループ
先ずインデックスiの初期値はn - 1(= 8)で、0から始まる配列の最後(data[n - 1]、値は8) を指します。
2.内側のループ
インデックスjが0からiの指す最後の手前まで、即ち配列data[0](値は2)から始め、順に次の配列(data[j + 1])の値と比較し、手前が大きければ次と交換して行きます。
配列 = {2, 3, 5, 4, 0, 6, 1, 7, 8}; (解説:交換で移動させられた値は橙、最後の最大値は赤で表します。)
偶々最後のdata[8]が8だったので、交換はされませんでしたが、一番大きな値の8が最後に置かれました。
3.外側のループ
インデックスiは配列最後の8の手前の7を指します。
4.内側のループ
インデックスjが又0からiの指す最後の手前まで、即ち配列data[0](値は2)から始めて比較と必要に応じて交換を行います。
配列 = {2, 3, 4, 0, 5, 1, 6, 7, 8}; (解説:↑の通り。なお確定値は青で示します。)
5.外側のループ
インデックスiは配列最後の二つ手前の6を指します。
6.内側のループ
インデックスjが又0からiの指す最後の手前まで比較と必要に応じて交換を行います。
配列 = {2, 3, 0, 4, 1, 5, 6, 7, 8};
7.外側のループ
インデックスiは配列最後の三つ手前の5を指します。
8.内側のループ
インデックスjが2から始めて
配列 = {2, 0, 3, 1, 4, 5, 6, 7, 8};
9.外側のループ
インデックスiは配列最後の四つ手前の4を指します。
10.内側のループ
インデックスjが2から始めて比較と必要に応じて交換を行います。
配列 = {0, 2, 1, 3, 4, 5, 6, 7, 8};
11.外側のループ
インデックスiは配列最後の五つ手前の3を指します。
12.内側のループ
インデックスjが2から始めて同様に処理します。
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
13.外側のループ
外側のインデックスがdata[2](値は2)、data[1](値は1)を指しますが、交換無しで終了します。
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
いかがでしょうか?具体的な例でプログラムが何をやっているかをトレースしてみるとよくその動作が分かるかと思います。(解説:デバッガーがやることをハンドでバッギングしている、ということです。)
この方法がバブルソートと呼ばれるのは、配列中の大きな値が最後の方へ運ばれる様子が「泡が上がってくる様子」と似ているからと言われます。しかし、この方法は比較や交換の回数が多くなり、他のソートアルゴリズム(解法)よりも遅いという難点があります。次の前に開示したコードの実行例は他のソートアルゴリズムが1万個の整数配列のソートに殆ど時間を要していないのに、バブルソートだけは95/10,000秒時間がかかったことを示しています。
次回はより速いソートアルゴリズムであるヒープソートを見て行きましょう。




