少しでも分かりやすく伝えたいマージソート

少しでも分かりやすく伝えたいマージソート

こんにちは、しゃねろんです。
今回はマージソートについて説明していきたいと思います!

マージソートとは

マージソートの前に「分割統治法」の説明を行います。
分割統治法は、一つの大きな問題を分割して問題を小分けにしてからそれぞれを解いていき、最終的に大きな問題を解決する手法の事を言います。

極端な例ですが、
「17 + 22 + 34 + 73」のような式を
「17 + 22」と「34 + 73」のように分けてそれぞれ計算すれば計算が楽になるよねっていうことです。

マージソートはその「分割統治法」の一例なんです。

マージソートのやり方

と、いうことで早速マージソートのソートの手順について説明していきます!

1.データを用意する

まずはソートするデータを用意します。

ソートするデータを用意する

今回は上のようなデータを用意しました。このデータを基にソートを行っていきます!

2.データを分割する

マージソートを行うにはまずデータを分ける必要があります。
マージソートでのデータ分割は半分に分けていくので、半分ずつに分けていきます。

データを2分割する

半分に分けて要素数が「4」のデータが2つ出来ました。
これを要素数が1になるまで分割していった結果が下の画像になります。

2分割を続けていく

さて、この後からデータの比較を行いソートを行っていきます。

3.データの比較を行いソートを行う

データの比較は2つのまとまりごとにデータの比較を行っていきます。
今回用いたデータの場合では、「6と5」「13と8」「3と7」「18と2」で比較を行います。

大小の比較を行い、ソートを行う

まず「6と5」の比較ですが、「5 < 6」なので「5」が前に、「6」が後ろになるようにソートが行われます。
この時、この2つの要素はソート済みになっているのでデータをくっつけてしまいます。

他のデータも比較し、ソートする

これと同じ動作を他の値もやっていくと上の画像のようになります。

次も先ほどと同様に2つのまとまりごとにデータの比較を行い、ソートを行います。
しかし、今回は1つのまとまりに2つのデータが入っていますね。
その場合はそれぞれの一番左側のデータ同士を比較し小さい方から順にデータを格納していきます。

まず最初は「5と8」の比較になります。

4つのデータの比較1

「5 < 8」なので「5」が一番左に格納されます。
次に「8」が格納される...のではなく「6と8」の比較が行われます。ここが肝です。
マージソートは2つのまとまりごとにデータの比較を行いソートするものなので、「5」がなくなれば次の「6」と比較を行うのです。

4つのデータの比較2

勿論そうなれば「6 < 8」なので、「6」が先に格納されます。

4つのデータの比較3

先に片方のデータが全て格納されてしまい、比較対象がなくなったので残りのデータである「8と13」はそのまま格納されます。「8と13」はソート済みなのでわざわざ比較する必要はありません。

4つのデータの比較(別の値)

もう片方も同様にデータの比較とソートを行うと上の画像のようになります。

最後も同じように要素数が4同士のデータを比較してソートしていきます。

8つのデータの比較

少し見た目がアレですが、最終的には上の画像のようになりソートが完了します。

まとめ

今回はマージソートについて説明してきました。
マージソートを一言で言うと、「要素数が1になるまで分けてからソートを行う」です。
基本情報技術者試験にも出るような内容なのでぜひ覚えておいてください!

テーマ

現在使用中テーマは最新版

v.1.0v.2.0v.3.0v.3.1v.3.2v.3.3v.3.4v.3.5v.3.6v.3.7v.3.8v.shaneron選択しない(安定版)