import java.util.Arrays;
public class InsertionSort {
public static int[] arr = {3, 2, 4, 1, 6, 8, 0};
/*
* 2, 3, 4, 1, 6, 8, 0 1,1 1,0
* 2, 3, 4, 1, 6, 8, 0 2,1 2,0
* 1, 2, 3, 4, 6, 8, 0 3,1 3,0
* 1, 2, 3, 4, 6, 8, 0
* 1, 2, 3, 4, 6, 8, 0 N-2,1 N-2,0
* 0, 1, 2, 3, 4, 6, 8 N-1,1 N-1,0
*
* best worst average
* compare N-1 N(N-1)/2 N-square/4
* swap 0 N(N-1)/2 N-square/4
*/
public static int[] sort(int[] a){
int N = a.length;
for(int i = 1; i < N; i++) {
for(int j = i; j > 0 && a[j] < a[j-1]; j--){
int t = a[j];
a[j]=a[j-1];
a[j-1]=t;
}
}
return a;
}
public static void main(String[] args) {
Arrays.stream(sort(arr)).forEach(System.out::println);
}
}
