이전에 다룬 버블 정렬Bubble Sort과 선택 정렬Selection Sort보다 조금 더 효율적인 삽입 정렬Insertion Sort에 대해 다뤄볼게요!

삽입 정렬

삽입 정렬Insertion Sort은 2번째 원소부터 시작해서, 이전 인덱스의 원소보다 작을 때까지 이전 인덱스로 이동해서 정렬하는 방식이에요.

1. n번째 원소를 임시 변수에 저장합니다($1 \leq n < n$)
2. n-1번째 '이전' 원소부터 비교하여 임시 변수 값보다 작은 원소가 나올때까지 진행합니다.
   2-1. 이 과정에서 '이전' 원소를 뒤로 삽입을 진행해요.
3. 진행이 완료되면 1번으로 돌아가 반복합니다.

그림

특징

시간복잡도는 최악의 경우 $O(n^{2})$이긴 합니다만, 이미 정렬이 된 경우엔 교환 과정을 거치지 않아, 최선의 시간 복잡도는 $O(n)$을 가지게 됩니다.

배열 추가가 따로 필요하지 않아 In-place하며, Stable한 정렬입니다.

한번 진행하면 해당 원소가 정확한 위치에 지정된다는 점에서 선택 정렬Selection Sort과 유사하지만 정확한 위치를 찾기 위해 모든 원소를 찾아 비교하는 선택 정렬Selection Sort과 달리 삽입 정렬Selection Sort은 해당 위치를 찾는데 필요한 만큼의 요소만 탐색해서 훨씬 효율적으로 찾는데 차이가 있습니다.

소스

template<typename T>
class InsertionSort
{
public:
	static void sort(vector<T>& arr)
	{
		for(size_t i = 1; i < arr.size(); ++i){
			T tmpValue = arr[i];
			int prev = i - 1;
			while((prev >= 0) && tmpValue < arr[prev]){
				arr[prev + 1] = arr[prev];
				--prev;
			}
			arr[prev + 1] = tmpValue;
		}
	}
};