『写経』からの道草　その２

2023年2月3日 07:46

お疲れ様です。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);
    }
}

動かしてみた所、配列の要素が４までなら数秒で結果がでました。試しに６まで増やしたらだいぶ待たされたので、実用に程遠いことがよく分かりました。

おふざけソートアルゴリズムはこの他にもスリープソートがあると分かりました。マルチスレッドで走らせて各要素の長さだけスリープさせると、昇順で帰ってくる仕組みです。pthreadを使って書いてみたくなったので明日やってみたいと思います。

写真はスリープということで寝てる猫です。猫はよく寝ていますね。猫が怠けていると思いきや、人間が活動し過ぎなのかもしれません。少しは猫を見習ったほうが良さそうです。

それではまた！

般若心経の写経とプログラムの『写経』に関する記事はこちらからどうぞ。

無料のプログラミングクラブCoderDojoを運営するにあたり寄付を受け付けています。お金は会場費・Wifiの費用・教科書に使用します。

『写経』からの道草 その２

『写経』からの道草　その２