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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = 3000000;
            var timer = new Stopwatch();
            int[] arrСlassic = new int[n];
            int[] arrCopy = new int[n];
            int[] arrTasks = new int[n];
            timer.Start();
            for (int i = 0; i < arrСlassic.Length - 1; i++)
            {
                arrСlassic[i] = i;
            }
            timer.Stop();
            Console.WriteLine($"Preparing array with {n} integers elapsed: {timer.ElapsedMilliseconds} miliseconds...");
            timer.Reset();
            var end = new Random();
            timer.Start();
            arrСlassic = arrСlassic.OrderBy(x => end.Next()).ToArray();
            timer.Stop();
            Console.WriteLine($"Sguffling the array elapsed: {timer.ElapsedMilliseconds} miliseconds");
            timer.Reset();
            Console.WriteLine("Copying shuffled array to others....");
            timer.Start();
            for (int i = 0; i < arrCopy.Length - 1; i++)
            {
                arrCopy[i] = arrСlassic[i];
                arrTasks[i] = arrСlassic[i];
            }
            timer.Stop();
            Console.WriteLine($"Done for {timer.ElapsedMilliseconds} milisecods");
            timer.Reset();
            timer.Start();
            QuickSort(arrСlassic, 0, arrСlassic.Length - 1);
            timer.Stop();
            //Console.WriteLine(string.Join(", ", arr));
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("QuickSortClassic sorted using synchronius operations");
            Console.WriteLine($"Time elapsed: {timer.ElapsedMilliseconds} miliseconds");
            timer.Reset();
            timer.Start();
            QuickSortTask(arrTasks, 0, arrTasks.Length - 1);
            timer.Stop();
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("QuickSortTask sorted using Task Factory");
            Console.WriteLine($"Time elapsed: {timer.ElapsedMilliseconds} miliseconds");
            timer.Reset();
            timer.Start();
            QuickSortParallel(arrCopy, 0, arrCopy.Length - 1);
            timer.Stop();
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("QuickSortParallel sorted using Parallel.Invoke");
            Console.WriteLine($"Time elapsed: {timer.ElapsedMilliseconds} miliseconds");
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("Becnhmark Done");
        }
        public static void QuickSort(int[] arr, int start, int end)
        {
            if (start >= end)
            {
                return;
            }
            int pivotIndex = Partition(arr, start, end);
            QuickSort(arr, start, pivotIndex - 1);
            QuickSort(arr, pivotIndex + 1, end);
        }
        public static void QuickSortParallel(int[] arr, int start, int end)
        {
            if (start >= end)
            {
                return;
            }
            int pivotIndex = Partition(arr, start, end);
            Parallel.Invoke
                (
                    () => QuickSortParallel(arr, start, pivotIndex - 1),
                    () => QuickSortParallel(arr, pivotIndex + 1, end)
                );
        }
        public static void QuickSortTask(int[] arr, int start, int end)
        {
            if (start >= end)
            {
                return;
            }
            int pivotIndex = Partition(arr, start, end);
            Task.Factory.StartNew(() => QuickSortTask(arr, start, pivotIndex - 1));
            Task.Factory.StartNew(() => QuickSortTask(arr, pivotIndex + 1, end));

        }
        private static int Partition(int[] arr, int start, int end)
        {
            int pivotIndex = start;
            int pivot = arr[end];

            for (int i = start; i < end; i++)
            {
                if (arr[i] <= pivot)
                {
                    int temp = arr[i];
                    arr[i] = arr[pivotIndex];
                    arr[pivotIndex] = temp;
                    pivotIndex++;
                }
            }
            int temp1 = arr[pivotIndex];
            arr[pivotIndex] = arr[end];
            arr[end] = temp1;

            return pivotIndex;
        }
    }
}