//QuickSort
        public static int Podziel(int[] tablica , int poczatek, int koniec)
        {
            int klucz = tablica[poczatek];
            while (true)
            {
                while (tablica[poczatek] <klucz)
                {
                    poczatek++;
                }
                while (tablica[koniec]> klucz)
                {
                    koniec--;
                }

                if (poczatek < koniec)
                {
                    if (tablica[poczatek] == tablica[koniec]) return koniec;
                    int tmp = tablica[poczatek];
                    tablica[poczatek] = tablica[koniec];
                    tablica[koniec] = tmp;
                }
                else return koniec;
            }
        }
        public static void QuickSort(int[] tablica, int poczatek, int koniec)
        {
            if (poczatek<koniec)
            {
                int klucz = Podziel(tablica, poczatek, koniec);
                if (klucz>1)
                {
                    QuickSort(tablica, poczatek, klucz -1);
                }
                if (klucz +1< koniec)
                {
                    QuickSort(tablica, klucz + 1, koniec);
                }

            }
        }


        //Sortowanie przez wstawianie (jak w kartach)
        public static int[] Sortowanie_przez_wstawianie(int[] tablica)
        {
            int klucz, j;

            for (int i = 1; i < tablica.Length; i++)
            {
                klucz = tablica[i];
                 j = i;
                while (j > 0 && tablica[j-1] > klucz) //sprawdza wpierw pierwszy warunek czyli j>0
                {
                    tablica[j] = tablica[j-1 ];
                    j--;
                }
                tablica[j] = klucz;
            }

            return tablica;

        }


        //Sortowanie przez scalanie/ MergeSort/łączenie (nie działa?)
        public static void Podział(int[] tab, int poczatek, int koniec, int[] tab2)
        {
            if (poczatek<koniec)
            {
                int mid = (poczatek + koniec) / 2;
                Podział(tab, poczatek, mid, tab2);
                Podział(tab, mid + 1, koniec, tab2);
                Scalaj(tab, poczatek, mid, koniec, tab2);
            }
        }
        public static void Scalaj(int[] tab, int poczatek, int mid, int koniec, int[] tab2)
        {
            int p1 = poczatek; int k1 = mid;
            int p2 = mid + 1; int k2 = koniec;

            int i = p1;

            while (p1<= k1 && p2<=k2)
            {
                if (tab[p1]>tab[p2])
                {
                    tab2[i] = tab[p2];
                    p2++;
                    i++;
                }
                else
                {
                    tab2[i] = tab[p1];
                    p1++;
                    i++;
                }
            }

            while (p1<=k1)
            {
                tab2[i] = tab[p1];
                p1++;
                i++;

            }
            while (p2<=k2)
            {
                tab2[i] = tab[p2];
                p2++;
                i++;
            }
            for (int f = 0; f < tab.Length; f++)
            {
                tab[f] = tab2[f];
            }
        }

        //Sortowanie przez selekcję
        public static void Selekcja_Sort(int[] tablica)
        {
            for (int i = 0; i < tablica.Length-1; i++)
            {
                int k = i;
                for (int j = i + 1; j < tablica.Length; j++)
                {
                    if (tablica[k] > tablica[j])
                    {
                        k = j;
                    }


                        int temp = tablica[k];
                        tablica[k] = tablica[i];
                        tablica[i] = temp;


                }

            }
        }


        //Sortowanie bąbelkowe

        public static void Bubble_Sort(int[] tab)
        {
            for (int i = 0; i < tab.Length-1; i++)
            {
                for (int j = 0; j < tab.Length-1; j++)
                {
                    if (tab[j] >tab[j+1])
                    {
                        int temp = tab[j+1];
                        tab[j+1] = tab[j];
                        tab[j ] = temp;
                    }
                }
            }
        }




zad 2
public static void Przedział(int[] ciąg, int x, int p, int k)
        {
            if (x < ciąg[k])
            {
                Console.WriteLine("<- nieskończoność, {0} >", ciąg[k]);
                return;
            }
            if (x > ciąg[p])
            {
                Console.WriteLine("< {0}, nieskończoność>", ciąg[p]);
                return;
            }
            int mid = (p + k) / 2;

            if (p +1==k)
            {
                if (x == ciąg[p]) Console.WriteLine("< {0}, nieskończoność>", ciąg[p]);
                if (x == ciąg[k]) Console.WriteLine("Znajduje się miedzy: < {0} , {1} >" , ciąg[p] , ciąg[k] +1);
                else Console.WriteLine("Znajduje się miedzy: < {0} , {1} >", ciąg[p], ciąg[k] );
                return;
            }

                if (x>= ciąg[mid])
                {


                    Przedział(ciąg, x, p, mid);
                }
                else
                Przedział(ciąg, x, mid, k);



        }



zad3

  public static int[] Sortowanie_wstawianie(int[] tab)
        {
            int[] index = new int[tab.Length];
            for (int i = 0; i < tab.Length; i++)
            {
                index[i] = i;
            }


            int k, j;
            for (int i = 1; i < tab.Length; i++)
            {
                k = tab[i];
                int x = index[i];
                j = i;
                x = i;
                while (j>0 && tab[j-1] >k)
                {
                    tab[j] = tab[j - 1];
                    index[j] = index[j - 1];
                    j--;
                }
                tab[j] = k;
                index[j] = x;
            }
            return index;
        }


zad5
public static int Kara(int[,] dół, int[,] prawo, int[,] skos,int wysokosc, int szerokosc, int[,] kroki )
        {
            int[,] wyniki= new int[wysokosc+1, szerokosc+1];
            wyniki[0, 0] = 0;
            for (int i = 1; i <=wysokosc; i++)
            {
                wyniki[i, 0] = wyniki[i-1, 0] + dół[i-1, 0];
                kroki[i, 0] = 1;
            }
            for (int j = 1; j <= szerokosc; j++)
            {
                wyniki[0, j] = wyniki[0, j - 1] + prawo[0, j - 1];
                kroki[0, j] = 2;
            }
            for (int i = 1; i <=wysokosc; i++)
            {
                for (int j = 1; j <= szerokosc; j++)
                {
                    if (wyniki[i-1,j] + dół[i-1,j] > wyniki[i, j-1] +prawo[i,j-1] && prawo[i,j-1] !=-1)
                    {
                        if (wyniki[i, j - 1] + prawo[i, j - 1] > wyniki[i - 1, j - 1] + skos[i - 1, j - 1])
                        {
                            wyniki[i, j] = wyniki[i - 1, j - 1] + skos[i - 1, j - 1];
                            kroki[i, j] = 3;

                        }
                        else
                        {
                            wyniki[i, j] = wyniki[i, j - 1] + prawo[i, j - 1];
                            kroki[i, j] = 2;
                        }
                    }
                    else
                    {
                        if (wyniki[i - 1, j] + dół[i - 1, j] > wyniki[i - 1, j - 1] + skos[i - 1, j - 1])
                        {
                            wyniki[i, j] = wyniki[i - 1, j - 1] + skos[i - 1, j - 1];
                            kroki[i, j] = 3;
                        }
                        else
                        {
                            wyniki[i, j] = wyniki[i - 1, j] + dół[i - 1, j];
                            kroki[i, j] = 1;
                        }
                    }

                }
            }
            return wyniki[wysokosc, szerokosc];





        }


public static void Ścieżka(int[,] kroki, int wysokosc,int szerokosc)
        {
            Stack<string> ścieżka = new Stack<string>();
            int i = wysokosc;
            int j = szerokosc;
            while (kroki[i,j] >0)
            {
                if (kroki[i,j] ==1)
                {
                    ścieżka.Push("down");
                    i--;
                }

                if (kroki[i,j] ==2)
                {
                    ścieżka.Push("right");
                    j--;
                }
                else
                {
                    ścieżka.Push("skos");
                    i--;
                    j--;
                }
            }
            while (ścieżka.Count>0)
            {
                Console.WriteLine(ścieżka.Pop());
            }
        }