ほぼC#だけのぶろぐ

マージソート

アルゴリズム
マージソート
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を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

挿入ソート

アルゴリズム
挿入ソート
挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。

挿入ソートを高速化したソート法として、シェルソートが知られている。


2番目以降の要素がそれより前のソート済みのリストを
一要素ずつさかのぼっていき、昇順になるまで入れ替えていく

例)
4,5,2,3,1

5を4(ソート済み)と比較し昇順になるよう入れ替えていく

4,5,2,3,1

2を4,5(ソート済み)と比較し昇順になるよう入れ替えていく
4,5,2,3,1

4,2,5,3,1

2,4,5,3,1

3を2,4,5(ソート済み)と比較し昇順になるよう入れ替えていく
2,4,5,3,1

2,4,3,5,1

2,3,4,5,1

1を2,3,4,5(ソート済み)と比較し昇順になるよう入れ替えていく
2,3,4,5,1

2,3,4,1,5

2,3,1,4,5

2,1,3,4,5

1,2,3,4,5

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

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

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

            // 挿入ソート
            Program.InsertSort(data);

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

        static void InsertSort(List<int>data)
        {
            if(data.Count == 0) { return; }

            for(var i = 1; i < data.Count; i++)
            {
                var index = i;
                for(var j = i - 1; -1 < j; j--)
                {

                    if(data[index] < data[j])
                    {
                        var temp = data[j];
                        data[j] = data[index];
                        data[index] = temp;
                        index--;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        /// <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-14 15:24:14
更新日時: 2020-08-14 15:29:14

選択ソート

アルゴリズム
選択ソート
選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。


最小値を探しだし、走査した最初の要素と置き換え、
範囲を一つ小さくして同じ処理の繰り返しを行う

例)
2,3,5,1,4の場合

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える


-------

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える


-------

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える


-------

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える



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

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

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

            // 選択ソート
            Program.SelectionSort(data);

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

        static void SelectionSort(List<int> data)
        {
            // データが0個なら終了
            if (data.Count == 0) { return; }

            // 未ソート領域の範囲を1つずつ狭めていく
            for (var i = 0; i < data.Count - 1; i++)
            {
                // 最小値の要素番号を取得
                // 最初の要素番号を基準値にする
                var minIndex = i;
                for (var j = i + 1; j < data.Count; j++)
                {
                    // より小さな値があればIndexを入れ替える
                    if (data[j] < data[minIndex]) { minIndex = j; }
                }

                // 最小値が先頭の場合入れ替え作業は不要
                if (i == minIndex)
                {
                    continue;
                }
                else
                {
                    // 未ソート領域の先頭要素と入れ替える
                    (data[i], data[minIndex]) = (data[minIndex], data[i]);
                }
            }
        }

        /// <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; }

                (num[i], num[rand]) = (num[rand], num[i]);
            }

            return num;
        }
    }
}

投稿日時: 2020-08-14 14:55:14
更新日時: 2020-08-16 14:48:16
PrePage | NextPage