using System;

using System.Diagnostics;

​

public class Program

{

    public void bubblesort()

    {

​

        int[] arr = { 2, 4, 6, 12, 0, 14, 19, -2 };

        Console.WriteLine("Original array : ");

        foreach (int b in arr)

        {

            Console.Write(" " + b);

        }

        int temp;

        for (int j = 0; j <= arr.Length - 2; j++)

        {

            for (int i = 0; i <= arr.Length - 2; i++)

            {

                if (arr[i] > arr[i + 1])

                {

                    temp = arr[i];

                    arr[i] = arr[i + 1];

                    arr[i + 1] = temp;

                }

            }

​

        }

​

​

        Console.WriteLine("");

        Console.WriteLine("sorted array: ");

​

        foreach (int n in arr)

        {

            Console.Write(" " + n);

​

        }

​

​

​

​

    }

​

​

    void insertionsort()

    {

        int[] arr = { 2, 4, 6, 12, 0, 14, 19, -2 };

        Console.WriteLine("Original array : ");

        foreach (int a in arr)

        {

            Console.Write(" " + a);

        }

        int curr;

        int i, j;

        for (i = 0; i < arr.Length; i++)

        {

            curr = arr[i];

            for (j = i; j > 0 && arr[j - 1] > curr; j--)

            {

                arr[j] = arr[j - 1];

            }

            arr[j] = curr;

        }

​

        Console.WriteLine("");

        Console.WriteLine("insertion sorted array: ");

​

        foreach (int N in arr)

        {

            Console.Write(" " + N);

​

        }

        Console.WriteLine("");

​

​

    }

    public class HeapSort

    {

​

        public void sort(int[] arr)

        {

​

​

            // Build heap (rearrange array) 

            int n = arr.Length;

            for (int i = n / 2 - 1; i >= 0; i--)

                heapify(arr, n, i);

​

            // One by one extract an element from heap 

            for (int i = n - 1; i >= 0; i--)

            {

                // Move current root to end 

                int temp = arr[0];

                arr[0] = arr[i];

                arr[i] = temp;

​

                // call max heapify on the reduced heap 

                heapify(arr, i, 0);

            }

        }

​

        // To heapify a subtree rooted with node i which is 

        // an index in arr[]. n is size of heap 

​

        void heapify(int[] arr, int n, int i)

        {

​

            int largest = i; // Initialize largest as root 

            int l = 2 * i + 1; // left = 2*i + 1 

            int r = 2 * i + 2; // right = 2*i + 2 

​

​

            // If left child is larger than root 

            if (l < n && arr[l] > arr[largest])

                largest = l;

​

            // If right child is larger than largest so far 

            if (r < n && arr[r] > arr[largest])

                largest = r;

​

​

            // If largest is not root 

            if (largest != i)

            {

                int swap = arr[i];

                arr[i] = arr[largest];

                arr[largest] = swap;

​

                // Recursively heapify the affected sub-tree 

                heapify(arr, n, largest);

​

            }

        }

​

​

        /* A utility function to print array of size n */

        public void printArray(int[] arr)

        {

            int n = arr.Length;

            for (int i = 0; i < n; ++i)

                Console.Write(arr[i] + " ");

        }

    }

​

    public class quicksort

    {

​

​

        static int partition(int[] arr, int low,

                                    int high)

        {

            int pivot = arr[high];

​

​

            int i = (low - 1);

            for (int j = low; j < high; j++)

            {

​

                if (arr[j] < pivot)

                {

                    i++;

​

                    // swap arr[i] and arr[j] 

                    int temp = arr[i];

                    arr[i] = arr[j];

                    arr[j] = temp;

                }

            }

​

​

            int temp1 = arr[i + 1];

            arr[i + 1] = arr[high];

            arr[high] = temp1;

​

            return i + 1;

        }

​

​

​

        public void quickSort(int[] arr, int low, int high)

        {

            if (low < high)

            {

​

​

                int pi = partition(arr, low, high);

​

​

                quickSort(arr, low, pi - 1);

                quickSort(arr, pi + 1, high);

            }

        }

​

​

        public void printArray(int[] arr, int n)

        {

            for (int i = 0; i < n; ++i)

                Console.Write(arr[i] + " ");

​

            Console.WriteLine();

​

        }

        public void array()

        {

            int[] arr = { 10, 7, 8, 9, 1, 5 };

            Console.WriteLine("");

            Console.WriteLine("");

            Console.WriteLine("*********Quick Sort**********");

            Console.WriteLine("");

            Console.WriteLine("orginal array:");

​

            foreach (int a in arr)

​

                Console.Write(" " + a);

​

            Console.WriteLine("");

            int n = arr.Length;

            quickSort(arr, 0, n - 1);

​

            Console.WriteLine("sorted array ");

​

            printArray(arr, n);

        }

​

    }

​

    public class MergeSort

    {

        static public void MainMerge(int[] numbers, int left, int mid, int right)

        {

            int[] temp = new int[25];

            int i, eol, num, pos;

            eol = (mid - 1);

            pos = left;

            num = (right - left + 1);

​

            while ((left <= eol) && (mid <= right))

            {

                if (numbers[left] <= numbers[mid])

                    temp[pos++] = numbers[left++];

                else

                    temp[pos++] = numbers[mid++];

            }

            while (left <= eol)

                temp[pos++] = numbers[left++];

            while (mid <= right)

                temp[pos++] = numbers[mid++];

            for (i = 0; i < num; i++)

            {

                numbers[right] = temp[right];

                right--;

            }

        }

​

        static public void SortMerge(int[] numbers, int left, int right)

        {

            int mid;

            if (right > left)

            {

                mid = (right + left) / 2;

                SortMerge(numbers, left, mid);

                SortMerge(numbers, (mid + 1), right);

                MainMerge(numbers, left, (mid + 1), right);

            }

        }

​

        public void sort()

        {

​

            int[] arr = { 2, 4, 6, 12, 0, 14, 19, -2 };

            Console.WriteLine("");

            Console.WriteLine("**********Merge Sort*********");

            Console.WriteLine("");

            Console.WriteLine("Original array : ");

            foreach (int a in arr)

            {

                Console.Write(" " + a);

            }

​

            Console.WriteLine("");

            Console.WriteLine("sorted array:");

            SortMerge(arr, 0, arr.Length - 1);

            for (int i = 0; i < arr.Length; i++)

                Console.Write(arr[i] + "\t");

​

        }

    }

​

​

​

    public static void Main()

​

    {

        Program p = new Program();

        Stopwatch i = new Stopwatch();

        i.Start();

        p.insertionsort();

        i.Stop();

        Console.WriteLine("Time taken by InsertionSort is: {0} milli", i.Elapsed.TotalMilliseconds);

        Console.WriteLine("");

        Console.WriteLine("***Bubble Sort****");

        Console.WriteLine("");

        Stopwatch b = new Stopwatch();

        b.Start();

        p.bubblesort();

        b.Stop();

        Console.WriteLine("");

        Console.WriteLine("Time taken by bubblesort is: {0} milli", b.Elapsed.TotalMilliseconds);

​

        Console.WriteLine("");

        Console.WriteLine("");

        Console.WriteLine("****Heap Sort***");

        Console.WriteLine("");

        int[] arr = { 12, 11, 13, 5, 6, 7,8,1,3,66,45,0,12,34,54,22,465,-2,66,43,54,43,42,41,67 };

​

        Console.WriteLine("orginal array:");

        foreach (int a in arr)

        {

            Console.Write(" " + a);

​

        }

        HeapSort ob = new HeapSort();

        Stopwatch h = new Stopwatch();

        h.Start();

        ob.sort(arr);

        Console.WriteLine("");

        Console.WriteLine("sorted array:");

        ob.printArray(arr);

        h.Stop();

        Console.WriteLine("");

       Console.WriteLine("Time taken by HeapSort is: {0} milli", h.Elapsed.TotalMilliseconds);

​

​

​

        Stopwatch q = new Stopwatch();

        q.Start();

        quicksort quk = new quicksort();

        quk.array();

          q.Stop();

          Console.WriteLine("Time taken by QuickSort is: {0} milli", q.Elapsed.TotalMilliseconds);

         Stopwatch m = new Stopwatch();

              m.Start();

        MergeSort me = new MergeSort();

        me.sort();

        m.Stop();

         Console.WriteLine("");

          Console.WriteLine("Time taken by MergeSort is: {0} milli", m.Elapsed.TotalMilliseconds);

​

​

​

    }

}

​

​

​