はじめに
ちょうと1年前くらいに
www.mtioutput.com
といった記事を書きました。タイトルの通り、選択ソートとバブルソートを可視化しました。
マージソートの可視化
準備
マージソートとは、
1. 配列を適当な長さでぶつ切りにする
2. それぞれをソートする。再帰でもいいし別のアルゴリズムでもいい
3. できた配列を混ぜる
今回は配列をx、マージソート関数をf、基準値をpivotとし、基準値は配列xの平均値とします。
pivot=ave(x)[[1]]
実装
配列xの各値が基準(pivot)より大きいか小さいかで配列をleft,rightに分割
for(k in 1:length(x)) { if(x[k] <= pivot) { left <- append(left,x[k]) count <- count + 1 } else { right <- append(right,x[k]) } }
分割したleft、rightを再起的にまたfにつっこむ流れにしました。
countは配列の結合で用いる配列の引数としてfに渡しています。
分割の回数で上記のマージソートを可視化したものが以下になります。
一秒毎に8回目までのソートの経過を可視化しました。選択ソートやバブルソートとは全く異なっていることが分かります。