(O+P)ut

習うより慣れろ、Practice makes perfect。この言葉をモットーに、Slerで働く若手インフラエンジニアが、学んだ知識を【 (O+P)ut = OutPut 】していく場です。

ソートの結果を可視化してみる

Javaで学ぶデータ構造とアルゴリズム」という杉山行浩さんの本を読んでいたら,ソートの結果を可視化して図にしていた.これは面白い!と思ったので紹介させてもらうと同時に,僕も実際にソートした結果をGifにしてみました.

まずソートの可視化方法.例えば大きさ100の配列に,未ソートの状態で実数が入っている時に,配列のインデックスをx座標,その配列の値をy座標にとるというものでした.

つまり,例えば配列の大きさを1000として0~1で一様乱数を発生させると以下のようなグラフになります.
f:id:mtiit:20151003185351p:plain

これを初期状態としてソートを行っていく際の途中経過を表示していくのが,今回言っている「ソートの可視化」です.

百聞は一見に如かず.
選択ソートで可視化をしてみます.選択ソートとは,
例えば 大きさ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
とソートが行われる,というアルゴリズムですね..

このアルゴリズムを用いて,0~1の一様分布に従った乱数1000個の配列に対して50個整列が終わる毎に出力したものをGifにしたのが下の画像です.







f:id:mtiit:20151003195514g:plain
分かりやすい...左側から整列していく様子が一目瞭然で分かる!

ついでにもう一つ.バブルソートではどのように整列が進むのでしょうか.
バブルソートとは,同じように大きさ5の配列
2 7 5 9 1
があった時に,一番右側の「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までが整列済み,というのを最後まで繰り返すアルゴリズムですね.

ではこれを同じようにGifにしてみると,どんな風に整列が進むか想像つきますかね?
正解は下の画像のようになりました.







f:id:mtiit:20151003195457g:plain
なるほど,バブルソートは隣あった数の比較を進めながら整列が進むので選択ソートよりかは途中段階においても緩やかなソートが行われていることが見て取れます.

このように,ソートのアルゴリズムを視覚的に表示させるのは,かなりいいアイデアだとは思う*1
上で紹介した本の中にはマージソートヒープソートも載っていて,「こんな整列の仕方してるのか!」と思った.

あと,今回はRでグラフを出したりしてたんですけど

plot(hoge)
dev.copy(png,file=filename)
dev.off()

でファイルネームでplotをpngファイルで保存できるんですね*2.便利でした.

*1:もちろんこの作者が考えついたとは思っていないが,僕はこの本で初めて知ったので!

*2:たしかpdfとか他の拡張子でもいける