【C#】シェルソートを実装してみる - はなちるのマイノート

はじめに

少し前に挿入ソートを実装してみました。
https://www.hanachiru-blog.com/entry/2020/07/30/180000www.hanachiru-blog.com

この挿入ソートをより高速化するために生まれたのが今回紹介するシェルソートになります。
ja.wikipedia.org

早速みていきましょう。

はじめに
シェルソート
実装
使い方
考察

シェルソート

ソートアルゴリズムは動画の方が視覚的に分かりやすい気がします。
www.youtube.com

実装

/// <summary>
/// シェルソート
/// </summary>
public static T[] ShellSort<T>(IEnumerable<T> items) where T : IComparable<T>
{
    var nums = items.ToArray();
    var n = nums.Length;

    int h = n / 2;

    while (h > 0)
    {
        // 挿入ソート
        for (int i = h; i < n; i++)
        {
            var a = nums[i];
            var k = i;

            while (k >= h && a.CompareTo(nums[k - h]) < 0)
            {
                nums[k] = nums[k - h];
                k -= h;
            }

            nums[k] = a;
        }

        // 間隔hを更新
        h = h / 2;
    }

    return nums;
}

使い方

static void Main(string[] args)
{
    var a = new int[] { 170, 45, 75, 90, 2, 24, 802, 66 };

    foreach (var item in ShellSort<int>(a))
        Console.WriteLine(item);       // 2, 24, 45, 66, 75, 90, 170, 802
}