using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ConsoleApplication9
{
    class Program
    {
        static Stopwatch timerQS = new Stopwatch();
        static Stopwatch timerMS = new Stopwatch();
        static Stopwatch timerIS = new Stopwatch();
        static Stopwatch timerHS = new Stopwatch();
        static Stopwatch calosc = new Stopwatch();
        static double[,] czasQS = new double[8,5];
        static double[,] czasMS = new double[8,5];
        static double[,] czasIS = new double[8,5];
        static double[,] czasHS = new double[8,5];
        static int[] rozmiar = { 10000, 50000, 100000, 500000, 1000000 };
        static float[] procent = { 0f, 0.25f, 0.5f, 0.75f, 0.95f, 0.99f, 0.997f, -1f };
        static void Main(string[] args)
        {
            calosc.Start();

            int IloscProb = 100;
            for (int k = 0; k < procent.Count(); k++)
                for (int i = 0; i < rozmiar.Count(); i++)
                {

                    for (int j = 0; j < IloscProb; j++)
                    {
                        ToSort QS = new ToSort(rozmiar[i], procent[k]);
                        ToSort MS = new ToSort(QS);
                        ToSort IS = new ToSort(QS);
                        ToSort HS = new ToSort(QS);

                        timerMS.Reset();
                        timerMS.Start();
                        MS.MergeSort();
                        timerMS.Stop();
                        czasMS[k,i] += timerMS.ElapsedMilliseconds;


                        timerQS.Reset();
                        timerQS.Start();
                        QS.QuickSort();
                        timerQS.Stop();
                        czasQS[k,i] += timerQS.ElapsedMilliseconds;

                        timerIS.Reset();
                        timerIS.Start();
                        IS.IntroSort();
                        timerIS.Stop();
                        czasIS[k,i] += timerIS.ElapsedMilliseconds;

                        timerHS.Reset();
                        timerHS.Start();
                        HS.HeapSort();
                        timerHS.Stop();
                        czasHS[k,i] += timerHS.ElapsedMilliseconds;
                    }
                    czasQS[k,i] = czasQS[k,i] / IloscProb;
                    czasMS[k,i] = czasMS[k,i] / IloscProb;
                    czasIS[k,i] = czasIS[k,i] / IloscProb;
                    czasHS[k,i] = czasHS[k,i] / IloscProb;
                    Console.WriteLine("Sredni czas MergeSort o rozmiarze {0} i posortowaniu {2:P2}: {1:F4} ms.", rozmiar[i], czasMS[k,i], procent[k]);
                    Console.WriteLine("Średni czas QuickSort o rozmiarze {0} i posortowaniu {2:P2}: {1:F4} ms.", rozmiar[i], czasQS[k,i], procent[k]);
                    Console.WriteLine("Średni czas IntroSort o rozmiarze {0} i posortowaniu {2:P2}: {1:F4} ms.", rozmiar[i], czasIS[k,i], procent[k]);
                    Console.WriteLine("Średni czas HeapSort  o rozmiarze {0} i posortowaniu {2:P2}: {1:F4} ms.\n\n", rozmiar[i], czasHS[k,i], procent[k]);

                }
            SaveFile("kek");
            calosc.Stop();
            Console.WriteLine(calosc.Elapsed + "s");
            Console.ReadKey();
        }

        static public void SaveFile(string fileName)
        {
            System.IO.StreamWriter file = new System.IO.StreamWriter(fileName + ".txt",false);
            for (int i = 0; i < procent.Count(); i++)
            {
                file.WriteLine(procent[i]);
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < rozmiar.Count(); j++)
                {
                    sb.Append(rozmiar[j] + " " + czasMS[i,j] + " " + czasQS[i,j] + " " + czasIS[i,j] + " " + czasHS[i,j]+"\n");
                }
                file.WriteLine(sb);
                file.WriteLine();
            }
            file.Close();
            Console.WriteLine("Udany zapis do pliku");
        }
    }
    class ToSort
    {
        #region Wspolne Podstawy Klasy
        public static Random r = new Random();
        public int[] tablica;
        public int rozmiar;
        int[] temp;
        float ilePosortowanych;
        int j = 0;
        public ToSort(ToSort ts)
        {
            this.rozmiar = ts.rozmiar;
            tablica = new int[rozmiar];
            Array.Copy(ts.tablica, tablica,rozmiar);

        }

        public ToSort(int rozm, float procent)
        {
            rozmiar = rozm;
            ilePosortowanych = procent;
            tablica = new int[rozmiar];
            WypelnijTablice();
        }


        void WypelnijTablice()
        {
            for (j = 0; j < rozmiar; j++)
                tablica[j] = r.Next(21);
            if(ilePosortowanych>0)
                Array.Sort(tablica, 0, (int)(ilePosortowanych * rozmiar));
            if(ilePosortowanych<0)
                Array.Sort(tablica,new Comparison<int>((i1,i2)=>i2.CompareTo(i1)));
        }
        public void Print()
        {
            Console.WriteLine("\n");
            foreach (int i in tablica)
                Console.Write(String.Format("{0,4}", i));
            Console.WriteLine("\n");
        }
#endregion
        private static int whiler = 0;
        private static int heaper = 0;
        #region QuickSort
        public void QuickSort()
        {
            QuickSort(0, rozmiar - 1);
        }

        public void QuickSort(int p, int o)
        {
            int i = p;
            int j = o;
            int pivot = tablica[(i + j) / 2];
            while (i < j)
            {
                while (tablica[i] < pivot) i++;
                while (tablica[j] > pivot) j--;
                if (i <= j)
                    Swap(i++, j--);
            }
            if (p < j) QuickSort(p, j);
            if (i < o) QuickSort(i, o);

        }
        void Swap(int p, int o)
        {
            int temp = tablica[p];
            tablica[p] = tablica[o];
            tablica[o] = temp;
        }
        #endregion
        #region MergeSort
        public void MergeSort()
        {
            temp = new int[rozmiar];
            MergeSort(0, rozmiar - 1);
        }
        void MergeSort(int p, int o)
        {
            if (p < o)
            {
                int srodek = (p + o) / 2;
                MergeSort(p, srodek);
                MergeSort(srodek+1, o);
                Merge(p, srodek, o);
            }
        }
        void Merge(int p, int s, int o)
        {
            for (int k = p; k <= o; k++)
                temp[k] = tablica[k];

            int i = p;
            int j = s + 1;
            int r = p;

            while (i <= s && j <= o)
            {
                if (temp[i] < temp[j])
                    tablica[r++] = temp[i++];
                else
                    tablica[r++] = temp[j++];
            }
            while (i <= s)
                tablica[r++] = temp[i++];
        }
        #endregion
        #region IntroSort
        public void IntroSort()
        {
            Intro_Sort(0, rozmiar-1, Convert.ToInt16(2*Math.Floor(Math.Log(rozmiar)/Math.Log(2))));
            InsertionSort(0, rozmiar - 1);
        }
        void Intro_Sort(int p, int o, int limit)
        {
            while(o-p >= 16)
            {
                //Console.WriteLine("W while {0}",limit);
                int i;

                if (limit <= 0)
                {
                    Console.WriteLine("W heap {0}", ++heaper);
                    HeapSort(p, o);
                    return;
                }
                i = Partition(p, o);
                limit--;
                Intro_Sort(i, o, limit);
                o = i;
            }
        }
        int Partition(int p, int o)
        {
            int i = p;
            int j = o;
            int pivot = tablica[(i + j) / 2];
            while (true)
            {
                while (tablica[i] < pivot) i++;
                j--;
                while (tablica[j] > pivot) j--;
                if (!(i < j))
                    return i;
                Swap(i, j);
                i++;
            }

        }

        public void HeapSort()
        {
            HeapSort(0, rozmiar - 1);
        }

        void HeapSort(int p, int o)
        {
            for (int i = o/2; i >= 0; i--)
            {
                Heapify(i,rozmiar-1);
            }
            for (int i = o-2; i >=0; i--)
            {
                Swap(0, i+1);
                Heapify(0, i);
            }
        }
        void Heapify(int p,int o)
        {
          //  Print();
            int temp = tablica[p];
            int j = 2 * p;
            while (j <= o)
            {
                if (j < o && tablica[j] < tablica[j + 1]) j++;
                if (temp >= tablica[j])
                    break;
                tablica[j / 2] = tablica[j];
                j = j * 2;
            }
            tablica[j / 2] = temp;
        }
        void InsertionSort(int p, int o)
        {
            int j, value;
            for (int i = 1; i < rozmiar; i++)
            {
                j = i;
                value = tablica[i];
                while ((j > 0) && (tablica[j - 1]) > value)
                {
                    tablica[j] = tablica[--j];
                }
                tablica[j] = value;
            }
        }
        #endregion
    }
}