バケットソート【bucket sort】ビンソート

概要

k種類の値を取りうるn個のデータ列があるとき、何らかのデータ構造として実装されたk個の置き場を用意しておき、データを端から順にその値に対応付けられた置き場に移していく。置き場から並べたい順にデータを取り出していけば整列完了となる。データを比較しないソート法で、平均して O（n+k） の線形時間でソートが完了する。

取りうる値が「0から99の整数」などといった場合は容易に実装できるが、「任意の32ビット整数値」になると約43億の置き場を用意する必要があり、単純な実装は困難となる。さらに「任意長の文字列」のような対象になるとそもそも取りうる値すべてを列挙することができないため、この方法で整列することはできない。

実用しようとすると極めて多数の取りうる値を相手にしなければならないことが多いため、例えば上位側から区切った短い桁数の値を用いて少ないバケツでソートし、各バケツの中を同じ桁数でソートし…という操作を再帰的に繰り返すといった工夫が必要になる。このような処理を繰り返すと結局は計算量も O（nlogn） といったオーダーになり、他の高速なソート法より圧倒的に有利ということにはならない。