配列をランダムにシャッフルする場合C++ではrandom_shuffle()を使いますが，Cの標準関数にはそのような関数は無いようです．Fisher-Yatesの方法*2を使ってこれを実現してみます．
直接要素を並び替えることもできますが，今回は二つのステップをふむものとします．まず最初にランダムなインデックス列を生成し，それを使って配列の要素を並び替える，という手順です．Fisher-Yatesの方法でランダムなインデックス列を生成するには，次のアルゴリズムを用います．
- すでに選択された要素かどうか記憶しておくためのテーブルを用意する．
- 0からまだ選択されていない数字の個数-1の間で，ランダムに数字を生成する．生成された数字をkとする．
- テーブルを参照しつつ，まだ選択されていない要素のうちk番目の要素を選択する．テーブルの方にも選択したことを記憶しておく．
- これをすべての要素を選択するまで繰り返す．
これをCで書くと，次のようになります．
void rand_index(size_t n, size_t* idx)
{
size_t i, j, k, m;
int unstruck[n];
for(i = 0; i < n; ++i) {
unstruck[i] = 1;
}
for(i = 0; i < n; ++i) {
m = rand() % (n - i);
for(j = 0, k = 0; !(unstruck[j] && k == m); ++j) {
if( unstruck[j] )
++k;
}
idx[i] = j;
unstruck[j] = 0;
}
}nは配列のサイズで，idxには0~n-1までのランダムにシャッフルされたインデックス列が書き込まれます．このインデックス列を使って，要素の並び替えを行います．
#define N 10
void print_val(size_t n, double* val)
{
size_t i;
for(i = 0; i < n; ++i) {
printf("[%d]: %f\n", i, val[i]);
}
}
int main()
{
size_t idx[N];
double val1[N];
double val2[N];
size_t i;
srand(time(NULL));
// 適当に値をセット
for(i = 0; i < N; ++i) {
val1[i] = 0.5 * i;
}
print_val(N, val1);
// ランダムなインデックスを作成
rand_index(N, idx);
printf("---------\n");
// シャッフル
for(i = 0; i < N; ++i) {
val2[i] = val1[idx[i]];
}
print_val(N, val2);
}これを実行すると次のような結果が得られ，元の配列の要素がランダムにシャッフルされていることがわかります．
[0]: 0.000000 [1]: 0.500000 [2]: 1.000000 [3]: 1.500000 [4]: 2.000000 [5]: 2.500000 [6]: 3.000000 [7]: 3.500000 [8]: 4.000000 [9]: 4.500000 --------- [0]: 4.000000 [1]: 2.000000 [2]: 1.500000 [3]: 3.500000 [4]: 1.000000 [5]: 4.500000 [6]: 0.500000 [7]: 2.500000 [8]: 0.000000 [9]: 3.000000
