ALDS1_2_D: Shell Sort

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q006 シェルソート https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("5");
            WillReturn.Add("1");
            WillReturn.Add("4");
            WillReturn.Add("3");
            WillReturn.Add("2");
            //2
            //4 1
            //3
            //1
            //2
            //3
            //4
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("3");
            WillReturn.Add("2");
            WillReturn.Add("1");
            //1
            //1
            //3
            //1
            //2
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList.Skip(1).Select(pX => int.Parse(pX)).ToArray();
        ShellSort(AArr);
    }

    static int mCnt = 0;

    static void ShellSort(int[] pArr)
    {
        var GapList = new List<int>();
        GapList.Add(1);
        while (true) {
            int LastVal = GapList[GapList.Count - 1];
            int NextVal = 3 * LastVal + 1;
            if (pArr.Length < NextVal) break;
            GapList.Add(NextVal);
        }
        GapList.Reverse();

        // Gapの配列
        Console.WriteLine(GapList.Count);

        for (int I = 0; I <= GapList.Count - 1; I++) {
            Console.Write(GapList[I]);
            if (I < GapList.Count - 1) Console.Write(" ");
        }
        Console.WriteLine();

        // シュルソートを行う
        GapList.ForEach(pX => InsertionSort(pArr, pX));

        Console.WriteLine(mCnt); // 合計の交換回数

        // ソート後の配列
        Array.ForEach(pArr, pX => Console.WriteLine(pX));
    }

    static void InsertionSort(int[] pArr, int pGap)
    {
        for (int I = pGap; I <= pArr.GetUpperBound(0); I++) {
            int V = pArr[I];
            int J = I - pGap;
            while (J >= 0 && pArr[J] > V) {
                pArr[J + pGap] = pArr[J];
                J -= pGap;
                mCnt++;
            }
            pArr[J + pGap] = V;
        }
    }
}

解説

漸化式
A(1) = 1
A(n+1) = A(n) * 3 + 1
で間隔を求めてます。

なお漸化式を
A(n+1) + 1/2 = 3 * (A(n) + 1/2) に変形して
B(n) = A(n) + 1/2 とおけば
B(n) は 初項 3/2 公比 3 の等比数列なので

B(n) = 3/2 * 3の(n-1)乗 = 1/2 * 3のn乗
A(n) = 1/2 * 3のn乗 - 1/2
     = (3のn乗 - 1) / 2
なので
A(n) の 一般項は、(3のn乗 - 1) / 2 となります。