分布数えソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。
バケットソート、バケツソート、ビンソートなどとも呼ばれる。実行速度は0(n)と高速であり、また安定である。アルゴリズムは以下のとおり。

• データを通読してキーの度数分布を数える
• 度数分布を累積して順位に変換する
• 順位の場所にデータを入れなおす

データは一定の範囲の整数値で無ければならないが、そうでない場合もキー値を整数に丸めた上で大まかに整列し、最後に挿入ソートで仕上げることもできる。 配列の参照が順を追って行われないため、仮想記憶上で大量のデータを整列しようとするとクイックソートより遅くなる場合がある。

プログラミング掲示板「ソートロジック大会」なども参照のこと

Const MAX = 100 '分布の上限値
Const MIN = 0 '分布の下限値
Sub distsort(n As Integer, a As *Integer, b As *Integer)
Dim i As Integer, x As Integer
Dim count[MAX - MIN] As Integer ' 度数分布の配列
'度数分布の初期化
For i = 0 To MAX - MIN
count[i] = 0
Next i
'度数分布の数え
For i = 0 To n
count[a[i] - MIN] = count[a[i] - MIN] + 1
Next i
'順位の決定
For i = 1 To MAX-MIN + 1
count[i] = count[i - 1] + count[i]
Next i
'再配列
For i = n To 0 Step -1
x = a[i] - MIN
count[x] = count[x] - 1
b[count[x]] = x
Next i
End Sub