バブルソートの可視化

Twitter / kabipan otoko: @hi_saito バブルソート、泡が上ってくる様子が可視化できると楽しそうですね。 にインスパイヤされて可視化してみます。

awk を使った可視化としてはコンソールに出力する方法もありますが、ここでは gnuplot を使って可視化してみます。 以前、AWK Users JP :: CPU 負荷率のグラフ化 で可視化した方法と同じ手法です。

#! /usr/local/bin/nawk -f
# bubble_sort.awk
# バブルソート
# usage: nawk -f bubble_sort.awk file

BEGIN {
    max = 30;

    for (i = 1; i <= max; i++) {
        line[i] = int(rand() * max);
    }

    bubble_sort(line, max);

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

# ref: http://en.wikipedia.org/wiki/Bubble_sort
function bubble_sort(arr, num,    swapped, i, tmp) {
    do {
        swapped = 0;
        for (i = 1; i <= num - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = 1;

                draw_gnuplot();

            }
        }
    } while (swapped)
}

function draw_gnuplot(data_file, tmp_file,    i) {
    data_file = "data_file";
    for (i = 1; i <= max; i++) {
        print i, line[i]                            > data_file;
    }
    close(data_file);

    tmp_file = "tmp_file";

    print "set terminal png"                        > tmp_file;
    print "set yrange [0:" max "]"                  > tmp_file;
    print "set xlabel 'num'"                        > tmp_file;
    print "set ylabel 'num'"                        > tmp_file;
    print "set size 0.5,0.5"                        > tmp_file;
    count++;
    print "set output \"bubble_" sprintf("%04d", count) ".png\""    > tmp_file;
    print "plot \"" data_file "\" using 1:2 title ''"   > tmp_file;
    print "quit"                                    > tmp_file;
    close(tmp_file);

    gnuplot_exec = "/usr/bin/gnuplot " tmp_file " > /dev/null";

    system(gnuplot_exec);
    close(gnuplot_exec);
}

バブルソートの入れ替えの部分に draw_gnuplot() という関数を入れています。

実行するとカレントディレクトリにたくさんの PNG ファイルができます。 これはバブルソートが最悪で O(n^2) であるからです。

また、ImageMagick を使って一気にアニメーション GIF を生成しています。

$ nawk -f bubble_sort_2.awk

$ convert bubble_*.png bubble_sort.gif

Doukaku_257.gif

最初、調子にのって max = 100 で実行すると、あまりにも大量の PNG ファイルができてしまい、アニメーション GIF の生成にも大量のメモリを消費してしまったので、実行する時には計算量に充分注意して実行してみてください。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png