[삽입 정렬] Java 삽입 정렬

public class Algo03 {

	public static void main(String[] args) {
		
		/*
		 * 삽입정렬
		 * 1 10 5 8 7 6 4 3 2 9
		 * 각 숫자를 적절한 위치에 삽입하는 방법
		 * 필요할떄만 위치를 바꾸게 된다.
		 * O(N^2)중에 가장 좋다.
		 * 1 -> 1 10 5 8 7 6 4 3 2 9
		 * 	 -> 1 5 10 8 7 6 4 3 2 9
		 * 	 -> 1 5 8 10 7 6 4 3 2 9
		 *   -> 1 5 7 8 10 6 4 3 2 9
		 *   기본적으로 정렬이 되어있다 가정하면 속도가 빠르다.
		 */
		
		int j,temp;	// 값를 바꾸기위한 변수 선언
		int arr[] = {1,10,5,8,7,6,4,3,2,9};
		for(int i = 0; i< arr.length - 1; i ++) {
			j = i;
			while(arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				j --;
			}
		}
		for(int i = 0; i < arr.length; i ++) {
			System.out.print(arr[i] + " ");
		}
	}
	/*
	 * 시간 복잡도
	 * 10 + 9 + 8 + ... + 1
	 * N * (N + 1) / 2
	 * O(N^2)
	 * 선택, 버블 정렬보다 연산의 수가 가장 적다.
	 */
}