[C++] iterator를 이용한 삽입 정렬(Insertion sorting) 구현

- 알고리듬

주어진 vector를 이중 loop를 이용하여 정렬한다. 우선 첫 루프는 이전 요소들과 비교하기 위한 고정 요소를 set하는 루프이다. 고정 요소는 두 번째 요소부터 시작한다.두 번째 루프는 첫 루프의 고정 요소와 비교할 요소를 set하고 정렬을 위한 조건을 검사한다. 내림 차순을 기준으로 고정 요소가 더 크다면 비교 요소의 앞에 삽입되어야 한다. 비교 요소가 더 크다면 올바른 순서이므로 고정 요소이전까지 증가시키며 비교한다.

여기서 핵심 부분은 고정 요소를 비교 요소 앞에 삽입하는 과정이다. vector::insert(iterator, value)를 이용하면 iterator가 가리키는 위치에 value를 삽입할 수 있다.  예를 들어 위 그림의 벡터에서 2를 가리키는 반복자와 3을 인자로 주면 4와 2사이에 3이 삽입되며 2~10 요소들이 한 칸씩 밀려난다. 즉 벡터는 { 4, 3, 2, 1, 3, 6, 8, 10 }이 된다. insert 후 vector::erase를 통해 기존의 3을 삭제해주어야 한다. 기존의 3을 삭제하면 또 그 뒤의 요소들을 정렬하기 위해 한 칸씩 모두 앞으로 당긴다.

즉 한 번의 정렬을 위해 요소들이 두번씩 정렬이 된다. 배보다 배꼽이 더 큰격이다. 벡터의 특징이 인덱스를 지원하는 가변 배열이기 때문에 순서를 유지해주기 위해 중간에 원소가 삽입되거나 삭제될 때마다 뒤 쪽 요소들을 재정렬해줘야 하기 때문에 오버헤드가 크다.
추가되거나 삭제된 요소 뒤에 1000개의 요소가 있다고 생각해보자. 삭제 한 번에 1000개의 요소를 재정렬해주어야 한다. 

그렇다면 재정렬을 줄일 수 있는 방법을 생각해보자. 내가 생각한 방법은 erase를 통해 요소를 제거하지 말고 마지막 요소를 해당 요소에 덮어 씌움으로써 재정렬을 막는 것이다. 즉 위 벡터에서 3을 2 앞에 삽입한다고 생각해보자.

3을 삽입한다.
4 3 2 1 3 6 8 10

기존의 3을 제거하기 위해 마지막 요소를 3 위치에 덮어쓴다.
4 3 2 1 3 6 8 10
4 3 2 1 10 6 8 10

마지막 요소를 제거한다.
4 3 2 1 10 6 8 10
4 3 2 1 10 6 8


이런 방식으로 최대한의 오버헤드를 줄이는 것이다. 이제 코드를 보고 비교해보자.

void SortDescending(std::vector<int>& v)
{
	using vec_size = vector<int>::size_type;
	using iter = vector<int>::iterator;

	vec_size size = v.size();

	for (vec_size i = 1; i != size; ++i)
	{
		for (vec_size j = 0; j != i; ++j)
		{
			if (v[i] > v[j])
			{
				// erase 사용
				v.insert(v.begin() + j, v[i]);
				v.erase(v.begin() + i + 1);
                
				// 덮어씌우기
				v.insert(v.begin() + j, v[i]); // j 위치에 v[i]를 삽입합니다.
				v[i + 1] = v.back();
				v.pop_back();
                
				// 공통
				break;
			}
		}
	}
}

두 코드의 수행 시간을 비교해보자.

다음은 1000개의 요소를 정렬했을 때 소요 시간이다. (Debug 모드)


- erase 사용
대략 18~20ms 로 측정된다.

- 덮어 씌우기
대략 12~15ms 로 측정된다.

다음은 20000개의 요소를 정렬했을 때 소요 시간이다. (Release 모드)

- erase 사용
대략 73~83ms 로 측정된다.

- 덮어 씌우기
대략 60~70ms 로 측정된다.

생각보다 크게 차이가 나진 않는다.

참고로 swap 방식은 거의 130ms 정도로 거의 2배가 차이난다.