[Algorithm] 삽입 정렬(Insertion Sort)

 

안녕하세요. 신뇽이 되고싶은 미뇽입니다!

오늘은 정렬 알고리즘 중 삽입 정렬에 대해 알아보도록 하겠습니다!

 

들어가기에 앞서 앞으로의 정렬은 모두

오름차 순으로 정렬한다고 가정하겠습니다

삽입 정렬

- 데이터를 비교하면서 찾기 때문에 비교 정렬입니다.

- 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로하지 않기 때문에 제자리 정렬입니다.

- 안정 정렬입니다.

정렬 방법

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교합니다.

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

3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복합니다.

 

첫 번째 원소는 타겟이 되어도 비교할 원소가 없기 때문에 처음 원소부터 타겟이 될 필요가 없고 두번째 원소부터 타겟이 됩니다.

 

 

public class Insertion_Sort {
 
	public static void insertion_sort(int[] a) {
		insertion_sort(a, a.length);
	}
	
	private static void insertion_sort(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--;
			}
			
			/*
			 * 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
			 * 타겟 원소는 j번째 원소 뒤에 와야한다.
			 * 그러므로 타겟은 j + 1 에 위치하게 된다.
			 */
			a[j + 1] = target;	
		}
		
	}
}

 

[장점]

 

1. 추가적인 메모리 소비가 작습니다.

2. 거의 정렬된 경우 매우 효율적입니다. 즉, 최선의 경우 O(N)의 시간복잡도를 갖습니다.

3. 안정정렬이 가능합니다.

 

[단점]

 

1. 역순에 가까울 수록 매우 비효율적입니다. 즉, 최악의 경우 O(N^2)의 시간 복잡도를 갖습니다.

2. 데이터의 상태에 따라서 성능 편차가 매우 큽니다.

 

 

출처: https://st-lab.tistory.com/179

자바 [JAVA] - 삽입 정렬 (Insertion Sort)