![見出し画像](https://assets.st-note.com/production/uploads/images/97107681/rectangle_large_type_2_e0df26f4d322eda268b412e9008c6774.jpeg?width=1200)
『写経』からの道草 その2
お疲れ様です。Y研究員です。京都の人と話していて「法隆寺」に行きたいですと言ってしまいました。あとからすぐ奈良と気がついても後の祭りです。。。
今日は前回に引き続き、ソートを深堀します。予告通り、ソートが完了するまでランダムに並び替えつづける(シャッフルし続ける)ボゴソートを実装しました。このシャッフルもアルゴリズムの一つで、よく調べると「フィッシャー・イエーツのシャッフル」という名前がついていました。なお、プログラムで書いているものは、正確に言うとダステンフェルドのアルゴリズムになるそうです
ざっとCで書いてこんな感じです。
int is_sorted(int v[], int length)
{
for (int i = 0; i < length - 1; i++)
{
if (v[i] > v[i+1])
{
return 0;
}
}
return 1;
}
void durstenfeld_shuffle(int v[], int length)
{
srand(time(NULL));
int r, tmp;
for (int i = 0; i < length; i++)
{
r = rand() % length;
tmp = v[i];
v[i] = v[r];
v[r] = tmp;
}
}
void bogosort(int v[], int length)
{
while (is_sorted(v, length) == 0)
{
durstenfeld_shuffle(v, length);
}
}
動かしてみた所、配列の要素が4までなら数秒で結果がでました。試しに6まで増やしたらだいぶ待たされたので、実用に程遠いことがよく分かりました。
おふざけソートアルゴリズムはこの他にもスリープソートがあると分かりました。マルチスレッドで走らせて各要素の長さだけスリープさせると、昇順で帰ってくる仕組みです。pthreadを使って書いてみたくなったので明日やってみたいと思います。
写真はスリープということで寝てる猫です。猫はよく寝ていますね。猫が怠けていると思いきや、人間が活動し過ぎなのかもしれません。少しは猫を見習ったほうが良さそうです。
それではまた!
般若心経の写経とプログラムの『写経』に関する記事はこちらからどうぞ。
無料のプログラミングクラブCoderDojoを運営するにあたり寄付を受け付けています。お金は会場費・Wifiの費用・教科書に使用します。