少しでも分かりやすく伝えたいマージソート
皆さんこんにちは！！
今回はマージソートについて説明していきたいと思います！
マージソートとは
マージソートの前に「分割統治法」の説明を行います。
分割統治法は、一つの大きな問題を分割して問題を小分けにしてからそれぞれを解いていき、最終的に大きな問題を解決する手法の事を言います。
極端な例ですが、
「17 + 22 + 34 + 73」のような式を
「17 + 22」と「34 + 73」のように分けてそれぞれ計算すれば計算が楽になるよねっていうことです。
マージソートはその「分割統治法」の一例なんです。
マージソートのやり方
と、いうことで早速マージソートのソートの手順について説明していきます！
1.データを用意する
まずはソートするデータを用意します。
今回は上のようなデータを用意しました。このデータを基にソートを行っていきます！
2.データを分割する
マージソートを行うにはまずデータを分ける必要があります。
マージソートでのデータ分割は半分に分けていくので、半分ずつに分けていきます。
半分に分けて要素数が「4」のデータが2つ出来ました。
これを要素数が1になるまで分割していった結果が下の画像になります。
さて、この後からデータの比較を行いソートを行っていきます。
3.データの比較を行いソートを行う
データの比較は2つのまとまりごとにデータの比較を行っていきます。
今回用いたデータの場合では、「6と5」「13と8」「3と7」「18と2」で比較を行います。
まず「6と5」の比較ですが、「5 < 6」なので「5」が前に、「6」が後ろになるようにソートが行われます。
この時、この2つの要素はソート済みになっているのでデータをくっつけてしまいます。
これと同じ動作を他の値もやっていくと上の画像のようになります。
次も先ほどと同様に2つのまとまりごとにデータの比較を行い、ソートを行います。
しかし、今回は1つのまとまりに2つのデータが入っていますね。
その場合はそれぞれの一番左側のデータ同士を比較し小さい方から順にデータを格納していきます。
まず最初は「5と8」の比較になります。
「5 < 8」なので「5」が一番左に格納されます。
次に「8」が格納される…のではなく「6と8」の比較が行われます。ここが肝です。
マージソートは2つのまとまりごとにデータの比較を行いソートするものなので、「5」がなくなれば次の「6」と比較を行うのです。
勿論そうなれば「6 < 8」なので、「6」が先に格納されます。
先に片方のデータが全て格納されてしまい、比較対象がなくなったので残りのデータである「8と13」はそのまま格納されます。「8と13」はソート済みなのでわざわざ比較する必要はありません。
もう片方も同様にデータの比較とソートを行うと上の画像のようになります。
最後も同じように要素数が4同士のデータを比較してソートしていきます。
少し見た目が良くないですが、最終的には上の画像のようになりソートが完了します。
まとめ
マージソートを一言で言うと、「要素数が1になるまで分けてからソートを行う」です。
基本情報技術者試験にも出るような内容なのでぜひ覚えておいてください！