オリジナルのFisher-Yatesより効率的なランダムシャッフル

以前の記事では，FisherとYatesが提案したアルゴリズムを用いてランダムシャッフルを行いました．これを，より効率的に行う方法が考えられているようです*2．

前のアルゴリズムと同じくランダムにシャッフルしたインデックス列を生成することを考えると，次のようなコードになります．

void rand_index(size_t n, size_t* idx)
{
    size_t i, j, tmp;
    
    for(i = 0; i < n; ++i) {
        idx[i] = i;
    }
    
    for(i = n - 1; i > 0; --i) {
        j = rand() % (i + 1);
        
        // idx[i]とidx[j]をスワップ
        tmp = idx[i];
        idx[i] = idx[j];
        idx[j] = tmp;
    }
}

これはFisher-Yatesの元々のアルゴリズムを効率化したものになっています．元々の方法では一度選択したものをチェックしてテーブルに保存しておき，新しい乱数発生時にそのテーブルを参照して未選択のものだけを辿っていました．上のアルゴリズムでは，選択した要素をチェックしておく代わりに，選択した要素と(有効な範囲のうちの)末尾の要素をスワップしています．これによって，先頭にある要素は常に未選択であることが保証されます．
例えば0から4の範囲で考えると，

[0,1,2,3,4]
 ↓(2を選択)
[0,1,4,3,2]
 ↓(1を選択)
[0,3,4,1,2]
 ↓(4を選択)
[0,3,4,1,2]
 ↓(0を選択)
[3,0,4,1,2]
 ↓(3を選択)
[3,0,4,1,2]

のようになります．こうして生成される[3,0,4,1,2]は，ランダムにシャッフルされたインデックス列になっています．元々のアルゴリズムが要素数nに対して計算量O(n²)であるのに対し，このアルゴリズムは未選択の要素の探索処理がない分，計算量としてはO(n)になっています．