並べ替えのアイデア

[アンドリュー]

0 から n-1 の合計n個の数字が、配列a[n]に入ってるのですが、
並んでいる順番をばらばらにしたいのです。
たとえば、
a[5]={0,1,2,3,4}
を、
a[5]={3,0,4,2,1}
といった具合に。
乱数を使い、実行するたびに結果が異なるようにしたいのですが、
何かいい方法はないでしょうか？
ついでに言うと、配列の数が5ではなく10000とか100000とかでも
比較的早く、まんべんなくばらばらになるような方法を…。

[box]

ほんの一例です。
0からn-1の範囲にある整数の乱数を2個（i,jとします）発生させて、
aとa[j]を入れ替えます。
この操作を所定の回数だけ繰り返せば、a[/url]の中身がばらけると思います。
「所定の回数」をいくつにすればいいかは、いろいろ試してみてください。

[lbfuvab]

ランダムソートでググってみて下さい。

[アンドリュー]

ぼくがやろうとしていることはランダムソートと呼ぶのですか！
たしかに入れ替えを繰り返すうちにばらつきが出てきますね。
いろいろ調べてみようと思います。ありがとうございました。

[lbfuvab]

後、一応自前で実装するならこうします。
xor128内のx,y,z,wの値を変えると、毎回違う結果になります。

#include<stdio.h>
#define SWAP(a,b)  (a^=b,b^=a,a^=b)
#define MAX 0xffffffff

unsigned long xor128(){						//速さならXorShift
  static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

int shuffle(int *buf,int len){
	int i;
	
	for(i=0;i<len;i++)
		SWAP(buf,buf[(int)(xor128()/(double)MAX)]);
	
	return 0;
}

[SCI]

＞#define SWAP(a,b) (a^=b,b^=a,a^=b)
これは今回のように仕様が確定している前提では上手くいきますね。

[Justy]

　ちょっと疑問に思ったのですが、

＞(int)(xor128()/(double)MAX)

　この結果は毎回０か１のどちらかしかならないような気がしますが、
それはそういうものなのでしょうか？


＞SWAP(buf,buf[(int)(xor128()/(double)MAX)]);

　仮に上の bufと buf[?]の交換だったとして、この SWAPの方式だと
もし iと ?が同じだった場合破綻しませんか？

[lbfuvab]

>＞(int)(xor128()/(double)MAX)
>
>　この結果は毎回０か１のどちらかしかならないような気がしますが、
>それはそういうものなのでしょうか？
>それはそういうものなのでしょうか？
>
>
>＞SWAP(buf,buf[(int)(xor128()/(double)MAX)]);
>
>　仮に上の bufと buf[?]の交換だったとして、この SWAPの方式だと
>もし iと ?が同じだった場合破綻しませんか？


わわわっ、すいません。間違ってました。
コンパイルせずに書くとやっぱりまずいですね。
2行目は
#define SWAP(a,b) ((a!=b)?(a^=b,b^=a,a^=b):0)
15行目は
SWAP(buf,buf[(int)((xor128()/(double)MAX)*len)]);
にします。

失礼しました。

[バグ]

私が好きなのは、Fisher Yatesかな？
理論自体はboxさんが言われているのと同じですね。
シンプルで、なおかつ最低限のシャッフル回数で済むのでスピードもそこそこです。
サンプルソースを載せておきますね。

#include <stdlib.h>

// int* buf = データ格納用バッファ
// int length = データ格納用配列の長さ
void shuffle(int*buf, int length)
{
	int i, index, swap;

	// 配列の初期化
	for (i = 0; i < length; ++i)
	{
		buf = i;
	}

	// シャッフル
	for (i = length - 1; i >= 0; --i)
	{
		index = rand() % length;
		swap = buf;
		buf = buf[index];
		buf[index] = swap;
	}
}