삽입 정렬 (Insertion Sort)

정의

---

• 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복
• 1개짜리 배열에서 시작하여 이미 정렬된 배열의 크기를 하나씩 늘린다

과정

---

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫번째 타겟은 두번째 원소부터 시작)
2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다
3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

장점 & 단점

---

• 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복
• 1개짜리 배열에서 시작하여 이미 정렬된 배열의 크기를 하나씩 늘린다

코드

---

private static void insertionSort(int[] a, int size) {

	for(int i = 1; i < size; i++) {
    	int target = a[i];
        
        int j = i - 1; //타겟의 이전 위치부터 시작
        
        while(j >= 0 && target < a[j]) {
        	a[j+1] = a[j]; //이전 원소를 한 칸씩 뒤로 미룬다.
            j--;
        }
        
        a[j + 1] = target;
    }
}

장점 & 단점

---

-장점

1. 추가적인 메모리 소비가 작다
2. 거의 정렬된 경우 O(N)의 시간복잡도를 가지며 매우 효율적이다
3. 안정 정렬이 가능하다

-단점

1. 역순에 가까울 수록 매우 비효율적이다. 최악의 경우 O(N^2)의 시간 복잡도를 갖는다
2. 데이터의 상태에 따라서 성능 편차가 매우 크다

시간복잡도

---

-최선 : O(N) -평균 & 최악 : O(N^2)