ビーズソート

ビーズソートまたは重力ソートとはJoshua J. Arulanandham、Cristian S. Calude、Michael J. Dinneenの3人によって2002年に発見されたソートアルゴリズムである。ヨーロッパ理論計算機科学会で発表された。ソフトウェアでの実装でも、ハードウェアでの実装でも時間計算量は"O"("n")であるが、特にソフトウェアでの実装では時間がかかることがあり、負の数のソートには使えないという欠点も持つ。また、少なくともこのアルゴリズムは空間計算量が"O"("n2")である。
アルゴリズムの概要.
ビーズソートの処理は、平行に並べられた糸をビーズが滑り落ちる様子で理解できる。図のステップ1では、"n"=5行"m"=4列の糸を考える。下から"n"行目は"n"個目のデータを格納する場所であり、1行目と2行目に3つずつビーズがあるため、1個目と2個目のデータが3であることを表している。
ここでビーズを重力に従って落下させると、それぞれの行の値がソート後の値となる。1行目は最大の数であり、"n"行目が最小の数である。もし上記の脚注通り左詰めでビーズを入れた場合、ビーズの右端の位置でソートの結果がわかる。
ハードウェアでの実装において、ビーズを「落下させる」ことを可能にする動作は、より高い行からより大きな値をより低い行に伝播させることを可能にした。 "a"行目の値が"a"+1行目の値よりも小さい場合、"a"+1行目の一部のビーズは"a"行目まで落下する。"a"行目のビーズが存在している場所は"a"+1行目のビーズの落下を物理的に邪魔するため、自動的に値が入れ替わる。
ビーズソートのメカニズムは計数ソートの背景にあるメカニズムと似ており、それぞれの行に存在するビーズの数は、その段数以上の値を持つ要素の数に対応する。
計算複雑性.
ビーズソートは、計算複雑性が異なる4種類の実装が可能である。
鳩の巣ソートのように、ビーズソートの最悪計算量が"O"("n"log)を下回る点で珍しく、最良計算量は比較ソートの最悪計算量である。ビーズソートの要素は非負整数であり、その制約を利用するため、このような高速なソートが可能である。
実装例.
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文が止まってしまう可能性がある"""