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

namespace ConsoleApplication1 {
    class Program {
        static void Main(string[] args) {
            int[] tokuda = { 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 68178, 153401, 345152, 776591 };
            int[] s248 = { 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, 54128, 134237, 332908, 825611 };
            int[] sizes = {10000, 50000, 100000, 200000, 300000, 500000, 1000000};

            string csv = "";
            foreach(int size in sizes) {
                // foreach size, try 100 times.
                for (int k = 0; k < 100; k++) {
                    int[] list = new int[size];
                    Random rnd = new Random();

                    for (int i = 0; i < list.Length; i++) {
                        list[i] = rnd.Next(0, Int32.MaxValue);
                    }

                    int[] tmp = (int[])list.Clone();
                    int c = shellsort(tmp, tokuda);

                    // Writing the CSV in the following format
                    //  Size of Array, Tokuda's comparison, Tokuda's swap
                    csv += size + "," + c + "," + swap;
                    tmp = (int[])list.Clone();

                    c = shellsort(tmp, s248);
                    csv += "," + c + "," + swap + "\n";
                }
            }

            System.IO.File.WriteAllText("result.csv", csv);
        }

        public static int compare = 0;
        public static int swap = 0;

        public static bool greaterthan(int a, int b) {
            compare++;
            return a > b;
        }

        public static int shellsort(int[] a, int[] gaps) {
            // For keeping track of number of swap and comparison
            compare = 0;
            swap = 0;

            int temp, gap, i, j;

            // Finding a gap that is smaller than the length of the array
            int gap_index = gaps.Length - 1;
            while (gaps[gap_index] > a.Length) gap_index--;

            while (gap_index >= 0) {

                // h-sorting
                gap = gaps[gap_index];
                for (i = gap; i < a.Length; i++) {
                    temp = a[i];
                    for(j = i; (j >= gap) && (greaterthan(a[j - gap], temp)); j -= gap) {
                        a[j] = a[j - gap];
                        swap++;
                    }

                    // swapping
                    a[j] = temp;
                    swap++;
                }

                gap_index--;
            }

            return compare;
        }
    }
}