ALDS1_2_A:

バブルソート

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

バブルソート

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

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

たとえば、配列 $A = [16, 4, 2, 8, 1]$ に対してバブルソートを行うと以下のようになります。

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

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

$A$	サイズが $N$ の整数型配列。
$i$	未ソートの部分の先頭を指すループ変数で、配列の先頭から末尾に向かって移動します。
$j$	未ソートの部分の隣り合う要素を比較するためのループ変数で、$A$の末尾である $N-1$ から開始し $i+1$ まで減少します。

これらの変数とループ変数を用いたバルブソートの実装には、いつかのバリエーションが考えられます。

まず、問題文に記載のコードを改善することを考えます。このコードでは、毎回 $j$を 1 まで減らしています。バブルソートでは、外側のループが１回終了するごとに、ソート済みの要素が増えていきます。従って、内側のループ処理の範囲は狭くなっていきます。このことから、バブルソートのアルゴリズムは、外側のループ変数 $i$ を導入して次のように実装することができます。

# 要素数 N の配列 A の要素を昇順に整列する
def bubble_sort(N, A):
    updated = True
    i = 0
    while updated:
        updated = False
        for j in range(N - 1, i, -1): # j を N-1 から i+1 まで回す
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j] # A[j] と A[j-1] を交換する
                updated = True

また、for文による二重ループで以下のように実装できます。

def bubble_sort(N, A):
    for i in range(N - 1):
        for j in range(N - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]

$i$ を導入した実装では、$i$ のループの回が終了すると、未ソート部分の中で一番小さい要素が $A[i]$ に移動し、ソート済みの部分列の末尾に追加されるデータが順番に決まっていきます。

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

Reference

---