[정렬 알고리즘] 삽입 정렬(Insertion Sort)

정렬 알고리즘인 삽입 정렬입니다.

배열의 앞쪽부터 시작해서 순회하면서 정렬을 합니다.

그리고 앞 부분의 정렬된 부분에서 선택된 값의 위치를 찾아서 이동시키는 알고리즘입니다.

기본적으로 버블 소트나 선택 정렬보다 성능이 좋고 구현이 간편한 장점이 있는 정렬입니다.

또한 추가적인 메모리가 크게 필요 없는 In-Place 알고리즘입니다.

반복문을 돌리기 위한 변수와 swap을 위한 변수 정도가 추가로 필요합니다.

그리고 같은 값이 있을 때 그 순서가 변경되지 않는 안정 정렬입니다.

Wiki에서 확인할 수 있는 삽입 정렬의 정렬 방식입니다.

http://en.wikipedia.org/wiki/Insertion_sort

이 영상이 삽입 정렬의 모든 것을 보여주고 있습니다.

두 번째 값부터 시작해서 각각의 값들이 앞부분의 정렬된 부분에서 자신의 자리를 찾습니다.

삽입 정렬의 소스 코드는 다음과 같습니다.

#include <iostream>

template <typename T>
void InsertionSort(T* arrVal, int nNum)
{
	int i, j;
	T remember;

	for (i = 1 ; i < nNum ; ++i)
	{
		remember = arrVal[i];
		for (j = i ; j > 0 ; --j)
		{
			if (arrVal[j - 1] > remember)
			{
				arrVal[j] = arrVal[j - 1];
			}
			else
			{
				break;
			}
		}
		arrVal[j] = remember;
	}
}

void main()
{
	using std::cout;
	using std::endl;

	int nVec[] = {5, 10, 6, 7, 9, 3, 4, 1, 2, 8};

	cout << "Before : ";
	for (int i = 0; i < _countof(nVec) ; ++i)
		cout << nVec[i] << " ";
	cout << endl;

	InsertionSort(nVec, _countof(nVec));

	cout << "After : ";
	for (int i = 0; i < _countof(nVec); ++i)
		cout << nVec[i] << " ";
	cout << endl;
}

코드도 상당히 단순합니다.

두 번째 원소부터 선택해서 계속 뒤로 이동하면서 앞 부분의 정렬된 부분과 비교합니다.

더 큰 값이 있으면 계속 뒤로 밀어내다가 같거나 작은 값이 있으면 멈추고 값을 위치시킵니다.

참고로 _countof()는 MS Visual C++에서만 사용이 가능한 것으로 알고 있습니다.

다른 컴파일러를 사용할 때는 sizeof() / sizeof()로 변경하거나 하면 됩니다.

비교적 간단한 정렬 알고리즘으로 역시 성능이 뛰어나진 않기 때문에 잘 사용되지 않습니다.