「分布数えソート」の編集履歴（バックアップ）一覧はこちら

「分布数えソート」(2010/01/25 (月) 19:02:36) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

整列アルゴリズムのひとつ。
バケットソート、バケツソート、ビンソートなどとも呼ばれる。実行速度は0(n)と高速であり、また安定である。アルゴリズムは以下のとおり。 
-データを通読してキーの度数分布を数える
-度数分布を累積して順位に変換する
-順位の場所にデータを入れなおす

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

プログラミング掲示板「ソートロジック大会」なども参照のこと 
#asciiart(blockquote){
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
}