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

nekoTheShadow’s diary

技術ブログとして始めたはずが、読書&愚痴ブログになりました(´・ω・`)

「マージ」に関する個人的な誤解(超低レベル編)。

 自分の恥をさらすと、ごくごく最近まで「マージ」を単に配列を前後に結合することだと思っていました……。

[1,2] + [3,4,5] => [1,2,3,4,5]

 このせいで「マージソート」なるものがさっぱり理解できず、ずいぶんと長い間学習を放棄していました……。個人的に再帰がものすごく苦手(というか、どこでどう使うのかがいまだによくわかっていない)ということもあり、逃げ回っていたということもあります。

 が、最近偶然読んでいた本でマージの本当の意味を会得。ばかばかしいですが、個人的にはかなりの大発見なので、記事として公開しておきます。

 もちろん「マージ」とはふたつの配列を単につなぎ合わせることではありません。「ふたつの配列の先頭を見比べ、小さいものを取り出して、別に用意した配列に追加していく」これこそが真の「マージ」です。したがって、ひとつの配列を極限までばらばらにしたのちにマージしていけば、最終的にはソートされた配列があらわれるはず――これでやっと「マージソート」が理解できます!

 なおこの手の説明はWikipedia「マージ」Wikipedia「マージソート」がもっともわかりやすかったと思います。

 とりあえず理解できたところで、実際に実装していきます。まずRuby

 書きやすく読みやすいコードが書けました(そのはず)。

 次に最近お勉強中のC言語――といきたいところですが、途中で挫折。やはりCは配列周りがややこしい! 結局逃げてC++を使いました。std::vectorは本当に便利ですね。

 メモリ? 解放? 知らない子ですね。ガベージコレクション万歳!