public class Sorting {
    public static void main(String[] args) {

        int[] array = {2,6,99,432,121,463424,23,3,4,6,3,34,25,4,3,2,1};

        insertionsort(array);

        for(int i = 0; i<array.length; i++) System.out.println(array[i]);


    }


    public static void bubblesort(int[] array) {

        boolean swapped;

        for(int i = 0; i < array.length; i++) {

            swapped = false; //set swapped to false because nothing has been swapped
            for(int j = 0; j < array.length - 1 - i; j++) { //-1 because we need to access j+1
                if (array[j] > array[j+1]) {
                    //swap
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    swapped = true;
                }
            }

            if (swapped == false) break; //if no swaps were made that means the list is sorted
        }
    }


    public static void selectionsort(int[] array) {

        for(int i = 0; i < array.length; i++) {
            //to move boundary n times
            int min_index = i;
            for(int j = i+1; j < array.length; j++) {
                if (array[j] < array[min_index]) min_index = j; //find min index in i+1 to n
            } //after this for loop we should have the index of min value in i to n (i if it was not updated)
            if (min_index != i) { //don't do anything if min_index was i (it's in the right position)
                //swap array[min_index] and array[i]
                int temp = array[min_index];
                array[min_index] = array[i];
                array[i] = temp;
            }
        }
    }

    public static void insertionsort(int[] array) {

        for(int i = 0; i < array.length; i++) {
            int k = i; //store current i in k to so we can change k without breaking the loop
            int elem = array[i];
            while(k>0 && elem < array[k-1]) {
                array[k] = array[k-1];
                k--;
            }
            array[k] = elem;
        }

    }


}