Stalin_Array_comm

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

namespace StalinArray
{
    class Program
    {
        static void Main(string[] args)
        {
            bool debug_flag = false;               // Флаг для вывода массива
            Stopwatch timer = new Stopwatch();     // Для замера времени выполнения
            List<long> timeres = new List<long>(); // Для хранения результатов замера
            Random r = new Random();

            const int lngth = 1000;
            int[] a = new int[lngth];

            timer.Start();
            for (int i = 0; i < lngth; i++) a[i] = i + 1;
            timer.Stop();
            timeres.Add(timer.ElapsedMilliseconds);
            timer.Reset();

            if (debug_flag)
            {
                foreach (int i in a) Console.Write("{0} ", i);
                Console.WriteLine();
            }

            /*
             * Можно любое число, но желательно, чтобы оно было
             * больше длинны массива, либо равно ей.
             * Благодаря этому массив будет более "перемешан".
             */
            const int magic_count = lngth;
            /*
            Console.ForegroundColor = ConsoleColor.Green;
            Console.WriteLine("Перемешивание...");
            Console.WriteLine("{0} замен...", magic_count);
            Console.ForegroundColor = ConsoleColor.Gray;
            */
            timer.Start();
            int t, i1, i2;
            /*
             * Простейшее перемешивание.
             * 2 случайно выбранных элемента массива меняются местами.
             */
            for (int i = 0; i < magic_count; i++)
            {
                i1 = r.Next(0, lngth);
                i2 = r.Next(0, lngth);

                t = a[i1];
                a[i1] = a[i2];
                a[i2] = t;
            }
            timer.Stop();
            timeres.Add(timer.ElapsedMilliseconds);
            timer.Reset();

            if (debug_flag)
            {
                foreach (int i in a) Console.Write("{0} ", i);
                Console.WriteLine();
            }
            /*
            Console.ForegroundColor = ConsoleColor.Green;
            Console.WriteLine("Сдвиги...");
            Console.ForegroundColor = ConsoleColor.Gray;
            */
            List<List<int>> tarr = new List<List<int>>();
            tarr.Add(new List<int>(a));

            timer.Start();
            /*
             * Первая важная магия процесса.
             * Создается двумерный массив, 0-евой итерацией которого
             * становится изначальный перемешанный массив.
             * Совершается пробежка по всему массиву.
             * Если число меньше предыдущего, то оно "выталкивается" на
             * следующую итерацию, удаляясь в этой.
             */
            for (int i = 0; i < tarr.Count; i++)
            {
                for (int q = 1; q < tarr[i].Count; q++)
                {
                    if (tarr[i][q] < tarr[i][q - 1])
                    {
                        if (i + 1 >= tarr.Count) tarr.Add(new List<int>());

                        tarr[i + 1].Add(tarr[i][q]);
                        tarr[i].RemoveAt(q);
                        q--;
                    }
                }
            }
            timer.Stop();
            timeres.Add(timer.ElapsedMilliseconds);
            timer.Reset();

            if (debug_flag)
            {
                for (int i = 0; i < tarr.Count; i++)
                {
                    for (int q = 0; q < tarr[i].Count; q++)
                    {
                        Console.Write("{0} ", tarr[i][q]);
                    }
                    Console.WriteLine();
                }
            }
            /*
            Console.ForegroundColor = ConsoleColor.Green;
            Console.WriteLine("Волшебная магия...");
            Console.ForegroundColor = ConsoleColor.Gray;
            */
            List<int> res = new List<int>();
            int ti;
            /*
             * Вторая часть магии.
             * Пока в массиве есть значения, происходит пробежка
             * по 0-евым лементов всех вложенных массивов и выбирается
             * наименьшый из всех вариантов, который добавляется в
             * массив результата и удалятся из двумерного массива "сдвигов".
             * Регулярные проверки на "пустоту" массивов с последующим удалением
             * оберегают от ошибок и исключений.
             */
            timer.Start();
            while (tarr.Count > 0)
            {
                if (tarr[0].Count < 1)
                {
                    tarr.RemoveAt(0);
                    continue;
                }

                ti = 0;
                for (int i = 1; i < tarr.Count; i++)
                {
                    if(tarr[i].Count < 1)
                    {
                        tarr.RemoveAt(i);
                        i--;
                        continue;
                    }

                    if (tarr[ti][0] > tarr[i][0]) ti = i;
                }

                res.Add(tarr[ti][0]);
                tarr[ti].RemoveAt(0);
            }
            timer.Stop();
            timeres.Add(timer.ElapsedMilliseconds);
            timer.Reset();

            if (debug_flag)
            {
                foreach (int i in res) Console.Write("{0} ", i);
            }

            Console.Write("\n-----------------------------\n");
            Console.WriteLine("TimeResults:");
            for (int i = 0; i < timeres.Count; i++)
            {
                Console.WriteLine("{0} - {1}", i, timeres[i]);
            }

            Console.ReadKey();
        }
    }
}