Insertion Sort (삽입 정렬)

삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.

시간복잡도는 느리지만 구현은 어렵지 않은 편이다.

삽입 정렬 과정

1. 현재 index에 데이터를 선택한다.

2. 현재 선택한 데이터가 정렬된 범위에 삽입될 위치를 탐색한다.

3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.

4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.

5. 전체 데이터 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.

예를 들어 위와 같이 5번째 원소까지 정렬이 되어 있고, 6번째 원소를 정렬할 차례이다.

삽입 정렬은 앞 원소들이 모두 정렬되어 있는 상황이고 숫자 4를 적절한 위치에 삽입하여 정렬하려고 한다.

1. 먼저 4를 key로 지정하고 앞에 있는 원소(9)와 비교해서 앞에 있는 원소가 더 크면 swap한다.

2. swap이 일어난 이후, 그 앞에 있는 원소와 다시 비교하여 같은 작업을 반복한다.

3. 앞에 있는 원소가 key보다 작은 경우 탐색을 중단한다.

위와 같은 방식으로 원소가 오름차순 정렬을 유지한 채 진행하는 방식이 삽입 정렬이다.

얼마나 정렬되느냐에 따라 진행 횟수는 달라지지만 최대 n(n-1)/2 번 탐색이 진행된다.

따라서 시간 복잡도는 O(N^2) 이다.

for (int i = 1; i < N; i++) {
	// 선택 데이터
	int key = arr[i];
	// 비교 데이터
	int j = i - 1;
	
	while (j >= 0 && arr[j] > key) {
		arr[j + 1] = arr[j];
		j--;
	}
	arr[j + 1] = key;
}

ex)

1 9 8 6 4, key = 4

• 1 9 8 6 6 (j = 3)

• 1 9 8 8 6 (j = 2)

• 1 9 9 8 6 (j = 1)

• 1 4 9 8 6 (j = 0), arr[j + 1= key