ビーズソートを使用する

ビーズソート (bead sort, gravity sort) は、各正整数を「そろばんの玉（ビーズ）」として棒に載せ、重力で落下させたあとの段数を読み取ることで昇順に並べる。

デジタル実装では、棒 j（0 始まり）に載っているビーズ数を配列で数え、入力の各値 x について棒 0 … x - 1 へ玉を 1 個ずつ載せたあと、下の段から順に「まだ玉がある棒の本数」を読み取る。

  1. 最大値の決定: 配列の最大値 max を求め、棒の本数を max とする。
  2. ビーズを載せる: 各要素 x について、棒 0 から x - 1 までのビーズ数を 1 ずつ増やす（値が大きいほど多くの棒に玉が載る）。
  3. 重力（落下）: 数え上げ実装では、棒ごとの合計がすでに「落下後」の積み上がりに相当する。
  4. 段の読み取り: 下の段から、ビーズが残っている棒の本数を数え、その本数をソート結果の要素とする。読んだビーズは各棒から 1 個ずつ取り除く。
procedure gravity_sort(A)
  if length(A) = 0 then return
  maxVal = maximum(A)
  if maxVal = 0 then return
  beads[0..maxVal-1] = 0
  for each x in A
    for j from 0 to x - 1
      beads[j] = beads[j] + 1
  for i from length(A) - 1 downto 0
    sum = 0
    for j from 0 to maxVal - 1
      if beads[j] = 0 then break
      sum = sum + 1
      beads[j] = beads[j] - 1
    A[i] = sum

正整数に限り、時間計算量はビーズの総数に比例して O(n · max)（または値の総和 S に対し O(S)）、補助空間は棒の本数ぶん O(max) である。入力が 1 … n の順列なら max = n となり平均・最悪とも O(n²) になる。値から棒への載せ方は一意なので、同値の相対順序は入力順とは無関係（一般に不安定）。

物理的なそろばんモデルの説明や可視化には向くが、max が大きいと棒配列とビーズ操作のコストが急増するため、実務では カウンティングソート など値域依存の別手法の方が扱いやすいことが多い。

次の図は入力 [3, 1, 4, 2] をそろばんに見立てたイメージである。各数ぶんの玉を棒へ載せ、重力で落下させたあと、各段に並ぶ玉の個数を上から読むと昇順 [1, 2, 3, 4] になる。

類似アルゴリズムとの相違点

カウンティングソートは値ごとの出現回数を数えて配置するのに対し、ビーズソートは「棒に玉を載せて落下させる」物理モデルで同じ情報を積み上げる。数え上げ実装では結果がカウンティングに近づくが、可視化と計算量の語り方が異なる。

鳩の巣ソートは値ごとの巣へ要素自体を入れる。スリープソートも物理量（待ち時間）に値を写す比喩だが、こちらは空間上のビーズ配置を使う。