7.3 プログラム例: 基数ソート

基数ソートアルゴリズムは、list および deque の他のコンテナとの組み合わせの良い例です。基数ソートでは、deque の vector がハッシュテーブルのように操作されます。

---

注: 完全な基数ソートプログラムは radix.cpp ファイルにあります。

---

基数ソートは、正の整数値リストの順序付けを行う手法です。値は、桁位置を右から左へと順に並べられます。これは、ソートされた桁位置によってバケットのインデックスが指定される場合、値をバケットに挿入することで実行することができます。すべての桁位置が検証されると、リストが必ずソートされます。

表 11 に、624 852 426 987 269 146 415 301 730 78 593 というリストのソートで実行された 4 つのステップの間に、各バケットで検出された値のシーケンスを示します。パス 1 では、1 の桁が順序付けられます。パス 2 では、前のパスで設定された相対位置を保持しながら、10 の桁が順序付けられます。パス 3 では、再び前のパスで設定された相対位置を保持しながら、100 の桁が順序付けられます。3 つのパスの結果が、順序付けられたリストとなります。

表 11 -- 基数ソートによる各バケットの値のシーケンス

基数ソートのアルゴリズムは単純です。while ループは、さまざまなパスで循環させるために使用されます。変数 divisor の値は、現在検証されている桁を示します。ブール型のフラグは実行の停止を指定するために使用されます。while ループが実行されるたびに、deque の vector が宣言されます。while ループ内にこの構造の宣言を配置することによって、各ステップを空にするために再初期化が行われます。ループが実行されるたびに、各値に対して関数 copyIntoBuckets() を実行することによって、list の値が適切なバケットにコピーされます。値は一度バケットに分散され、蓄積によって list に戻されます。

void radixSort(list<unsigned int> & values)
{
   bool flag = true;
   int divisor = 1;
   
   while (flag) {
      vector< deque<unsigned int> > buckets(10);
      flag = false;
      for_each(values.begin(), values.end(), 
            copyIntoBuckets(...));
      accumulate(buckets.begin(), buckets.end(), 
            values.begin(), listCopy);
      divisor *= 10;
      }
}

ここでの関数 accumulate() の使用は、通常とは多少異なります。作成されるスカラー値が list そのものとなります。蓄積の初期値は、list の先頭を示す反復子です。各バケットは、次の 2 項関数で処理されます。

list<unsigned int>::iterator 
      listCopy(list<unsigned int>::iterator c, 
         deque<unsigned int> & lst)
{
   // リストを元のリストにコピーし、終端に戻る
   return copy(lst.begin(), lst.end(), c);
}

ここで残った唯一の問題は、関数 copyIntoBuckets() の定義です。ここでの問題は、挿入される要素だけを関数の引数としなくてはならないことですが、同時に buckets、divisor、flag の 3 つの値へアクセスする必要があります。他の関数内での関数の定義を許可する言語では、解が while ループ内の局所関数として copyIntoBuckets() に定義されます。しかし、C++ には、このような機能はありません。代わりに、適切な値への参照で初期化できるように、クラス定義を作成する必要があります。このクラスの括弧演算子は、基数ソートプログラムでの関数 for_each() 呼び出しとして使用されるようになります。

class copyIntoBuckets {
public:
   copyIntoBuckets
      (int d, vector< deque<unsigned int> > & b, bool & f) 
         : divisor(d), buckets(b), flag(f) {}

   int divisor;
   vector<deque<unsigned int> > & buckets;
   bool & flag;

   void operator () (unsigned int v)
   {   int index = (v / divisor) % 10;
       // bucket がある場合、フラグが true に設定される
       // ゼロ次以外が使用される
       if (index) flag = true; 
       buckets[index].push_back(v);
   }
};