エクセルの使い方
エクセルの使い方を覚えよう




マクロ集目次に戻る


エクセルマクロでアルゴリズムを学ぼう

[an error occurred while processing this directive]

マージソートの解説

マージソートの概要

マージソートのアルゴリズムでは以下のようなイメージで並べ替えを行っていきます(あくまでイメージなので、実際のアルゴリズムとは若干異なります)。

  1. まず左端から2つの値をとり、その2つを小さい順に並べ替えます
  2. 次に、その右隣の2つの値をとり、その2つを小さい順に並べ替えます
  3. 次に、1.と2.(合計で4つの値がありますね)を小さい順に並べかえます。
  4. 次に、3.の右隣の4つの数字を上記1、2、3、と同じ手順で並べ替えをします。
  5. 3.と4.(合計で8つの値がありますね)を小さい順に並べ替えます。

・・・という感じで全てを並べ替えていきます。「すでに並べ替えてある少ない個数の値を合体(マージ)して、より多い個数の値の並べ替える」ところからマージソートというふうに呼ばれます。

元の数値
5814 7326
ソート後
1234 5678


マージソートの具体的な手順

スポンサード リンク

マージソートを実際に行う際には、上のように左から2個ずつ選んでいくわけではなく、並べ替え対象となる値を左右均等に分割していくことによって、2個または1個のグループを作るところからスタートします。

マージソートのアルゴリズムを具体的に書くと、下記のようになります。

  1. まず、並べ替えの対象となる数値を、すべてのグループが1個または2個の数値からなるように左右均等に分割していきます。
  2. そして、その分割した結果の数値を小さい順に並べ替えます
  3. その並べ替え済みの2つのグループを持ってきて、それを小さい順に並べ替えます。
  4. さらに、その並べ替え済みの2つのグループを持ってきて、それを小さい順に並べ替えます。

・・・というアルゴリズムにより全てを並べ替えていきます。



マージソートの実際の様子

分割

まず、並べ替え対象となる数値全体を2つに分割していき、すべてのグループが1個または2個の数値からなるようにします。

分割前
5814 7326
グループ1
5814
グループ2
7326
グループ1−1
58
グループ1−2
14
グループ2−1
73
グループ2−2
26


次に、それぞれのグループ(1−1,1−2,2−1,2−2)の中でソートを行います。
グループ1−1
58
グループ1−2
14
グループ2−1
73
グループ2−2
26
58
14
37
26


さらに、より大きいグループ1,グループ2の中でソートを行います。
グループ1
58 14
グループ2
37 26
14 58
23 67

1巡目:2回目

全体でソートを行います。



全体
14 58 23 67
12 34 56 78


マージソートの特徴

スポンサード リンク

マージソートの特徴的なところとしては、下記のような点があります。

  • 数字の並び順に関係なく時間計算量は常にnlog(n)となる。
  • 時間計算量で見るとクイックソートよりも速く見えるが、処理のオーバーヘッドが大きいため、クイックソート等に比べて処理速度はやや遅め。
  • 普通にプログラムを組むと計算用の領域を大きくとる必要があり、空間計算量は大きくなる。




マージソートのエクセルマクロ

マージソートマクロのダウンロード

マージソートのダウンロードはこちらからどうぞ




マージソートマクロの使い方

  • ダウンロードしたエクセルファイルを開きます。
  • マクロを実行してもよいかどうかを聞くウィンドウが表示されますので、「はい」をえらびます。
  • 「Ctrl」と「Shift」を押したままで「M」のキーを押します。

これで、プログラムの実行が開始されます。



免責事項

このプログラムを実行したことによる一切の損害について責任は負いかねます。ご自身の責任でご利用ください。

マクロ集目次に戻る


「経理事務のためのエクセル基礎講座(初級編)」(動画マニュアル 総収録時間162分)を無料プレゼント中です!

このマニュアルで解説していることを一通り学べば、経理事務を行う上で最低限必要となる知識が得られます。

ご登録者の方には、合わせて、公認会計士が実体験を通して身に付けたエクセルを使う技をメールにてお伝えしていきます!

↓ 登録はこちら ↓
名字
名前
メールアドレス


 





姉妹サイト:
情報処理技術者試験対策   逆ポーランド記法  

[an error occurred while processing this directive]