簡単な並べ替え(バブルソート)

整列という操作は、与えられたデータをある規則にしたがって並べ替えることを言う。 ソーティング(sorting)とも呼ばれる。

整列の例としては次のようなものがある。

最後の並べ替えの規則は何だろうか？ :-)

整列を行うための方法には、様々なものが考案されている。 簡単で代表的なものとして、ここではバブルソートを取り上げる。

バブルソートは、未整列の列を左から順に隣り合った２つのデータを比較し、 順序が間違っていたら、交換を行うことで、整列を行う。 次に、上で扱った５つの数値データを昇順に並べ替える手続きを、 バブルソートで整列するのを見てみよう。 "|" は未整列と整列済みのデータの境界を示すものとする。

上のデータの変遷を見ると、未整列のデータの中での最大値が順に右に移動していく様子がわかる。 そのため、水の中の泡が浮いていくのに例えられ、バブルソートと呼ぶ。

バブルソートを C 言語の関数として表現した例を次に示す。 データは配列 a に、データ数は nとして渡されることとしよう。

int bubble_sort(int a[], int n) {
        int i, data, tmp;
	/* data: 整列する必要があるデータ数。 */
        for (data = n; data > 1; --data) {
	        /* i: 現在比較中のデータペアの左側を示す */
                for (i = 0; i < data - 1; ++i) {
		        /* 比較 */
                        if (a[i] > a[i+1]) {
		            /* 間違っていたので交換 */
                                tmp = a[i];
                                a[i] = a[i+1];
                                a[i+1] = tmp;
                        }
                }
        }
        return 0;
}
  

変数の値を交換するためには、一度値を退避しておく変数が必要であることを忘れると データが破壊されてしまうので注意が必要である。

バブルソートは 単純ではあるがデータ数が大きくなると急激に遅くなるアルゴリズムである。 それは、上記のプログラムの中で、比較が行われる回数を考えると良く分かる。 最初の for ループでは data変数が n から 2 まで変化していく。 内側の for ループでは 1 から data -1 まで変化する。 従って交換が行われる回数は

となる。 したがって、バブルソートの処理速度はデータ数の2乗したものに、ほぼ比例することになる。 つまり、データ数が2倍になれば、処理速度は4倍に、データ数が10倍になれば処理速度は100倍になることになる。

もどる