using System;

namespace SortowanieSzybkie
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int n, x;
            var rand = new Random();
            Console.WriteLine("Ile liczb chcesz posortować: ");
            n = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Wybierz wariant: ");
            Console.WriteLine("1. Pivot - srednia geometryczna z pierwszego, srodkowego i ostatniego elementu tablicy. ");
            Console.WriteLine("2. Pivot - srednia arytmetyczna z dwoch losowych elementów tablicy");
            x = Convert.ToInt32(Console.ReadLine());
            var tab = new int[n];
            for (int i = 0; i < n; i++)//utworzenie tablicy losowych elementow
            {
                tab[i] = rand.Next(1, 10000);//zakres elementów do losowania
            }
            Console.WriteLine("Tablica przed sortowaniem: ");
            for(int i = 0; i < n; i++)
            {
                Console.Write(tab[i] + " ");
            }
            Console.WriteLine();


            if(x == 1) QuickSort(tab, 0, tab.Length - 1);
            if (x == 2) QuickSort2(tab, 0, tab.Length - 1);

            Console.WriteLine();
            Console.WriteLine("Tablica po sortowaniu: ");
            for (int i = 0; i < n; i++)
            {
                Console.Write(tab[i] + " ");
            }


            Console.ReadKey();
        }

        public static void QuickSort(int[] tab, int p, int q)
        {
            var i = p;//pierwszy element tablicy( indeks 0 )
            var j = q;//ostatni element tablicy( indeks ostatniego elementu
            int r = q / 2;
            double f = tab[p];
            double c = tab[r];
            double l = tab[q];
            double x = (f * c * l);
            double y = 1d / 3d;
            /// Pivot - srednia geometryczna z pierwszego, srodkowego i ostatniego elementu tablicy:
            var pivot = Math.Pow(x, y);
            //Console.WriteLine(pivot);

            while (i < j)
            {
                while (tab[i] < pivot) i++;
                while (tab[j] > pivot) j--;
                if (i <= j)
                {
                    var schowek = tab[i];
                    tab[i++] = tab[j];
                    tab[j--] = schowek;
                }
            }
            if (p < j) QuickSort(tab, p, j);
            if (i < q) QuickSort(tab, i, q);
        }

        public static void QuickSort2(int[] tab, int p, int q)
        {
            var rand1 = new Random();
            var i = p;
            var j = q;
            /// Pivot - srednia arytmetyczna z dwoch losowych elementów tablicy:
            var pivot = ((tab[rand1.Next(p, q)] + tab[rand1.Next(p, q)]) / 2);
            while (i < j)
            {
                while (tab[i] < pivot) i++;
                while (tab[j] > pivot) j--;
                if (i <= j)
                {
                    var schowek = tab[i];
                    tab[i++] = tab[j];
                    tab[j--] = schowek;
                }
            }
            if (p < j) QuickSort2(tab, p, j);
            if (i < q) QuickSort2(tab, i, q);

        }
    }
}