ALDS1_2_A:

バブルソート

バブルソートでは、挿入ソートと同様に、各計算ステップにおいて、配列は「ソート済みの部分列」と「未ソートの部分列」とに分けられます。

順番が逆になっている隣接要素がなくなるまで、次の処理を繰り返す：

• 配列の末尾から隣接する要素を順番に比べていき、大小関係が逆ならば交換する。

例えば、配列 ${5, 3, 2, 4, 1}$に対してバブルソートを行うと以下のようになります。

このバブルソートのアルゴリズムでは、ソート済みのデータが配列の先頭から順番に決定します。例では、1. から4. の処理が終了すると、データの中で一番小さい要素が配列の先頭 A[0] に移動します。以下同様に、5. から7. が終了すると、2 番目に小さい要素が A[1] に移動し、8. から9.、10. でそれぞれソート済みの部分列の末尾に追加されるデータが順番に決まっていきます。

この例から分かるように、外側のループが１回終了するごとに、ソート済みの要素が増えていきます。従って外側のループは最大でもN回実行され、内側のループ処理の範囲は狭くなっていきます。このことから、バブルソートのアルゴリズムは、外側のループ変数iを用いて次のように実装することができます。

1 bubbleSort()
2   flag = 1
3   i = 0 // 未ソート部分列の先頭インデックス
4   while flag
5     flag = 0
6     for j = N-1 から i+1 まで
7       if A[j] < A[j-1]
8         A[j] と A[j-1] を交換
9         flag = 1
10    i++

このバブルソートの実装に必要な主な変数は以下のようになります。

バブルソートは、配列要素の隣同士のみを比較・交換するので、要素のキーが同じだった場合、それらの順番が入れ替わることはありません。従ってバブルソートは安定なソートです。ただし隣同士を比較する 演算A[j] < A[j-1] に等号を入れて A[j] <= A[j-1] としてしまうと安定ではなくなるので注意が必要です。

バブルソートの計算量を考えてみましょう。データの数を $N$とすると、バブルソートは未ソートの部分列における隣どうしの比較を $N-1$ 回、$N-2$ 回、$... 1$ 回の合計 $(N^2-N)/2$ 回行います。これは最悪の場合は、$(N^2-N)/2$ 回の比較演算が行われるため、オーダーが $O(N^2)$ のアルゴリズムとなります。

ちなみに、バブルソートの交換回数は反転数または転倒数と呼ばれるもので、列の乱れの具合を表す数値として知られています。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。