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

namespace algorytmy374
{
    class Program
    {
        static int N = 20000000, czas;

        static void swap(ref int a, ref int b)
        {
            int roboczy = a; a = b; b = roboczy;
        }

        static void SelectionSort(int[] tab)
        {
            int m;
            for (int i = 1; i <= N; i++)
            {
                m = i;
                for (int j = i + 1; j <= N; j++)
                {
                    if (tab[j] < tab[m])
                    {
                        swap(ref tab[m], ref tab[i]);
                    }
                }
            }
        }

        static void HeapSprt(int[] tab)
        {
            int k, m, x, j;

            //robimy kopiec
            for (int i = 2; i <= N; i++)
            {
                j = i; k = j / 2; x = tab[i];
                while ((k > 0) && (tab[k] < x))
                {
                    tab[j] = tab[k]; j = k; k = j / 2;
                }
                tab[j] = x;
            }

            //rozbieramy kopiec
            for (int i = N; i > 1; i--)
            {
                swap(ref tab[1], ref tab[i]);
                j = 1; k = 2;
                while (k < i)
                {
                    if ((k + 1 < i) && (tab[k + 1] > tab[1]))
                        m = k + 1;
                    else m = k;

                    if (tab[m] <= tab[j])
                        break;
                    swap(ref tab[m], ref tab[j]);
                    j = m; k = j + j;
                }
            }
        }

        static void Main(string[] args)
        {
            DateTime startTime;
            Random los = new Random();
            int[] tab1 = new int[N + 1];
            int[] tab2 = new int[N + 1];

            for (int i = 1; i <= N; i++) tab1[i] = tab2[i] = los.Next(0, 9999);

            if (N < 21)
            for (int i = 1;i<=N;i++)
            {
                Console.Write(tab1[i] + " ");
            }

            Console.WriteLine("\n");
            //selection sort
            //startTime = DateTime.Now;
            //SelectionSort(tab1);
            //czas = (int)(DateTime.Now - startTime).TotalMilliseconds;
            //Console.WriteLine("czas sortowania: " +  czas);
            //Console.WriteLine("\n");

            //heap sort
            startTime = DateTime.Now;
            HeapSprt(tab2);
            czas = (int)(DateTime.Now - startTime).TotalMilliseconds;
            Console.WriteLine("czas kopcowania: " + czas);
            Console.Read();
        }
    }
}