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

namespace Week5_1
{
    internal class Program
    {        
        static void bubbleSort(int[] arr, int n)
        {
            int i, j, temp;
            bool swapped;
            for (i = 0; i < n - 1; i++)
            {
                swapped = false;
                for (j = 0; j < n - i - 1; j++)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        // Swap arr[j] and arr[j+1]
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        swapped = true;
                    }
                }

                // IF no two elements were 
                // swapped by inner loop, then break
                if (swapped == false)
                    break;
            }
        }

        // Function to print an array 
        static void printArray(int[] arr, int size)
        {
            int i;
            for (i = 0; i < size; i++)
                Console.Write(arr[i] + " ");
            Console.WriteLine(" <br>");
        }

        public static void Main()
        {
            int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
            int n = arr.Length;
            bubbleSort(arr, n);
            Console.WriteLine("Sorted array:");
            printArray(arr, n);
        }


        static void swap(int[] arr, int xp, int yp)
        {
            int temp = arr[xp];
            arr[xp] = arr[yp];
            arr[yp] = temp;
        }

        static void selectionSort(int[] arr, int n)
        {
            int i, j, min_idx;

            // One by one move boundary of unsorted subarray 
            for (i = 0; i < n - 1; i++)
            {
                // Find the minimum element in unsorted array 
                min_idx = i;
                for (j = i + 1; j < n; j++)
                    if (arr[j] < arr[min_idx])
                        min_idx = j;

                // Swap the found minimum element with the first element 
                swap(arr, min_idx, i);
            }
        }

        static void printArray(int[] arr)
        {
            int n = arr.Length;
            for (int i = 0; i < n; ++i)
                Console.Write(arr[i] + " ");
            Console.WriteLine();
        }

        // Driver code
        public static void Main(String[] args)
        {
            int[] arr = { 41, 51, 71, 67, 984, 32, 91, 4, 7, 65, 94, 82 };
            Console.WriteLine("Given array is");
            printArray(arr);
            mergeSort(arr, 0, arr.Length - 1);
            Console.WriteLine("\nSorted array is");
            printArray(arr);
        }

        static void merge(int[] A, int start, int mid, int end)
        {
            int p = start;
            int q = mid + 1;
            int[] arr = new int[end - start + 1];
            int k = 0;
            for (int i = start; i <= end; i++)
            {
                if (p > mid)
                { //checks if first part comes to an end or not
                    arr[k++] = A[q++];
                }
                else if (q > end)
                { //checks if second part comes to an end or not
                    arr[k++] = A[p++];
                }
                else if (A[p] < A[q])
                { //checks which part has smaller element.
                    arr[k++] = A[p++];
                }
                else
                {
                    arr[k++] = A[q++];
                }//end if
            }//end for
            for (p = 0; p < k; p++)
            {
                // Now the real array has elements in sorted manner including both parts.
                A[start++] = arr[p];
            }//end for
        }//end function

        static void mergeSort(int[] A, int start, int end)
        {
            if (start < end)
            {
                int mid = ((start + end) / 2); // defines the current array in 2 parts .
                mergeSort(A, start, mid); // sort the 1st part of array .
                mergeSort(A, mid + 1, end);  // sort the 2nd part of array.
                                             // merge the both parts by comparing elements of both the parts.
                merge(A, start, mid, end);
            }//end if      
        }//end function


        // Driver code
        public static void Main2(String[] args)
        {
            int[] arr = { 41, 51, 71, 67, 984, 32, 91, 4, 7, 65, 94, 82 };
            Console.WriteLine("Given array is");
            printArray(arr);
            mergeSort(arr, 0, arr.Length - 1);
            Console.WriteLine("\nSorted array is");
            printArray(arr);
        }

        // PHP program for implementation
        // of selection sort
        static void selectionSorted(int[] arr, int n)
        {
            for (int i = 0; i < n; i++)
            {
                int low = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (arr[j] < arr[low])
                    {
                        low = j;
                    }//end if
                }//end for
                 // swap the minimum value to $ith node
                if (arr[i] > arr[low])
                {
                    int tmp = arr[i];
                    arr[i] = arr[low];
                    arr[low] = tmp;
                }//end if
            }//end for
        }//end function

        // Driver Code
        public static void Main3()
        {
            int[] arr = { 64, 25, 45, 75, 76, 34, 2, 48, 12, 22, 11 };
            int len = arr.Length;
            Console.WriteLine("<h3>Selection Sort Week 5\n</h3>");
            Console.WriteLine("Unsorted array: <br>");
            Console.WriteLine(arr + " ");
        selectionSorted(arr, len);
            Console.WriteLine("<br>Sorted array: <br>");

            for (int i = 0; i < len; i++) {
                Console.WriteLine(arr[i] + " ");
            }
        }
}//end for

    // This code is contributed
    // by Deepika Gupta.
}