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

Pocket
LINEで送る
GREE にシェア
LinkedIn にシェア

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

手順解説

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

スクリーンショット 2017-03-05 13.41.04
数値郡が端数の場合は、どちらかに含める

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

スクリーンショット 2017-03-05 13.41.25

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

スクリーンショット 2017-03-05 13.41.45

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

スクリーンショット 2017-03-05 13.41.51

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

スクリーンショット 2017-03-05 13.41.58
※この時、くっつけた状態での大小比較を行う

完了

スクリーンショット 2017-03-05 13.42.12

図解

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

スクリーンショット 2017-03-05 13.33.46

検討

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

リンク

Wikipedia – https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

マージソート記事

解説

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です