using System;

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("");

            Console.WriteLine("");

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

            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");

            Console.ReadLine();

        }

    }

    public static void Main()

          {

    Program p=new Program();

        p.insertionsort();

        p.bubblesort();

        Console.WriteLine("");

        Console.WriteLine("");

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

        Console.WriteLine("");

         int[] arr = { 12, 11, 13, 5, 6, 7 };

        Console.WriteLine("orginal array:");

        foreach (int a in arr)

        {

            Console.Write( " " +a );

​

        }

        HeapSort ob = new HeapSort();

        ob.sort(arr);

        Console.WriteLine("");

        Console.WriteLine("sorted array:");

         ob.printArray(arr); 

       quicksort quk=new quicksort();

        quk.array();

        MergeSort me=new MergeSort();

        me.sort();

    }

 }

​

​