読者です 読者をやめる 読者になる 読者になる

(O+P)ut

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

マージソートの可視化

テクノロジー R アルゴリズム

ちょうと1年前くらいに
mti.hatenablog.com
といった記事を書いたんですが、そこでは選択ソートとバブルソートを可視化しました。

今回はマージソートの可視化を行います。使用するのも前回同様 R言語で。

マージソートとは、並べ替えたい配列を再帰的に分割していき、再び併合(マージ)していくことで並び替えを実現しようとするソートアルゴリズムです。

今回は配列を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につっこむ流れですね。*1

分割の回数で上記のマージソートを可視化したものが以下になります。
f:id:mtiit:20161103103618g:plain
一秒毎に8回目までのソートの経過を可視化しました。選択ソートやバブルソートとは全く異なっていることが分かります。


おまけとして、pivotを

pivot_t=ave(x[1:2])[[1]]

とすればどうなるでしょう。直観的には、基準が前の二つの平均値となるので少し偏ったpivotで配列を分割していくことになりそうです。
同じく8回目までのソートの経過を可視化したものが以下になります。
f:id:mtiit:20161103104419g:plain
8回だけでは並べ替えきれていない感じがします。

以上、マージソートの可視化でした。*2

*1:countは配列の結合で用いる配列の引数としてfに渡してました

*2:分割と併合を繰り返したものの経過の可視化はマージソートWikipediaにも掲載されていましたのでご参考まで