はじめに
「Javaで学ぶデータ構造とアルゴリズム」*1を読んでいた際、ソート結果をユニークに可視化して図示していました。
見せ方として素敵だったので、紹介がてらR言語にて実装してみました。
コード等は簡単なので省略しますが、割とおもしろい動きを見れるのでぜひご覧ください。
ユニークな可視化手法
まずソートの可視化方法ですが、例えば大きさ1000の配列に未ソートの状態で実数が入っているとします。
配列のインデックスをx座標、その配列に格納されている実数の値をy座標にとると、どうなるでしょうか。
今回は、配列の大きさを1000の中で、０～１ の乱数を発生させてプロットしてみました。
以下のようなグラフになります。
これを初期状態とし、ソートを行っていく際の途中経過を表示していくのが著書で紹介されていた「ソートの可視化」です。
百聞は一見に如かずということで、選択ソートを実装しました。
選択ソートとは、要素から最大値または最小値を探索し、配列の最後の要素と入れ替えを順々に行っていくソート手法です。
例えば 大きさ5の配列
2 7 5 9 1
があった時に，
一番小さな 1 を 一番左に持ってきて、元あった2と入れ替える。
1 7 5 9 2
ここで一番左は整列済みなので、次は未整列な4つの中で一番小さい 2 を 一番左(整列しているところは除いて)と入れ替える。
1 2 5 9 7
これを繰り返すと残りは、
1 2 5 7 9
とソートが行われる、というアルゴリズムです。左側から順々に揃っていきます。
選択ソートを可視化
乱数で作られた1000個の配列に対して、50個整列が終わる毎に出力したものをGifにしました。
左側から整列していく様子を確認できます。
ついでにバブルソートを可視化
バブルソートとは、同じように大きさ5の配列
2 7 5 9 1
があった時に、一番右側の「１」から自分の左隣と比較して右側の方が小さければ値を交換していきます。
上の例で言えば、9 と 1 を比較すると1の方が小さいので
2 7 5 1 9 となる...次は5と1の比較で...
2 7 1 5 9
2 1 7 5 9
1 2 7 5 9
となって一番左側は整列済み、となります。同じようにまた 9と5を比較して、
1 2 7 5 9
1 2 5 7 9
1 2 5 7 9
となって1,2までが整列済み、というのを最後まで繰り返すアルゴリズムです。
これを可視化したものが以下です。
ちなみに、上で紹介した本の中にはマージソートやヒープソートも載っています。
ここからはメモ書きですが、今回はRでプロット結果を大量に出力したのですが、
plot(hoge) dev.copy(png,file=filename) dev.off()
で任意のファイルネームでプロット結果ををpngファイルで保存できます。
以上、ご参考ください。
*1:杉山行浩さん著
