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

namespace InsertSort
{
    class Program
    {
        public static void InsertSort(int[] tab)
        {
            int n = tab.Length;
            int obecny;
            int inny;
            for (int i=1;i<n;i++)
            {
                obecny = tab[i];
                inny = i;
                while (inny > 0 && obecny < tab[inny - 1])
                {
                    tab[inny] = tab[inny - 1];
                    inny--;
                }
                tab[inny] = obecny;
            }
        }

        public static void Swap(int[] tab, int index1, int index2)
        {
            int bufor = tab[index1];
            tab[index1] = tab[index2];
            tab[index2] = bufor;
        }

        public static void Select(int[] tab)
        {
            int min;
            int n = tab.Length;

            for (int i=0;i<n - 1;i++)
            {
                min = i;
                for (int j = i+1;j<n; j++)
                {
                    if (tab[min] > tab[j])
                        min = j;
                }
                Swap(tab, min, i);
            }
        }

        public static void Zliczanie(int[] tab)
        {
            int n = tab.Length;
            int i, k, c;
            int[] pomocnicza = new int[100];
            for (i = 0; i < 100; i++)
                pomocnicza[i] = 0;
            for (i = 0; i < n; i++)
                pomocnicza[tab[i]]++;
            c = 0;
            for (i=0;i<100;i++)
            {
                if (pomocnicza[i] > 0)
                {
                    for (k=1;k<pomocnicza[i]+1;k++)
                    {
                        tab[c] = i;
                        c++;
                    }
                }
            }
        }

        static void Main(string[] args)
        {
            Random r = new Random();
            int[] tab = new int[20];
            for (int i=0;i<tab.Length;i++)
            {
                tab[i] = r.Next(100);
                Console.Write(tab[i] + " ");
            }
            Console.WriteLine();
            Zliczanie(tab);
            for (int i = 0; i < tab.Length; i++)
            {
                Console.Write(tab[i] + " ");
            }
            Console.ReadKey();
        }
    }
}