Fisher-Yatesのシャッフルアルゴリズムをc言語で実装してみる

Fisher-Yatesのシャッフルアルゴリズムをc言語で実装

配列の要素をランダムに並べ替える手法として、Fisher-Yatesのシャッフルアルゴリズムが有名ですね。
ランダムに選ばれた配列の要素を、配列の末尾の要素と入れ替えます。
入れ替えは配列の最後尾から開始して、先頭の要素まで順次ループ処理します。
入れ替え対象の要素は、入れ替え済みの末尾の要素は対象外となります。
計算量はO(n)となります。

void shuffleArrayData(int* array, int size){
	int i, target, tmp;
	
	//最後尾から順次ループ処理
	for(i = size -1; i > 0; i--){
		//0~i番目の要素から、入れ替え対象の要素をランダムに選ぶ
		target = rand() % i;
		//ここから下は末尾の要素と入れ替え
		tmp = array[target];
		array[target] = array[i];
		array[i] = tmp;
	}
}

最後尾からループ処理することで、入れ替え対象の要素を選ぶコードが、下記のようにシンプルに書けますね。
実際に書いてみると感動します。

		target = rand() % i;

サンプルコード

下記がサンプルコードになります。

$ cat sample.c 
#include <stdio.h>
#include <stdlib.h>

void shuffleArrayData(int* array, int size){
	int i, target, tmp;
	
	for(i = size -1; i > 0; i--){
		target = rand() % i;
		tmp = array[target];
		array[target] = array[i];
		array[i] = tmp;
	}
	
	for(i = 0; i < size; i++){
		printf("%d ", array[i]);
	}
}

int main(){
	int array[] = {4, 2, 8, 7, 1, 2, 3};
	//int array[] = {4, 2};
	//int array[] = {4};
	
	shuffleArrayData(array, (int)(sizeof(array) / sizeof(array[0])));
		
	return 0;
}

$ gcc -o sample sample.c
$ ./sample 
2 7 4 8 3 1 2