삽입 정렬(Insertion Sort)

개념 요약

• Selection Sort와 유사하지만, 더 효율적인 정렬 방법이다.
• 자료의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 방법이다.

 

---

정렬 과정

1. 시작 인덱스를 2번째 인덱스부터 시작한다.
2. 시작 인덱스 값과 이전의 인덱스 값을 비교하여 삽입한다.
3. 시작 인덱스 + 1을 2번 과정으로 반복한다. 

 

---

코드

void	insertion_sort(std::vector<int> &unsorted_array)
{
	int	temp = 0, prev_idx = 0;
	// 2번째 인덱스 부터 시작
	for (int idx = 1; idx < unsorted_array.size(); ++idx)
	{
		// 현재 인덱스 값, 루프를 돌 인덱스 저장
		temp = unsorted_array[idx];
		prev_idx = idx - 1;
		while (prev_idx >= 0 && unsorted_array[prev_idx] > temp)
		{
			// 뒤로 땡기기
			unsorted_array[prev_idx + 1] = unsorted_array[prev_idx];
			--prev_idx;
		}
		// 찾은 위치에 삽입
		unsorted_array[prev_idx + 1] = temp;
	}
}

 

---

시간 복잡도

• 최악의 경우는 $O(n^2)$이다.
• 하지만 모두 정렬되어있는 경우 $O(n)$이고 평균적으로 $O(n^2)$이다.

 

---

공간 복잡도

• 주어진 배열 내에서 swap 하므로 $O(n)$이다.

 

---

장단점

• 알고리즘이 단순하고 정렬되어있을 경우엔 매우 효율적이다.
• 버블 정렬, 선택 정렬보다 상대적으로 빠르며, 안정한 정렬이다.
• 평균, 최악의 시간 복잡도가 $O(n^2)$으로 비효율적이다.