삽입 정렬(Insertion sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (두 번째 원소부터 시작한다.)

2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.

3. 타켓이 되는 숫자가 이전 위치에 있던 원소보다 크다면, 타켓 숫자 뒤에 바로 삽입한다.

3. 현재 타켓의 다음 숫자를 타켓으로 하여, 1~3번을 반복한다.

자바로 구현한 코드는 다음과 같다.

static void insertion_sort(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
    	int target = arr[i];
        
        int j = (i-1);
        
        while(j >= 0 && target < arr[j]) {
        	arr[j + 1] = arr[j];
        	j--;
        }
        
        arr[j + 1] = target;
    
    }
}

시간복잡도는 O(n²) 이다.

거품 정렬과 선택 정렬과 시간복잡도가 평균, 최악일 때는 동일하나
최선인 경우, O(n)이 된다. (숫자가 모두 제대로 정렬되어 있는 경우)

---

참조한 책 및 사이트

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
https://hanhyx.tistory.com/38