[ALGORITHM] 18. 삽입 정렬 구현하기

삽입 정렬(Insertion Sort)은 현재 위치에서 그 보다 앞(혹은 더 작은 값)의 원소들과 비교하여

자신이 들어갈 위치를 찾아 삽입하는 방식으로 동작하며,

정렬되지 않은 부분의 원소를 하나씩 정렬된 부분으로 삽입하면서 정렬이 완료된다.

 

template<typename T>
void insertion_sort(std::vector<T>& data) { //최악 O(n^2)
										 
	int n = data.size();

	for (int i = 1; i < n; i++) {

		T key = data[i];
		int j = (i - 1);

		while (j >= 0 && data[j] > key) {

			data[j + 1] = data[j];
			j--;
		}

		data[j + 1] = key;
	}
}

 

 

특징

 

1. 안정성 : 동일한 키 값을 가진 원소 간의 상대적인 순서가 정렬 정후에도 유지된다.

2. 원본 배열에서 정렬 진행 : 정렬을 진행하면서 추가적인 배열이나 자료구조를 사용하지 않고,

주어진 배열 자체의 원소를 이용해 정렬을 수행한다. (정렬된 부분을 제외한 나머지 부분의 순서가 변하지 않음)

3. 작은 데이터셋에 적합 : 데이터셋의 크기가 작은 경우에는 다른 정렬 알고리즘에 비해 성능이 나쁘지 않을 수 있다.

 

 

장점

 

1. 정렬된 리스트에 대한 성능이 좋다 : 정렬된 데이터나 정렬된 상태에 가까운 데이터에 대해

비교적 빠른 성능을 보일 수 있다. (최선과 최악의 편차가 클 수 있음)

 

 

단점

 

1. 효율적이지 않다 : 평균 및 최악의 경우 O(n²)이므로 큰 데이터셋에 대해서는 비효율적이다.

2. 큰 데이터셋에 부적합 : 큰 데이터셋에 대해선 다른 효율적인 알고리즘을 권장하며,

삽입 정렬은 작은 데이터셋이나 정렬이 이미 어느 정도 진행된 상태에서 활용하는 게 좋다.

3. 안정성은 유지되나 불안정 정렬보다 느리다 : 안정성을 유지하면서 정렬을 진행하는 삽입 정렬은

불안정 정렬보다 일반적으로 느리며, 특히 큰 데이터셋에서는 다른 안정한 알고리즘을 사용하는 게 더 효율적이다.