using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        System.Int32[] myInts = {10, 1, 4, 2, 3, 9, 8, 7, 6, 5};

        System.Console.WriteLine(

            System.String.Join(", ", myInts)

        );

        BubbleSort(myInts);

        System.Console.WriteLine(

            System.String.Join(", ", myInts)

        );

        myInts = [500, 499, 100, 699, 3, 91, 75, 24];

        System.Console.WriteLine(

            System.String.Join(", ", myInts)

            );

        SelectionSort(myInts);

        System.Console.WriteLine(

            System.String.Join(", ", myInts)

            );

        myInts = [799, 699, 3, 4096, 17, 899];

        System.Console.WriteLine(

            System.String.Join(", ", myInts)

        );

        InsertionSort(myInts);

        System.Console.WriteLine(

            System.String.Join(", ", myInts)

        );

    }

    private static void BubbleSort(System.Int32[] a) {

        System.Int32 temp;

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

            for(int j=a.Length-1; j>i; j--) {

                if(a[j] < a[j-1]) {

                    temp = a[j];

                    a[j] = a[j-1];

                    a[j-1] = temp;

                }

            }

        }

    }

    private static void SelectionSort(System.Int32[] a) {

        System.Int32 mIndex = 0, temp;

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

            mIndex = i;

            for(int j=i+1; j<a.Length; j++) {

                if(a[j] < a[mIndex]) {

                    mIndex = j; 

                }

            }

            temp = a[i];

            a[i] = a[mIndex];

            a[mIndex] = temp;

        }

    }

    // Verified as valid implementation/solution

    private static void InsertionSort(System.Int32[] a) {

        System.Int32 j, val2savNset;

        System.Console.WriteLine("Starting 'Insertion Sorting Algorithm'");

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

            j = i+1;

            val2savNset = a[j];

            while(j>0 && val2savNset < a[j-1]) {

                a[j] = a[j-1];

                j--;

            }

            a[j] = val2savNset;

            System.Console.WriteLine(

                System.String.Join(", ", a)

            );

        }

    }

}