[자료구조] 삽입 정렬 (insertion sort)

  삽입 정렬의 수행 순서는 다음과 같다.

 

1. 첫 번째 패스스루에서 임시로 인덱스 1(두 번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 인덱스 1에 값이 없으므로 공백이 생긴다.

이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.

 

2. 다음으로 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다.

공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 그 값을 오른쪽으로 시프트 한다.

값을 오른쪽으로 시프트 했으므로 자연히 공백이 왼쪽으로 옮겨진다. 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다.

 

3. 이제 임시로 제거한 값을 현재 공백에 삽입한다.

4. 배열이 완전히 정렬될 때까지 1단계부터 3단계를 반복한다.

#include <iostream>
#include <vector>
using namespace std;

void insertion_sort(vector<int>& array)
{
	for (int i = 1; i < (int)array.size(); i++)
	{
		int position = i;
		int tmp_value = array[i];

		while (position > 0 && array[position - 1] > tmp_value)
		{
			array[position] = array[position - 1];
			position = position - 1;
		}

		array[position] = tmp_value;
	}
}

int main()
{
	vector<int> test_array = { 4, 2, 7, 1, 3 };

	insertion_sort(test_array);

	for (int i = 0; i < (int)test_array.size(); i++)
		cout << test_array[i] << endl;
	return 0;
}

  삽입 정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입, 네 종류다. 삽입 정렬의 효율성을 분석하려면 각 단계별 총합을 계산해야 한다. 최악의 시나리오에서 삽입 정렬은 버블 정렬이나 선택 정렬과 시간 복잡도가 같다. 하지만 여기서 평균 시나리오를 고려해야 한다.

 

  평균 시나리오는 가장 자주 일어나는 경우를 말한다. 최악의 그리고 최선의 시나리오는 드물게 일어난다. 실제로는 대부분 평균 시나리오가 일어난다. 삽입 정렬의 경우에는 시나리오에 따라 성능이 크게 좌우된다. 최악의 시나리오에서 삽입 정렬은 N²단계가 걸린다. 평균 시나리오에서는 N²/2단계가 걸린다. 최선의 시나리오에서는 약 N단계가 걸린다.