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

namespace TestNums
{
    class Program
    {
        //метод обмена элементов
        static void Swap(ref int e1, ref int e2)
        {
            var temp = e1;
            e1 = e2;
            e2 = temp;
        }

        //сортировка пузырьком
        static int[] BubbleSort(int[] array)
        {
            var len = array.Length;
            for (var i = 1; i < len; i++)
            {
                for (var j = 0; j < len - i; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                    }
                }
            }

            return array;
        }

        //сортировка перемешиванием
        static int[] ShakerSort(int[] array)
        {
            for (var i = 0; i < array.Length / 2; i++)
            {
                var swapFlag = false;
                //проход слева направо
                for (var j = i; j < array.Length - i - 1; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        Swap(ref array[j], ref array[j + 1]);
                        swapFlag = true;
                    }
                }

                //проход справа налево
                for (var j = array.Length - 2 - i; j > i; j--)
                {
                    if (array[j - 1] > array[j])
                    {
                        Swap(ref array[j - 1], ref array[j]);
                        swapFlag = true;
                    }
                }

                //если обменов не было выходим
                if (!swapFlag)
                {
                    break;
                }
            }

            return array;
        }


        //сортировка вставками
        static int[] InsertionSort(int[] array)
        {
            for (var i = 1; i < array.Length; i++)
            {
                var key = array[i];
                var j = i;
                while ((j > 1) && (array[j - 1] > key))
                {
                    Swap(ref array[j - 1], ref array[j]);
                    j--;
                }

                array[j] = key;
            }

            return array;
        }


        //сортировка по частям
        static int[] StoogeSort(int[] array, int startIndex, int endIndex)
        {
            if (array[startIndex] > array[endIndex])
                Swap(ref array[startIndex], ref array[endIndex]);

            if (endIndex - startIndex > 1)
            {
                var len = (endIndex - startIndex + 1) / 3;
                StoogeSort(array, startIndex, endIndex - len);
                StoogeSort(array, startIndex + len, endIndex);
                StoogeSort(array, startIndex, endIndex - len);
            }

            return array;
        }

        //Сортировка Шелла
        static int[] ShellSort(int[] array)
        {
            //расстояние между элементами, которые сравниваются
            var d = array.Length / 2;
            while (d >= 1)
            {
                for (var i = d; i < array.Length; i++)
                {
                    var j = i;
                    while (j >= d && array[j - d] > array[j])
                    {
                        Swap(ref array[j], ref array[j - d]);
                        j -= d;
                    }
                }

                d /= 2;
            }

            return array;
        }

        //Поразрядная сортировка, int length - исключает последнее!!!
        public static int[] MsdSorting(int[] arr, int range, int length)
        {
            var lists = new ArrayList[range];
            for (var i = 0; i < range; ++i)
                lists[i] = new ArrayList();

            for (var step = 0; step < length; ++step)
            {
                //распределение по спискам
                foreach (var t in arr)
                {
                    var temp = t % (int) Math.Pow(range, step + 1) /
                               (int) Math.Pow(range, step);
                    lists[temp].Add(t);
                }

                //сборка
                var k = 0;
                for (var i = 0; i < range; ++i)
                    for (var j = 0; j < lists[i].Count; ++j)
                        arr[k++] = (int) lists[i][j];

                for (var i = 0; i < range; ++i)
                    lists[i].Clear();
            }

            return arr;
        }

        public static int[] GetNewArray()
        {
            int numElements = 10000;
            Random rand = new Random();
            int[] source = { };
            for (int i = 0; i < numElements; ++i)
            {
                Array.Resize(ref source, source.Length + 1);
                source[i] = rand.Next(0, 1000);
            }

            return source;
        }


        private static TimeSpan TestSorting(int num, Func<int[], int[]> func)
        {
            var res = new List<TimeSpan>();
            for (int i = 0; i < num; ++i)
            {
                var source = GetNewArray();

                DateTime test = DateTime.Now;
                var resultArray = func(source);
                var span = DateTime.Now - test;
                res.Add(span);
            }

            return res.Aggregate(TimeSpan.Zero, (span, timeSpan) => span + timeSpan) / num;
        }


        private static TimeSpan TestMsdSorting(int num, Func<int[], int, int, int[]> func)
        {
            var res = new List<TimeSpan>();
            for (int i = 0; i < num; ++i)
            {
                var source = GetNewArray();
                var len = source.Length;
                DateTime test = DateTime.Now;
                func(source, 1000, 4);
                var span = DateTime.Now - test;
                res.Add(span);
            }

            return res.Aggregate(TimeSpan.Zero, (span, timeSpan) => span + timeSpan) / num;
        }



        static void Main(string[] args)
        {
//            Console.WriteLine($"Bubble sort done - mean: {TestSorting(10, BubbleSort)}");
//            Console.WriteLine($"Shaker sort done - mean: {TestSorting(10, ShakerSort)}");
//            Console.WriteLine($"Insertion sort done - mean: {TestSorting(10, InsertionSort)}");
//            Console.WriteLine($"Shell Sort - mean: {TestSorting(1000, ShellSort)}");
//            Console.WriteLine($"Bit(Radix) Sort - mean: {TestMsdSorting(1000, MsdSorting)}");
//
//
//            var test66 = GetNewArray();
//            DateTime test6 = DateTime.Now;
//            var sharp = test66.OrderBy(x => x).ToArray();
//            var testRes6 = DateTime.Now - test6;
//            Console.WriteLine($"OrderBy sort - {testRes6}");

            var t = GetNewArray();
            var temp = new int[10000];
            t.CopyTo(temp, 0);

            var test = DateTime.Now;
            MsdSorting(t,1000,1);
            Console.WriteLine($"Bit(Radix) Sort>>>: {DateTime.Now - test}");
//            Console.WriteLine(string.Join(",",t));
//            Console.WriteLine(string.Join(",",temp.OrderBy(x=>x)));

            var testing = temp.OrderBy(x => x).ToArray();

            bool res = t.SequenceEqual(testing);
            Console.WriteLine(res);
            if (!res)
                for (int i = 0; i < 10000; i++)
                {
                    if (t[i] != testing[i])
                        Console.WriteLine($"Num {i}: t={t[i]}  <>  testing={testing[i]}");
                }

//
//            var dict = new Dictionary<int, TimeSpan>();
//
//            for (var k = 1; k <= 10000; ++k)
//            {
//                var t = GetNewArray();
//                var len = t.Length;
//                var test = DateTime.Now;
//                MsdSorting(t,len,2);
//                dict.Add(k,DateTime.Now - test);
//                Console.WriteLine($"Bit Sort - {k} lists: {DateTime.Now - test}");
//            }
//
//            var min = dict.Values.Min();
//            Console.WriteLine(dict.First(x => x.Value == min));
        }
    }
}