マージソート

アルゴリズム
マージソート
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。

n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースな(すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない)バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする[1]。

(ナイーブな)クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。


2分割していき、1つになるまで再帰する。
その後、それぞれマージしていくことでソートした塊を作り
ソートした者同士をさらにマージしていき、一つのデータにマージしていく。

例)
6,1,4,5,2,7,3

[6,1,4,5][2,7,3] 4個と3個にわける

[[6,1],[4,5]][[2,7],[3]] それぞれさらに分割する

1個または2個に分割できたのでそれぞれ並びかえる
[[6,1],[4,5]][[2,7],[3]]

[[[6],[1]],[[4],[5]][[2],[7]],[3]]

[[6],[1]] と[[4],[5]]と[[2],[7]]のそれぞれの小さい要素を比較し、小さい値を取り出すマージしていく
[[1,[6]],[4,[5]],[2,[7]],[3]]
[[1,6],[4,5]],[[2,7],[3]]

[[1,6],[4,5]]と[[2,7],[3]]のそれぞれの小さい要素を比較し、小さい値を取り出しマージしていく
[1,[6],[4,5]],[2,[7],[3]]
[1,4[6],[5]],[2,3,[7]]
[1,4,5,[6]],[2,3,7]
[1,4,5,6],[2,3,7]

[1,4,5,6]と[2,3,7]のそれぞれの小さい要素を比較し、小さい値を取り出しマージしていく
[1,4,5,6],[2,3,7]
1,[4,5,6],[2,3,7]
1,2,[4,5,6],[3,7]
1,2,3,[4,5,6],[7]
1,2,3,4,[5,6],[7]
1,2,3,4,5,[6],[7]
1,2,3,4,5,6,[7]
1,2,3,4,5,6,7


サンプルコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Markup;

namespace SampleCode
{
    class Program
    {
        static void Main(string[] args)
        {
            // 20までの数字を生成しシャッフルする
            var data = Program.GenerateData(20);

            // Sort前
            Console.WriteLine(string.Join(',', data));

            // Mergeソート
            Program.MergeSort(data, 0, data.Count -1);

            // Sort後
            Console.WriteLine(string.Join(',', data));
        }

        static void MergeSort(List<int> data, int left, int right)
        {

            if(right - left < 1) { return; }

            var mid = (left + right) / 2;
            MergeSort(data, left, mid);
            MergeSort(data, mid + 1, right);

            // Merge
            Merge(data, left, mid, right);
        }

        static void Merge(List<int> data, int left, int mid, int right)
        {
            // 一時格納領域
            var temp = new List<int>();
            var l = left;
            var r = mid + 1;
            var lmax = mid;
            var rmax = right;
            while (l <= lmax || r <= rmax) 
            {
                if(l <= lmax && r <= rmax)
                {
                    if(data[l] < data[r])
                    {
                        temp.Add(data[l++]);
                    }
                    else
                    {
                        temp.Add(data[r++]);
                    }
                }
                else if(l <= lmax)
                {
                    temp.Add(data[l++]);
                }
                else if(r <= rmax)
                {
                    temp.Add(data[r++]);
                }
            }

            temp.ForEach(v => data[left++] = v);
        }

        /// <summary>
        /// 任意の1〜nまでのリストを生成し、Fisher-Yatesシャッフルしたものを返す
        /// </summary>
        /// <param name="maxNumber"></param>
        /// <returns>1〜任意の数字までのシャッフルされたリスト</returns>
        static List<int> GenerateData(int maxNumber)
        {
            // 1未満の場合は空のリストを返す
            if (maxNumber < 1) { new List<int>(); }

            // 1から任意の数字までのリストを生成
            var num = Enumerable.Range(1, maxNumber).ToList<int>();

            // シャッフル
            Random r = new Random();
            for (var i = num.Count() - 1; 0 < i; i--)
            {
                var rand = r.Next(i);

                // 乱数が最大値と同じ時、シャッフル元とシャッフル先が同一となるため何もしない
                if (rand == i) { continue; }

                var temp = num[i];
                num[i] = num[rand];
                num[rand] = temp;
            }

            return num;
        }
    }
}

投稿日時: 2020-08-15 00:14:15
更新日時: 2020-08-15 02:39:15
挿入ソート | マージソート

Comment