ビーズソート

ビーズソートまたは重力ソートとはJoshua J. Arulanandham、Cristian S. Calude、Michael J. Dinneenの3人によって2002年に発見されたソートアルゴリズムである。ヨーロッパ理論計算機科学会で発表された。ソフトウェアでの実装でも、ハードウェアでの実装でも時間計算量はO(n)であるが、特にソフトウェアでの実装では時間がかかることがあり、負の数のソートには使えないという欠点も持つ。また、少なくともこのアルゴリズムは空間計算量がO(n²)である。

アルゴリズムの概要

ビーズソートの処理は、平行に並べられた糸をビーズが滑り落ちる様子で理解できる。図のステップ1では、n=5行m=4列の糸を考える。下からn行目はn個目のデータを格納する場所であり、1行目と2行目に3つずつビーズがあるため、1個目と2個目のデータが3であることを表している。^[1]

ここでビーズを重力に従って落下させると、それぞれの行の値がソート後の値となる。1行目は最大の数であり、n行目が最小の数である。もし上記の脚注通り左詰めでビーズを入れた場合、ビーズの右端の位置でソートの結果がわかる。

ハードウェアでの実装において、ビーズを「落下させる」ことを可能にする動作は、より高い行からより大きな値をより低い行に伝播させることを可能にした。 a行目の値がa+1行目の値よりも小さい場合、a+1行目の一部のビーズはa行目まで落下する。a行目のビーズが存在している場所はa+1行目のビーズの落下を物理的に邪魔するため、自動的に値が入れ替わる。

ビーズソートのメカニズムは計数ソートの背景にあるメカニズムと似ており、それぞれの行に存在するビーズの数は、その段数以上の値を持つ要素の数に対応する。

計算複雑性

ビーズソートは、計算複雑性が異なる4種類の実装が可能である。

O(1): ビーズは落下距離にかかわらず単位時間で落下するとするモデル。実際には実装できない抽象化されたビーズソートである。
O( ${\sqrt {n}}$ ): 重力を用いる物理モデル。落下距離は時間の2乗に比例するため、落下時間はデータの数の平方根に比例する。
O(n): ビーズが等速で移動するモデル。ソフトウェアでの実装では、下にビーズがあるかを確認するため、この時間計算量が相当する。
O(S): Sはビーズの総数であり、ソフトウェアでの実装では、各ビーズに対して落下可能かを確認する効率的なアルゴリズムが存在しない場合、この計算量となる。

鳩の巣ソートのように、ビーズソートの最悪計算量がO(nlog)を下回る点で珍しく、最良計算量は比較ソートの最悪計算量である。ビーズソートの要素は非負整数であり、その制約を利用するため、このような高速なソートが可能である。

実装例

Pythonでの実装例を以下に示す。ビーズの「落下」は少し異なる実装である。

def Gravity(obj):
    if all([type(x) == int and x >= 0 for x in obj]):
        reference = [range(x) for x in obj]
    else:
        raise ValueError("入力は正の整数である必要があります")

    intermediate = []
    index = 0
    previous = sum([1 for x in reference if len(x) > index])

    while previous:
        intermediate.append(range(previous))
        index += 1
        previous = sum([1 for x in reference if len(x) > index])

    index = 0
    previous = sum([1 for x in intermediate if len(x) > index])
    out = []

    while previous:
        out.append(previous)
        index += 1
        previous = sum([1 for x in intermediate if len(x) > index])

    out = out[::-1]
    return out

"""how it does it: it counts the "beads" in each column, then uses those numbers to make a new set of rows.
Adding up the beads in each column after turning the initial sums into the new rows gives the backwards
version of the sorted list, which is then turned around using list slicing.
If you believe you understand how the code does it and think you can describe it better, feel free to edit
this description.
Note: 0を含むと、 prev が0となり、while文が止まってしまう可能性がある"""
# contributed by an amateur programmer. Feel free to test & use it.

参考文献・注釈

^ 慣例では、kを表す時、1本目からk本目の糸にビーズを通し、k+1本目からm本目までは空にする。必須要件ではないが、実装上このようにするとわかりやすい。

外部リンク

Bead Sort in MGS, a visualization of a bead sort implemented in the MGS programming language
Bead Sort on MathWorld

[rowconventions-1] 慣例では、kを表す時、1本目からk本目の糸にビーズを通し、k+1本目からm本目までは空にする。必須要件ではないが、実装上このようにするとわかりやすい。

[1]