flashでソートアルゴリズムをヴィジュアライズしてみた

flash

経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログを見て，自分もなにかアルゴリズムをヴィジュアライズしてみたくなった．

さらに，Perfect Shuffle Visualizationを見て,
同じような感じでソートをヴィジュアライズできないかと思ったのでやってみた．



見れない人はこちら


とりあえず，バブルソートと挿入ソートとマージソート，クイックソートの4種類．
左端がシャッフルされた状態で，右端がソートが完了した状態．
また，ソートアルゴリズムが1ステップ進むごとに，どこに要素が移動するかを線でつないでいる．

要素数は64個．変数一個をいじるだけで簡単に変えることは出きるが，
外部から変えるのは面倒そうだったので未実装．
あとで実装するかも．


他のソートアルゴリズムも気が向いたら実装する予定
http://en.wikipedia.org/wiki/Category:Sorting_algorithms


なお，マージソートとクイックソートは分割統治によるものなので，1ステップがよくわからないが，適当に（ほとんど）同値なものをfor文でエミュレートしている．

バブルソート

http://en.wikipedia.org/wiki/Bubble_sort
隣合うもの同士を比較して，順序が逆ならスワップすることを繰り返すアルゴリズム．
上から下までなめるのを繰り返すように実装したため，下の方の要素から正しい位置に来ていることが見て取れる．
時間計算量はO(n^2)

挿入ソート

http://en.wikipedia.org/wiki/Insertion_sort
上からk個がソートされているとき，k+1個目の要素を正しい位置に挿入することで，上からk+1個をソートされた状態にすることを繰り返すアルゴリズム．
kステップ目でk番目の要素は動かされるため，対角線が見える．
時間計算量はO(n^2)．

クイックソート

http://en.wikipedia.org/wiki/Quicksort
適当な値（今回は一番上の要素の値）より小さいものと大きいものに再帰的に分割していくアルゴリズム．
序盤の数回でほとんどソートできているのが見て取れるようにとても速い．
ただし，ある程度要素が少なくなると遅いので別のアルゴリズムを用いるとよりよくなるらしい．
時間計算量は平均でO(n log n)，最悪でO(n^2)
平均的には4つのなかでもっとも速い．

マージソート

http://en.wikipedia.org/wiki/Merge_sort
上半分と下半分に要素を分け，それぞれをソートしたものをマージするということを再帰的に繰り返すアルゴリズム．
のはずだが，実装の都合上左からトーナメントのようなものを作りマージをしている．
見た目が一番奇麗．
時間計算量はO(n log n)


まとめ

ソートアルゴリズムを視覚化してみた．
クイックソートが後半遅いなどが見て取れて勉強になった．
また，予想よりも綺麗なものができてよかった．


似たようなことをpythonでやってる人もいるみたい．
http://corte.si//posts/code/visualisingsorting/index.html