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

namespace Sorty
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] tab = new int[] { 10, 9, 8, 7, 6};
            Console.Write("Przed sortowaniem: ");
            wypisz();

            int[] tab1 = new int[] { 10, 9, 8, 7, 6 };
            Bsort(tab1);
            Console.Write("BubbleSort: ");
            wypisz();

            int[] tab2 = new int[] { 10, 9, 8, 7, 6 };
            InsertionSort(tab2);
            Console.Write("InsertionSort: ");
            wypisz();

            int[] tab3 = new int[] { 10, 9, 8, 7, 6 };
            SelectionSort(tab3);
            Console.Write("Selection: ");
            wypisz();

            int[] tab4 = new int[] { 10, 9, 8, 7, 6 };
            Console.Write("CountingSort: ");
            CSort(tab);

            int[] tab5 = new int[] { 10, 9, 8, 7, 6 };
            QuickSort(tab5,0,tab.Length-1);
            Console.Write("\n\nQuickSort: ");
            wypisz();

            int[] tab6 = new int[] { 10, 9, 8, 7, 6 };
            MergeSort(tab6, 0, tab.Length - 1);
            Console.Write("MergeSort: ");
            wypisz();

            void wypisz()
            {
                foreach (int i in tab)
                {
                    Console.Write(i + " ");
                }
                Console.WriteLine("\n");
            }
            Console.ReadKey();
        }
        static void Swap(int[] tab, int p, int d) //zamienia pierwszą z drugą
        {
            var tmp = tab[p];
            tab[p] = tab[d];
            tab[d] = tmp;
        }
        static void Bsort(int[] tab)
        {
            bool czyZmiana = false; //czyZmiana = false, gdyż żadna wartość nie została jeszcze zeSwapowana
            do
            {
                czyZmiana = false; //czyZmiane ustawia na false z każdym zapętleniem żeby for działał dopóki nie zamienią się wszystkie wartości
                for (int i = 0; i < tab.Length-1 ; i++)
                {
                    if (tab[i] > tab[i + 1])
                    {
                        Swap(tab, i,i+1); //Jeśli pierwsza liczba jest > od drugiej, zamień je
                        czyZmiana = true; //jeśli była zamiana ustawia na true
                    }
                }
            } while (czyZmiana) ;
        }
        static void InsertionSort(int[] tab)
        {
            for (int i =1;i<tab.Length;i++)
            {
                int obecna = tab[i]; //następna liczba jeszcze nie posortowana
                int indexPierw = i - 1; //index wczesniejsza liczby, już w tablicy posortowanej

                while (indexPierw >= 0 && tab[indexPierw] > obecna) //wykonuje się dopóki index wczesniejsze > 0 i wczesniejsza > następnej
                {
                    obecna = tab[indexPierw]; //obecną zamienia na wczesniejszą
                    indexPierw -= 1; //wczesniejszą zamienia na jeszcze wcześniejszą i pętla wykonuje się ponownie dla niej
                }
            }
        }
        static void SelectionSort(int[] tab)
        {
            int minIndex;
            for (int i = 0; i < tab.Length - 1; i++) //pętla po całej tablicy
            {
                minIndex = i; //index minimalnej ustawionej na pierwszą liczbę
                for (int j = i+1; j<tab.Length;j++) //pętla po tabliczy z wyjatkiem minIndex
                {
                    if (tab[j] < tab[minIndex]) //jeśli wartosc drugiej < od pierwszej
                    {
                        minIndex = j; //minIndexeb bedzie index tej drugiej
                    }
                }
                Swap(tab, minIndex, i); //zamienia znalezioną najmniejszą z tą pierwszą z pętli z 1 for'a
            }
        }
        static void CSort(int[] tab)
        {
            int max = 0;
            //znajduje maxymalną
            for (int i = 0; i < tab.Length; i++)
            {
                if (max < tab[i])
                    max = tab[i];
            }
            //tworzy tablicę zer(częstotliwości)
            int[] freq = new int[max+1];
            for (int i = 0; i <= max; i++)
            {
                freq[i] = 0;
            }
            //jeśli liczba tab[i] == indexowi tablicy frq wtedy +=1
            for (int i = 0; i < tab.Length; i++) //for po wszystkich indexach tab nieposortowanej
            {
                for (int j = 0; j < max; j++) //for po wszystkich indexach tab freq
                {
                    if (tab[i] == j)
                    {
                        freq[j] += 1;
                    }
                }
            }
            for (int i = 0; i <= max; i++)
            {
                for (int j = 0; j < freq[i] ; j++)
                    Console.Write(i + " ");

            }
        }
        static void QuickSort(int[] tab, int poczatek, int koniec)
        {
            int L = poczatek;
            int P = koniec;
            int S = tab[(poczatek + koniec) / 2]; //srodek
            while (L < P) //dopoki lewy index < prawy index
            {
                while (tab[L] < S) L++; //dopóki warosc z lewej < wartosc srodka ; index lewy++
                while (tab[P] > S) P--; //dopóki warosc z prawej > wartosc srodka ; index prawy--
                if (L <= P)
                {
                    Swap(tab, L, P); //zamien wartosc z lewgo indexu z wartoscia z prawego indexu
                    L++;
                    P--;
                }
            }
            if (poczatek < P) QuickSort(tab, poczatek, P);
            if (L < koniec) QuickSort(tab, L, koniec);
        }
        static void Merge(int[] tab,int poczatek, int koniec)
        {
            int[] tmp = new int[tab.Length];
            for (int i = poczatek; i <= koniec; i++) //przepisanie wartosci tablicy do tymczasowej
            {
                tmp[i] = tab[i];
            }
            int P = poczatek; //pocz tab nieposortowanej tymczasowej
            int S = (poczatek + koniec) / 2 +1; //index srodek
            int Ptmp = poczatek; //pocz tab nieposortowanej
            while (P <= poczatek+koniec/2  && S <= koniec)
            {
                if (tmp[P] < tmp[S])
                {
                    tab[Ptmp] = tmp[P];
                    Ptmp++;
                    P++;
                }
                else
                {
                    tab[Ptmp] = tmp[S];
                    Ptmp++;
                    S++;
                }

            }
            while (P <= (poczatek+koniec)/2)
            {

                tab[Ptmp] = tmp[P];
                Ptmp++;
                P++;
            }
        }

        static void MergeSort(int[] tab,int pocz, int kon)
        {
            if (pocz < kon)
            {
                Merge(tab, pocz, (pocz + kon) / 2); //scalanie lewej
                Merge(tab, (pocz + kon) / 2 + 1, kon); //scalanie prawej
                Merge(tab, pocz, kon); //scalanie
            }
        }
    }
}