using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace ConsoleApplication1
{
    class Sort
    {
        public static double[] FileToDoubleArray(string s)
        {
            string[] s2 = File.ReadAllText(s).Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries);
            double[] d = new double[s2.Length];
            for (int i = 0; i < s2.Length; ++i)
            {
                d[i] = double.Parse(s2[i]);
            }
            return d;
        }
        public static string FirstSort(ref double[] a)
        {
            int j = 1;
            double x; 
            Stopwatch timer = new Stopwatch();
            timer.Start();
            for (int i; j < a.Length; ++j)
            {
                i = j - 1;
                x = a[j];
                for (; (i >= 0) && (x < a[i]); --i)
                    a[i + 1] = a[i];
                a[i + 1] = x;
            }
            timer.Stop();
            return timer.Elapsed.TotalMilliseconds.ToString();
        }
        public static void CheckSort(double[] d)
        {
            bool check = true;
            for (int i = 0; i < (d.Length - 1); ++i)
            {
                if (d[i] > d[i + 1])
                {
                    check = false;
                    break;
                }
            }
            Console.WriteLine();
            if (!check)
                throw new Exception("Сортировка произведена неправильно");
            Console.WriteLine("Сортировка верна");
        }
        public static string GetDesorder(string s)
        {
            Regex r0 = new Regex(@"[][0-9]{6}000[0-9]{2}");
            Regex r25 = new Regex(@"[][0-9]{6}025[0-9]{2}");
            Regex r50 = new Regex(@"[][0-9]{6}050[0-9]{2}");
            Regex r75 = new Regex(@"[][0-9]{6}075[0-9]{2}");
            Regex r100 = new Regex(@"[][0-9]{6}100[0-9]{2}");
            if (r0.IsMatch(s))
                return "0";
            if (r25.IsMatch(s))
                return "25";
            if (r50.IsMatch(s))
                return "50";
            if (r75.IsMatch(s))
                return "75";
            return "100";
        }
        public static string SecondSort(ref double[] a)
        {
            int N;
            List<double> ArrayForSort = new List<double>();
            foreach (double t in a)
                ArrayForSort.Add(t);
            int i = ArrayForSort.Count - 1;
            ArrayForSort.Add(ArrayForSort[i]);
            for (; i > 0; --i)
            {
                ArrayForSort[i] = ArrayForSort[i - 1];
            }
            ArrayForSort[0] = 1000000;
            N = ArrayForSort.Count - 1;
            for (i = 1; i <= N; ++i)
            { ArrayForSort.Add(100000); }
            Stopwatch timer = new Stopwatch();
            timer.Start();
            N2(ref ArrayForSort, N);
            timer.Stop();
            List<double> ArrayForSort2 = new List<double>();
            for (int p = 1; p <= N;++p )
            {
                ArrayForSort2.Add(ArrayForSort[p]);
            }
            ArrayForSort2.CopyTo(a);
            return timer.Elapsed.TotalMilliseconds.ToString();
        }
        private static void N2(ref List<double> K, int N)
        {
            bool s = true, f;
            int j, k, l, i, d;
            do
            {
                if (s)
                {
                    i = 1;
                    j = N;
                    k = N + 1;
                    l = 2 * N;
                }
                else
                {
                    k = 1;
                    l = N;
                    i = N + 1;
                    j = 2 * N;
                }
                d = 1;
                f = false;
            a:
                if (K[i] <= K[j])
                {
                    if (i == j)
                    {
                        K[k] = K[i];
                        s = !s;
                        continue;
                    }
                    K[k] = K[i];
                    k += d;
                    i++;
                    if (K[i - 1] <= K[i])
                        goto a;
                    do
                    {
                        K[k] = K[j];
                        k += d;
                        j = j - 1;
                    }
                    while (K[j + 1] <= K[j]);
                }
                else
                {
                    K[k] = K[j];
                    k += d;
                    j--;
                    if (K[j + 1] <= K[j])
                        goto a;
                    do
                    {
                        K[k] = K[i];
                        k += d;
                        i++;
                    }
                    while (K[i - 1] <= K[i]);
                }
            f = true;
            d = -d;
            k += l;
            l = k - l;
            k -= l;
            goto a;
            } while (f);
            if (!s) 
            {
                for (int h = 1; h <= N; ++h) 
                {
                    K[h] = K[N + h];
                }
            }
        }
        public static string ThirdSort(ref double[] a) 
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Array.Sort(a);
            timer.Stop();
            return timer.Elapsed.TotalMilliseconds.ToString();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                string[] Files = Directory.GetFiles(@"d:\Артем\new_files_1\1 пик");
                File.AppendAllText(@"d:\Сортировка.xls", "\nSort 1" + "\n" + "Variant" + "\t" + "Elements" + "\t" + "% of chaos" + "\t" + "Time,mks");
                for (int f = 0; f < Files.Length; ++f)
                {
                    double[] figures = Sort.FileToDoubleArray(Files[f]);
                    string time = Sort.FirstSort(ref figures);
                    Sort.CheckSort(figures);
                    string Out = "\n" + Files[f][Files[f].Length - 5].ToString() + "\t" + figures.Length + "\t" + Sort.GetDesorder(Files[f]) + "\t" + time;
                    File.AppendAllText(@"d:\Сортировка.xls", Out);

                }
              File.AppendAllText(@"d:\Сортировка.xls", "\nSort 2" + "\n" + "Variant" + "\t" + "Elements" + "\t" + "% of chaos" + "\t" + "Time,mks");
                for (int f = 0; f < Files.Length; ++f)
                {
                    double[] figures = Sort.FileToDoubleArray(Files[f]);
                    string time = Sort.SecondSort(ref figures); 
                    Sort.CheckSort(figures);
                    string Out = "\n" + Files[f][Files[f].Length - 5].ToString() + "\t" + figures.Length + "\t" + Sort.GetDesorder(Files[f]) + "\t" + time;
                    File.AppendAllText(@"d:\Сортировка.xls", Out);

                }
                File.AppendAllText(@"d:\Сортировка.xls", "\nSort 3" + "\n" + "Variant" + "\t" + "Elements" + "\t" + "% of chaos" + "\t" + "Time,mks");
                for (int f = 0; f < Files.Length; ++f)
                {
                    double[] figures = Sort.FileToDoubleArray(Files[f]);
                    string time = Sort.ThirdSort(ref figures); 
                    Sort.CheckSort(figures);
                    string Out = "\n" + Files[f][Files[f].Length - 5].ToString() + "\t" + figures.Length + "\t" + Sort.GetDesorder(Files[f]) + "\t" + time;
                    File.AppendAllText(@"d:\Сортировка.xls", Out);

                }
                Console.WriteLine("А программка то завершилась");
            }
            catch (Exception e) { Console.WriteLine(e.Message); }
        }




    }
}


