[알고리즘] 정렬 - 삽입 정렬, O(N^2)

  삽입 정렬 역시 Θ(N^2) 의 시간 복잡도를 지닌 정렬 알고리즘이다. 사실 정렬 알고리즘은 어디서부터 정렬할지 정하기 나름이지만 필자는 삽입 정렬을 왼쪽부터 정렬된 상태를 늘려나간다고 공부했다. 개념적으로 왼쪽부터 정렬된 공간을 1씩 늘려나간다고 생각할 수 있다.

 

    삽입 정렬 (Insertion Sort) 소개             

  삽입 정렬은 왼쪽부터 정렬된 공간을 1씩 순차적으로 늘려나가면서 정렬하는 과정이다. 차례대로 원소를 보면서 왼쪽의 정렬된 공간의 알맞은 자리에 삽입하면서 정렬된다는 의미에서 삽입 정렬이라는 이름이 붙게 되었다. 글로만 설명하려니까 어려우므로 그림을 보면서 이해하면 될 것 같다.

삽입 정렬 과정의 도식도

 

  그림에서는 알맞은 자리로 한 번에 이동하는 것처럼 표시했지만 사실은 현재 삽입하려는 원소를 바로 아래의 인덱스부터 차례대로 내려가면서 비교하여 자신의 자리를 찾는 방식이다. 실제로 구현할 때에는 비교하여 내려가면서 기준 원소보다 큰 값들을 1칸씩 올리면서 내려간다.

2를 삽입하는 과정 도식

 

  비교하고자 하는 값을 따로 저장해두고, 순차적으로 비교해 내려가면서 값의 이동도 동시에 진행한다. 결국 N개의 원소에 대해 각각의 원소 왼쪽에 있는 원소의 개수만큼 비교가 일어나므로 삽입정렬, 버블정렬과 마찬가지로 1+2+...+(N-2)+(N-1) = (N-1)*N/2 회의 비교가 일어난다. 다만 이 비교횟수는 모든 원소가 최대 횟수로 비교를 하는 것이기 때문에 비교 원소가 항상 왼쪽에 있는 원소들보다 작은 경우이다. 이를 전체적으로 생각하면 역순으로 정렬된 데이터라고 생각할 수 있다. 이는 최악의 경우로, 삽입 정렬이 최악의 경우 (N^2)의 시간 복잡도를 가진다. 반대로, 처음부터 정렬된 데이터의 경우 처음을 제외한 모든 원소가 1번의 비교만 하기 때문에 총 N-1회의 비교가 이루어지고, Θ(N)의 시간 복잡도를 갖게 된다. 이는 flag를 이용해 개선한 버블 정렬과 동일한 결과이다. 다만 버블 정렬과 다르게 알고리즘의 자체적인 과정에서 자연스럽게 비교 횟수가 최적화되는 경우라고 할 수 있다.

 

    C++ 구현             

#include <iostream>

void InsertionSort(int* _arr, int _size)
{
	// 인덱스 1인 원소부터 올라가면서 기준 원소로 설정
	for (int i = 1; i < _size; ++i)
	{
		int pivot = _arr[i];

		// 기준 원소의 바로 직전 원소부터 차례대로 내려가면서 비교. -1까지로 설정한 이유는 pivot이 가장 작은 경우도 자연스럽게 처리해주기 위해.
		for (int j = i - 1; j >= -1; --j)
		{
			// pivot이 비교원소보다 작고, j가 0 이상인 경우 (-1 인덱스가 불가능하므로)
			if (_arr[j] > pivot && j>=0)
			{
				// 비교원소를 1칸 올림
				_arr[j + 1] = _arr[j];
			}
			// pivot이 비교원소보다 작거나 같아지는 순간 또는 모두 비교했을 때 pivot이 가장 작은 경우
			else
			{
				// 오른쪽 자리에 pivot 값을 대입하고 종료
				_arr[j + 1] = pivot;
				break;
			}
		}

	}
}

int main()
{
	int arr[10] = { 5,1,2,3,9,8,4,6,10,7 };
	InsertionSort(arr, 10);

	return 0;
}

 

  구현하다 보니 pivot (기준 원소)이 가장 작은 경우, 비교가 끝난 시점을 처리하는 게 살짝 까다로웠다. 이 부분의 구현으로 다른 방법을 참고할 필요가 있을 것 같다.