配列のシャッフル

リストの要素のシャッフルを見て、awk でシャッフルをやってみます。

#! /usr/bin/gawk -f
# shuffle.awk

BEGIN {

    # 毎回同じなのも嫌なので srand() で初期化
    srand();

    # 順番どおりの配列を生成
    for (i = 1; i <= 10; i++) {
        array[i] = i;
    }

    # 配列をシャッフル
    shuffle_array(array);

    # シャッフルしたものを表示
    for (i = 1; i <= num_arr; i++) {
        print array[i];
    }
}

# 配列をシャッフル
function shuffle_array(arr,    tmp) {
    for (a in arr) {
        num_arr++;
    }

    for (i = num_arr; i >= 1; i--) {
        j = int((i + 1) * rand());

        if (j == 0) {
            j = 1;
        }

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

実際に実行してみましょう。

$ gawk -f shuffle.awk
6
8
2
5
10
3
1
4
7
9

さて、リストの要素のシャッフルの中に bogo sort という言葉がありますので、bogo sort を作ってみます。

#! /usr/bin/gawk -f
# bogo_sort.awk

{
    line[NR] = $0;
}

END {
    bogo_sort(line, NR);

    for (i = 1; i <= NR; i++) {
        print line[i];
    }
}

# bogo sort
function bogo_sort(arr, num) {
    while (is_sort(arr, num) != 1) {
        shuffle_array(arr, num);
    }
}

# is sorted?
function is_sort(arr, num,   ans) {
    for (i = 1; i <= num - 1; i++) {
        if (arr[i] <= arr[i + 1]) {
            ans = 1;
        } else {
            ans = 0
            break;
        }
    }
    return ans;
}

# 配列をシャッフル
function shuffle_array(arr, num,    tmp) {
    for (i = num; i >= 1; i--) {
        j = int((i + 1) * rand());

        if (j == 0) {
            j = 1;
        }

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

なんとも奇妙なソートですが、要するにソートが完了するまでシャッフルするというもので、O(n x n!) の平均計算時間を必要とします。

$ time gawk -f shuffle.awk  | gawk -f bogo_sort.awk
1
2
3
4
5
6
7
8
9
10
gawk -f shuffle.awk  0.00s user 0.00s system 60% cpu 0.007 total
gawk -f bogo_sort.awk  49.69s user 0.11s system 99% cpu 50.091 total

マシンが代わり、CoreDuo 2.5 GHz なのですが、50 秒もかかってしまいました。