// Insertion sort


public class insertionSort
{
    public static void main(String[] args) {
        int [] numbers = new int[]{2,5,7,23,12,1,79,4};

        List<Integer> result1 = insertionSort_1(numbers);

        System.out.println("original array:");
        for (int num : numbers) System.out.print(num + " ");
        System.out.println("\n" +"sorted array with List implementation:");
        for (Integer num : result1) System.out.print(num + " ");

        int [] result2 = insertionSort_2(numbers);

        System.out.println("\n" +"sorted array with classic arrays sorting:");
        for (Integer num : result2) System.out.print(num + " ");

    }

    //Using List implementation
    public static List<Integer> insertionSort_1(int[] arr) {

        List<Integer> sorted = new ArrayList<>();

        outer: for (int num : arr) {
            for (int i = 0; i < sorted.size(); i++) {
                if (num < sorted.get(i)) {
                    sorted.add(i, num);
                    continue outer;
                }
            }
            sorted.add(sorted.size(), num);
        }

        return sorted;
    }

    //classic array sorting
    public static int [] insertionSort_2(int [] arr) {
        int [] sorted = new int[arr.length];

        for (int i = 0; i < sorted.length; i++) {
            sorted[i] = arr[i];
        }

        int temp, j;    //in temp we put our "the first" element of unsorted part, j is the number of cell, in which we put this element after sorting

        for (int i = 0; i < sorted.length - 1; i++) {

            if (sorted[i] > sorted[i + 1]) {

                temp = sorted[i + 1];
                sorted[i + 1] = sorted[i];
                j = i;

                while (j > 0 && temp < sorted[j - 1]) {
                    sorted[j] = sorted[j - 1];
                    j--;
                }
                sorted[j] = temp;
            }

        }
        return sorted;
    }

}