ビーズソート
From Wikipedia, the free encyclopedia
ビーズソートの処理は、平行に並べられた糸をビーズが滑り落ちる様子で理解できる。図のステップ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(): 重力を用いる物理モデル。落下距離は時間の2乗に比例するため、落下時間はデータの数の平方根に比例する。
- O(n): ビーズが等速で移動するモデル。ソフトウェアでの実装では、下にビーズがあるかを確認するため、この時間計算量が相当する。
- O(S): Sはビーズの総数であり、ソフトウェアでの実装では、各ビーズに対して落下可能かを確認する効率的なアルゴリズムが存在しない場合、この計算量となる。
鳩の巣ソートのように、ビーズソートの最悪計算量がO(nlog)を下回る点で珍しく、最良計算量は比較ソートの最悪計算量である。ビーズソートの要素は非負整数であり、その制約を利用するため、このような高速なソートが可能である。
