挿入ソート

アルゴリズム
挿入ソート
挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともに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
Q01 10進数で回文 | 挿入ソート

Comment