Design-and-analysis-of-algorithms-radix-sort

DAA-基数ソート

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

直観的には、数字を最上位桁でソートしたい場合があります。 ただし、Radixソートは、最下位桁を最初にソートすることにより、直感に反して機能します。 最初のパスでは、すべての数値が最下位桁でソートされ、配列に結合されます。 次に、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

分析

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

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

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

例

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

Input	1st Pass	2nd Pass	3rd Pass
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

上記の例では、最初の列が入力です。 残りの列は、次第に有効数字の位置で連続してソートした後のリストを示しています。 Radixソートのコードは、 _ n_ 要素の配列 A の各要素が d 桁であると想定しています。ここで、桁 1 は最下位桁で、 _ d_ は最上位桁です。