using System;

public class Program

{

    public static void Main()

    {

        int[] arr = new int[] {5, 3, 7, 8, 1, 3};

        //BubbleSort(ref arr);

        //SelectionSort(ref arr);

        InsertionSort(ref arr);

        foreach(var i in arr) Console.Write(i);

    }

    public static void BubbleSort(ref int[] arr) 

    {

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

        {

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

            {

                if(arr[j]<arr[j+1]) 

                {

                    //swap arr[i] and arr[i+1]

                    int temp = arr[j+1];

                    arr[j+1] = arr[j];

                    arr[j] = temp;

                }

            }

        } 

    }

    public static void SelectionSort(ref int[] arr) 

    {

        int len = arr.Length;

        for(int i=0; i<len-1; i++)

        {

            //Find Position of Minimum number

            int posMin = i;

            for(int j=i+1; j<len; j++) 

            {

                if(arr[j]<arr[posMin]) posMin = j;

            }

            //Swap the values of start position(ith) and posMin

            int temp = arr[posMin];

            arr[posMin] = arr[i];

            arr[i] = temp;

        }

    }

    public static void InsertionSort(ref int[] arr)

    {

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

        {

            int temp = arr[i];

            int j=i-1;

            while(j>=0 && temp<arr[j])

            {

                arr[j+1]=arr[j];

                j--;

            }

            arr[j+1] = temp;

        }

    }

}