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

namespace ConsoleApplication2
{
    class Sorting
    {
        public long porownanie = 0;
        public long przestawianie = 0;

        public int Max(int[] tab)
        {
            int max = tab[0];
            for (int i = 0; i < tab.Length; i++)
                if (tab[i] > max)
                    max = tab[i];
            return max;
        }
        public int Min(int[] tab)
        {
            int min = tab[0];
            for (int i = 0; i < tab.Length; i++)
                if (tab[i] < min)
                    min = tab[i];
            return min;
        }
        public void countingsort_2(int[] tab, int min, int max)
        {
            int[] count = new int[max - min + 1];
            int z = 0;

            for (int i = 0; porownanie++ >= 0 && i < count.Length; i++)
                count[i] = 0;

            for (int i = 0; porownanie++ >= 0 && i < tab.Length; i++)
                count[tab[i] - min]++;

            for (int i = min; porownanie++ >= 0 && i <= max; i++)
                while (porownanie++ >= 0 && count[i - min]-- > 0)
                {
                    tab[z] = i;
                    z++;
                    przestawianie++;
                }
        }
        public void countingsort(int[] tab, int min, int max)
        {
            int[] count = new int[max - min + 1];
            int z = 0;

            for (int i = 0; i < count.Length; i++)
                count[i] = 0;

            for (int i = 0; i < tab.Length; i++)
                count[tab[i] - min]++;

            for (int i = min; i <= max; i++)
                while (count[i - min]-- > 0)
                {
                    tab[z] = i;
                    z++;
                }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Podaj ilosc danych");
            int size = Convert.ToInt32(Console.ReadLine());
            Random r = new Random();

            // z1
            int[] tab_z1 = new int[size];
            for (int i = 0; i < tab_z1.Length; i++)
                tab_z1[i] = r.Next(1, 1000000);

            // z2
            int[] tab_z2 = (int[])tab_z1.Clone();

            // z3
            int[] tab_z3 = (int[])tab_z1.Clone();

            Sorting s = new Sorting();

            //srotowanie z2 rosnąco
            int min_z2 = s.Min(tab_z2);
            int max_z2 = s.Max(tab_z2);
            s.countingsort(tab_z2, min_z2, max_z2);

            //sortowanie z3 malejąco
            int j = 0;
            for (int i = tab_z2.Length - 1; i >= 0; i--)
            {
                tab_z3[j] = tab_z2[i];
                j++;
            }

            Sorting s1 = new Sorting();
            int min_z1 = s1.Min(tab_z1);
            int max_z1 = s1.Max(tab_z1);
            s1.countingsort_2(tab_z1, min_z1, max_z1);
            Console.WriteLine("z1nLiczba porównań: {0}tLiczba przestawien: {1}", s1.porownanie, s1.przestawianie);
            s1.porownanie = 0;
            s1.przestawianie = 0;

            Sorting s2 = new Sorting();
            s2.countingsort_2(tab_z2, min_z2, max_z2);
            Console.WriteLine("z1nLiczba porównań: {0}tLiczba przestawien: {1}", s2.porownanie, s2.przestawianie);
            s2.porownanie = 0;
            s2.przestawianie = 0;

            Sorting s3 = new Sorting();
            int min_z3 = s3.Min(tab_z3);
            int max_z3 = s3.Max(tab_z3);
            s3.countingsort_2(tab_z3, min_z3, max_z3);
            Console.WriteLine("z1nLiczba porównań: {0}tLiczba przestawien: {1}", s3.porownanie, s3.przestawianie);
            s3.porownanie = 0;
            s3.przestawianie = 0;

            Console.ReadKey();
        }
    }
}