[アルゴリズム] マージソートのプログラミング(解説)

2017年3月11日

テクノロジー プログラミング 特集

ソートアルゴリズムプログラミングの第5弾目になりますが、これもかなりメジャーなソートアルゴリズムである「マージソート」をコーディングしてみたいと思います。 簡単に言うと、ソートする数値配列を一度細かく分割していき、後半はそれらを大小比較しながらマージしていくやり方です。 すると最後に、全ての値でソートされているという結果になるんですね。

手順解説

1.(分解)数値郡(配列)を2分割ずつしていく

数値郡が端数の場合は、どちらかに含める

2.(分割)分割結果の配列が2つ以下になるまで繰り返す

3.(比較)数値をそれぞれ比較する(数の低い順にする)

4.(結合)比較した同士をくっつける

5.(結合)全ての分割された数字郡がひとつになるまで繰り返しつなげる

※この時、くっつけた状態での大小比較を行う

完了

図解

手順を図で書くと以下のようになります。

検討

このアルゴリズムで最初不思議に思ったのが、マージしていく課程でその中の値を全て処理しているので、いっその事、最初に2分割した状態でくっつける際にソートするだけではダメなのかと考えていたところ、 1対1にまで細分化する意味は、複数対複数という状態で左から小さい順になっているグループにしておくことで、比較処理を楽にしている事に気がついた。 確かに、バブルソートは考え方は楽だが、このマージソートの方が、高速に処理できるように思われる。

リンク

Wikipedia - https://ja.wikipedia.org/wiki/マージソート たくさんのプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。