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

namespace BubbleSortOrder
{
    class Program
    {
        public static int count = 0;
        public static Stopwatch time = new Stopwatch();

        public static bool IsSorted(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i - 1] > arr[i])
                {
                    return false;
                }
            }

            return true;
        }

        static public void BubbleSort(int[] array)
        {
            time.Reset();
            time.Start();
            Console.WriteLine("BubbleSort: finished sorting... ");

            for (int write = 0; write < array.Length; write++)
            {
                for (int sort = 0; sort < array.Length - 1; sort++)
                {
                    if (array[sort] > array[sort + 1])
                    {
                        int temp = array[sort + 1];
                        array[sort + 1] = array[sort];
                        array[sort] = temp;
                        count++;
                    }
                }
            }

            if(IsSorted(array))
            {
                time.Stop();
                Console.WriteLine("Time: " + time.Elapsed);
                Console.WriteLine("Turns: " + count);
                Console.WriteLine(" ");
            }
        }
        static public void SelectSort(int[] arr)
        {
            int pos_min, temp;

            time.Reset();
            time.Start();
            Console.WriteLine("SelectSort: finished sorting... ");

            for (int i = 0; i < arr.Length - 1; i++)
            {
                pos_min = i;

                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[pos_min])
                    {
                        pos_min = j;
                    }

                    count++;
                }

                if (pos_min != i)
                {
                    temp = arr[i];
                    arr[i] = arr[pos_min];
                    arr[pos_min] = temp;
                }
            }

            if (IsSorted(arr))
            {
                time.Stop();
                Console.WriteLine("Time: " + time.Elapsed);
                Console.WriteLine("Turns: " + count);
                Console.WriteLine(" ");
            }
        }

        static public void MergeSort(int[] input, int startIndex, int endIndex)
        {
            int mid;

            time.Reset();
            time.Start();
            Console.WriteLine("SelectSort: finished sorting... ");

            if (endIndex > startIndex)
            {
                count++;

                mid = (endIndex + startIndex) / 2;
                MergeSort(input, startIndex, mid);
                MergeSort(input, (mid + 1), endIndex);
                Merge(input, startIndex, (mid + 1), endIndex);
            }

            if (IsSorted(input))
            {
                time.Stop();
                Console.WriteLine("Time: " + time.Elapsed);
                Console.WriteLine("Turns: " + count);
                Console.WriteLine(" ");
            }
        }

        static public void Merge(int[] input, int left, int mid, int right)
        {
            int[] temp = new int[input.Length];
            int i, leftEnd, lengthOfInput, tmpPos;
            leftEnd = mid - 1;
            tmpPos = left;
            lengthOfInput = right - left + 1;

            while ((left <= leftEnd) && (mid <= right))
            {
                if (input[left] <= input[mid])
                {
                    temp[tmpPos++] = input[left++];
                    count++;
                }
                else
                {
                    temp[tmpPos++] = input[mid++];
                    count++;
                }
            }

            while (left <= leftEnd)
            {
                count++;
                temp[tmpPos++] = input[left++];
            }

            while (mid <= right)
            {
                count++;
                temp[tmpPos++] = input[mid++];
            }

            for (i = 0; i < lengthOfInput; i++)
            {
                count++;
                input[right] = temp[right];
                right--;
            }
        }

        static public void MixerArray(int[] array)
        {
            Random rnd = new Random();

            for(int i = 0; i < array.Length; i++)
            {
                array[i] = rnd.Next(0, 60000);
            }

            count = 0;
        }

        public static void Main(string[] args)
        {

            int[] numbers = new int[1000];
            int len = numbers.Length;

            MixerArray(numbers);
            BubbleSort(numbers);
            MergeSort(numbers, 0, len - 1);

            Console.ReadLine();
        }
    }
}
