DAA-基数ソート

Radix sortは、多くの人が名前の大きなリストをアルファベット順に並べるときに直感的に使用する小さな方法です。具体的には、名前のリストは最初に各名前の最初の文字に従ってソートされます。つまり、名前は26のクラスに配置されます。

直感的には、最上位桁で数値を並べ替えることができます。ただし、基数ソートは、最下位桁を最初にソートすることにより、直感に反して機能します。最初のパスでは、すべての数値が最下位桁でソートされ、配列に結合されます。次に、2番目のパスで、数値全体が2番目の最下位桁で再度ソートされ、配列に結合されます。

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

分析

各キーは、最長のキーの各桁（またはキーがアルファベットの場合は文字）ごとに一度に調べられます。したがって、最長のキーがm 数字とがあります n キー、基数ソートには順序があります O(m.n)。

ただし、これら2つの値を見ると、キーの数と比較すると、キーのサイズは比較的小さくなります。たとえば、6桁のキーがある場合、100万の異なるレコードを持つことができます。

ここでは、キーのサイズは重要ではなく、このアルゴリズムは線形の複雑さであることがわかります。 O(n)。

例

次の例は、基数ソートが7つの3桁の数値でどのように動作するかを示しています。

入力	1回目のパス	2回目のパス	3回目のパス
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

上記の例では、最初の列が入力です。残りの列は、有効数字の位置が連続してソートされた後のリストを示しています。基数ソートのコードは、配列内の各要素を想定していますA の n 要素は持っています d 数字、ここで数字 1 は最下位桁であり、 d は最上位桁です。