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

namespace Knut
{
    class Sort7
    {
        //‘Быстрая сортирвка
        List<Info> initialArray = new List<Info>();
        List<Info3> stack = new List<Info3>();
        public void Run()
        {
            Init();
            PrintAll();
            RunSort();
            PrintAll();
        }
        void Init()
        {
            initialArray.Clear();
            Random r = new Random();
            int n = r.Next() % 10 + 10;
            for (int i = 0; i < n; i++)
            {
                int a = r.Next() % 100;
                int b = r.Next() % 2;
                if (b == 0) a = -a;
                initialArray.Add(new Info()
                {
                    key = a,
                    text = "Text for " + a
                });
            }
        }
        void PrintAll()
        {
            Console.WriteLine("Key" + " \t " + "Some info");
            for (int i = 0; i < initialArray.Count; i++)
            {
                Console.WriteLine(initialArray[i].key + " \t " + initialArray[i].text);
            }
            Console.WriteLine("------------------------------");
        }
        void RunSort()
        {
            int M = 5;
            int N = initialArray.Count;
            int l, r;
            int K, j, i;
            if (N <= M)
            {
                RunSimpleInsertSort();
            }
            else
            {
                l = 1 - 1;
                r = N - 1;
                do
                {
                    i = l - 1;
                    j = r + 1 - 1;
                    K = initialArray[l].key;
                    do
                    {
                        do
                        {
                            i++;
                            if (!(initialArray[i].key < K))
                            {
                                break;
                            }
                        } while (true);
                        do
                        {
                            j--;
                            if (!(K < initialArray[j].key))
                            {
                                break;
                            }
                        } while (true);
                        if (j <= i)
                        {
                            Info temp = initialArray[l];
                            initialArray[l] = initialArray[j];
                            initialArray[j] = temp;
                            break;
                        }
                        else
                        {
                            Info temp = initialArray[i];
                            initialArray[i] = initialArray[j];
                            initialArray[j] = temp;
                        }
                    } while (true);
                    if ((r - j >= j - l) && (j - l > M))
                    {
                        stack.Add(new Info3()
                        {
                            a = j + 1,
                            b = r
                        });
                        r = j - 1;
                        continue;
                    }
                    else if ((j - l > r - j) && (r - j > M))
                    {
                        stack.Add(new Info3()
                        {
                            a = l,
                            b = j - 1
                        });
                        l = j + 1;
                        continue;
                    }
                    else if ((r - j > M) && (M >= j - l))
                    {
                        l = j + 1;
                        continue;
                    }
                    else if ((j - l > M) && (M >= r - j))
                    {
                        r = j - 1;
                        continue;
                    }
                    else
                    {
                        if (stack.Count != 0)
                        {
                            var temp = stack[stack.Count - 1];
                            l = temp.a;
                            r = temp.b;
                            stack.RemoveAt(stack.Count - 1);
                        }
                        else
                        {
                            break;
                        }
                    }
                } while (true);
                PrintAll();
                RunSimpleInsertSort();

            }

        }
        void RunSimpleInsertSort()
        {
            int i, j;
            for (j = 1; j < initialArray.Count; j++)
            {
                i = j - 1;
                Info temp = new Info()
                {
                    key = initialArray[j].key,
                    text = initialArray[j].text
                };
                do
                {
                    if (temp.key >= initialArray[i].key)
                    {
                        initialArray[i + 1] = temp;
                        break;
                    }
                    else
                    {
                        initialArray[i + 1] = initialArray[i];
                        i--;
                    }
                    //PrintAll();
                    //Console.WriteLine(temp.key + " - " + temp.text);
                } while (i > -1);
                if (i == -1)
                {
                    initialArray[0] = temp;
                }
                //PrintAll();
                //Console.WriteLine(temp.key + " - " + temp.text);
                //Console.WriteLine();
            }
        }
    }
}