バブルソート

はじめに

活躍したところを見たことがないバブルさん。
これこそ「THE メモ」

バブルソートさんの特徴としては以下です。

• 遅い
• 安定(同順位のものの順序関係が保たれる)
• 最悪の場合計算量は
• 特に長所がない

泡が水面に上がっていくように一つ一つポコポコとソートしていくことからバブルソート。ですねー。

アルゴリズム

配列の先頭から順番に見ていき、隣通しを比較して自分のほうが大きい(小さい)場合は位置を交換します。
これを配列の最後まで行います。
最後まで行ったらまた先頭から同じことを行っていき、位置の交換が一度も起こらなくなったら終了です。

コードにしてみる

#!/etc/bin/env python
# -*- coding: utf-8 -*-
import numpy as np

def sort(vals, asc=True):
  vals = vals.copy()
  while True:
    cnt = 0
    for i in range(len(vals) - 1):
      if (asc and vals[i] > vals[i + 1]) or (not asc and vals[i] < vals[i + 1]):
        swap(vals, i, i + 1)
        cnt += 1
    if cnt == 0:
      break
  return vals

def swap(vals, x, y):
  vals[y] = vals[x] - vals[y]
  vals[x] -= vals[y]
  vals[y] += vals[x]

こちらを実行してみると、

a = np.random.randint(0, 100, 10)
print(a)
print(sort(a))
print(sort(a, asc=False))
>>>[72 91 75 45 43  5 61  0 31  9]
>>>[ 0  5  9 31 43 45 61 72 75 91]
>>>[91 75 72 61 45 43 31  9  5  0]

となります。

計算量について

とくに何も考える必要はなくシンプルです。
長さ$ n $の配列に関して、whiteループ1回の間に$ n $回の比較を行います。
最悪ケース(昇順を求めたいのに降順に並んでいる、またはその逆)の場合whileループは$ n $回実行されます。
よって、計算量は$ O(n^{2})となります。

これではあまりに非効率

上のコードなのですが、毎回配列の端から端まで比較を行っているのでは非効率的です。
バブルソートはその手法上、whileループ1順で最低でも1つの要素がソートされるべき位置まで移動します。

上の例では、6(最大値)の移動は完了します。
また、この次のループでは5の移動が完了というように、順々に確定することができます。

さらにこの考えを進めると、 バブルソートでは交換が発生した最後の要素は、その場所で確定でき、次のループでは比較を行う必要がなくなります。

これをコードにしてみます

#!/etc/bin/env python
# -*- coding: utf-8 -*-
import numpy as np

def sort(vals, asc=True):
  vals = vals.copy()
  k = len(vals) - 1
  while k >= 0:
    j = -1
    for i in range(k):
      if (asc and vals[i] > vals[i + 1]) or (not asc and vals[i] < vals[i + 1]):
        swap(vals, i, i + 1)
        j = i - 1
    k = j
  return vals

def swap(vals, x, y):
  vals[y] = vals[x] - vals[y]
  vals[x] -= vals[y]
  vals[y] += vals[x]

あんまり変わっていませんが、一応さっきよりは効率的にはなっています。さっきよりは。。

計算量について

上のコードの場合でも、最悪ケースになるのは、ソートしたい順序と逆になっている場合です。 (昇順にしたいのに降順、またはその逆)

その場合、長さ$ n $の配列の比較回数は、$ n - 1, n - 2, \dots, 1 $となるので、 $$ \begin{eqnarray} \begin{split} & (n - 1) + (n - 2) + \dots + 2 + 1 \\ &= \bigl((n - 1) + 1\bigr) \frac{n - 1}{2} \\ &= \frac{n^2 - n}{2} \end{split} \end{eqnarray} $$ これより、結局計算量は変わらず、$ O(n^2) $となります。

おわりに

工夫してもバブルたんはバブルたん。
出番ありませんが有名。ということでメモっておきます。