[정렬]02. 삽입 정렬

1. 기본 컨셉

 - 앞에서부터 자료를 정렬해가는 방식이다.

 - 새로운 요소를 이미 정렬된 마지막 요소부터 비교해가며 적절한 자신의 위치에 삽입해 넣는다.

 

다음 동영상을 보고 전체적인 흐름을 이해해보자.

https://www.youtube.com/watch?v=ROalU379l3U

 

2. 정렬 과정

int [] src = {3,0,1,8,7,2,5,4,9,6};

 

 

3. 자바 코드

@Test
public void insertionSortTest() {
	data = new int[] { 3, 0, 1, 8, 7, 2, 5, 4, 9, 6 };
	// 0번째는 볼 필요 없다.
	int key = 0;// 비교를 시작하는 값
	int j = 0;// key가 삽입될 위치
	for (int i = 1; i < data.length; i++) {
		key = data[i];
		// key 보다 이미 정렬된 값이 더 클 경우 위치를 변경한다.
			for (j = i - 1; j >= 0 && data[j] > key; j--) {
			data[j + 1] = data[j];// 레코드를 오른쪽으로 이동한다.
		}
		// 다 이동했으면 key를 삽입한다.
		data[j + 1] = key;
		System.out.printf("%d번째: %s%n", i, Arrays.toString(data));
	}
	System.out.printf("정렬 완료: %s%n", Arrays.toString(data));
}

 

1번째: [0, 3, 1, 8, 7, 2, 5, 4, 9, 6]
2번째: [0, 1, 3, 8, 7, 2, 5, 4, 9, 6]
3번째: [0, 1, 3, 8, 7, 2, 5, 4, 9, 6]
4번째: [0, 1, 3, 7, 8, 2, 5, 4, 9, 6]
5번째: [0, 1, 2, 3, 7, 8, 5, 4, 9, 6]
6번째: [0, 1, 2, 3, 5, 7, 8, 4, 9, 6]
7번째: [0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
8번째: [0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
9번째: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
정렬 완료: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

4. 정리

삽입 정렬은 구현은 간단하지만 버블 정렬과 마찬가지로 비효율적인 정렬 방식으로 시간 복잡도는 O(n^2)을  갖는다.