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

ALDS1_5_B Merge Sortを解く話

AOJのマージソートを実装する問題です.

 

特徴

・分割統治と再帰を上手く使ったソーティングアルゴリズム

・配列を1要素になるまで分割してくっつき直すときに比較.

 

アルゴリズム

Mergesort(array, left, right)

  1. 素数が1ならソート済みなのでreturn.(実装では left + 1 < right)
  2. 配列を半分にする.
  3. 左半分をMergesortに渡す(実装では再帰を使う).
  4. 右半分をMergesortに渡す(同じく再帰).
  5. マージ.

 

計算量

マージがn回,分割が log(n) 回なので計算量は O(nlog(n))

 

実装

分割した配列の末尾に番兵を配置するのに注意.

gist46eccdb4e29c4cc01cc448b894cf8814

 

感想

マージソートに対する僕のイメージは全結合していないニューラルネット

  1. 入力層にこれからソートする配列を渡す.
  2. 層を進むにつれて配列は分割され次の層へ.
  3. 一番真ん中の層が配列が1要素数になるまで分割された状態.
  4. この後の層では比較とマージをする.

てな感じ.これで覚えておけばそらで書けるかな.