<알고리즘: 삽입정렬> 기본개념과 설명 및 코드

# 삽입 정렬

---

 삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 마치 뒤섞여 있는 트럼프 카드를 순서대로 정리하는 모습과 같다. 카드를 한 장씩 뽑아 카드의 값에 따라 적절한 곳에 끼워 넣는 것을 반복하다 보면 결국 모든 카드가 순서대로 정리된다. 마찬가지로 데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하다 보면 정렬된 데이터 집합을 얻을 수 있다.

 삽입 정렬은 구현이 간단해서 버블 정렬과 함께 프로그래머들에게 애용되는 알고리즘 중 하나다. 성능 또한 버블 정렬과 비슷하다. 이 알고리즘은 아래의 과정을 통해 정렬을 수행한다. 오름차순으로 정렬할 때를 가정한다.

• 데이터 집합에서 정렬 대상이 되는 요소들을 선택한다. 정렬 대상은 왼쪽부터 선택해나가며, 그 범위가 처음에는 2개지만, 반복 횟수가 늘어날 때마다 1씩 늘어난다. 데이터 집합의 크기를 n이라고 했을 때 반복의 횟수는 최대 n - 1 번이다. (2개씩 비교하면서 시작되기 때문이다.)
  
  
• 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다. 그렇지 않다면, 이 요소를 정렬 대상에서 뽑아내고, 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다. 적절한 곳의 기준은 데이터 집합의 가장 왼쪽을 기준으로 자신보다 더 작은 요소가 없는 위치를 말한다.
  
  
• 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로 이동시킨다. 이렇게 이동하면, 새로이 위치할 곳의 자리가 비게 된다. 이제 이 새로 생긴 자리에 뽑았던 요소를 삽입하면 된다.

1) 직접적인 예시를 통해 삽입정렬의 과정을 살펴보도록 하자. 아래의 배열의 요소들을 편의상 '카드'라고 가정하자. 그림과 같이 6장의 카드가 존재한다고 생각하고 시작한다.

2) 우선 앞의 두 장의 카드(5와 1)를 정렬 대상으로 선택한다. 그리고 선택한 두 장의 카드 중 오른쪽 카드가 왼쪽보다 큰 지 비교한다. 왼쪽이 5, 오른쪽이 1 이므로 오른쪽 카드가 더 작다. 이 카드를 뽑는다.

3) 뽑아낸 카드 1은 5보다 앞에 위치해야 한다. 따라서 1이 들어갈 자리를 마련하기 위해 5를 오른쪽으로 한 자리 옮긴다.

4) 5가 오른쪽으로 이동하면서 맨 좌측에 빈 자리가 생겼다. 이 자리에 1을 삽입한다. 이로써 첫 번째 반복이 끝났다.

5) 첫 번째 반복이 끝났으므로 정렬 대상의 범위를 하나 더 늘린다. 3장의 카드를 비교해보자. 비교대상 중 마지막 카드가 6인데, 바로 앞에 있는 카드 5와 비교한다. 6이 더 크므로 교체해야할 필요가 없다. 바로 직전 자리와 검사하는 이유는, 그 전의 자릿수들은 이미 이전 정렬을 통해 정렬이 되어 있는 상태기 때문이다. 따라서 다음 반복으로 바로 넘어간다.

6) 이번엔 정렬 대상의 마지막 요소가 4 카드다. 바로 앞에 있는 6보다 작으므로 카드 4를 뽑는다.

7) 맨 좌측의 1부터 4가 들어갈 자리가 있는지 모색한다. 4가 들어갈 적절한 곳은 5 앞에 존재한다. 따라서 정렬 대상 중 4보다 큰 5, 6 카드를 우측으로 한 자리씩 옮긴다.

8) 5와 6카드를 옮김으로써 생긴 빈 자리에 4를 삽입한다. 이런 식으로 두 번만 더 반복하면 이 데이터의 집합은 완전히 정렬될 것이다.

// 삽입 정렬은 정렬 대상을 줄여나가는 버블 정렬과는 반대로, 정렬 대상을 하나씩 늘려간다.

# 삽입 정렬의 효율

---

 위에서 다룬 예제는 데이터 집합의 크기가 6이다. 정렬을 위한 반복은 5회 수행한다. 그리고 데이터 집합 내 요소들간의 비교는 정렬 대상의 범위가 2개일 때 한 번, 3개일 때 두 번, 4개일 때 3번, ..., 6개일 때 5번 수행한다. 이로부터 삽입 정렬의 비교 횟수를 계산해 보면 다음과 같은 공식을 유도할 수 있다..

삽입 정렬의 비교 횟수 = 1 + 2 + ... + (n - 2) + (n - 1) = n(n - 1) / 2

 비교 횟수가 버블 정렬과 동일하다. 버블 정렬과의 다른 점은, 바로 앞의 요소와 검사했을 때 데이터가 잘 정돈되어 있다면 비교 루프를 거치지 않는다는 점이다. 즉 데이터가 정렬되어 있는 경우는 비교를 딱 (n - 1)번만 수행하게 된다. 바로 앞에 있는 데이터와 비교하게 되는 것이니 2개씩 묶어 비교한다고 생각하면 (n - 1)번이 나온다.

 따라서 최선의 경우 (n - 1)과 최악의 경우 ( n(n-1) / 2 )의 평균을 내보면, (n^2 + n - 2) / 2 정도가 나온다. 평균적으로 버블정렬보다 삽입 정렬의 성능이 더 낫다는 뜻이다. 버블은 정렬이 되어 있건 말건 모든 요소를 비교하게끔 설계되어 있고 삽입은 정렬되어 있는 것이라면 다음 루틴으로 넘어가기 때문이다.

# 삽입 정렬 코드

---

 삽입 정렬이 잘 작동하는지 테스트할 수 있는 코드다.

/*************************************************
 ** Insertion Sort Algorithm
*************************************************/

#include <stdio.h>
#include <string.h>

void insertion_sort(int dataSet[], int length)
{
	int i, j; // 반복을 위한 변수
	int value; // 빼낸 값을 기억해놓기 위한 변수

	// 1부터 시작하는 이유는 인덱스가 하나 더 작은 값과 비교하기 위함이다.
	// 즉, 첫 비교는 dataSet[0] 과 dataSet[1]을 비교하게 되는 것이다.
	for (i = 1; i < length; i++)
	{
		if (dataSet[i - 1] <= dataSet[i]) // 정렬이 되어 있는 상황
			continue; // 아래의 루틴을 진행할 필요가 없으므로 continue
		
		// 아래의 진행은 정렬이 안되어 있는 상태일 때 진행된다.
		value = dataSet[i]; // i에 위치한 값을 빼낸다.
		
		// 빼낸 값을 배열의 첫 요소부터 쭈욱 비교하기 시작한다.
		// 어디에 위치시키는 게 좋을지를 정하는 과정이다.
		for (j = 0; j < i; j++)
		{
			// 적절한 위치를 발견, 나 보다 큰 값의 좌측에 위치해야 한다.
			if (dataSet[j] > value)
			{	
				// 들어갈 위치를 확보하기 위해 우측으로 요소들을 옮긴다.
				// memmove 함수를 사용한다. 원본데이터를 이동시키는 함수다.
				memmove(&dataSet[j + 1], // 첫 번째 매개변수는 이사할 새로운 주소 
					&dataSet[j], // 두 번째 매개변수는 이사할 데이터가 어디서 부터인지를 나타내는 주소
					sizeof(dataSet[0]) * (i - j)); // 세 번째 매개변수는 얼마만큼 옮길건지를 표현하는 byte
				
				// 들어갈 자리 j가 확보됐으니 이 위치에 빼낸 값을 껴넣는다.
				dataSet[j] = value;
				break;
			}
		}
	}
}

int main()
{
	int dataSet[] = { 6,4,2,3,1,5 };

	// dataSet의 길이를 측정한다.
	int length = sizeof dataSet / sizeof dataSet[0];
	
	int i = 0; // 반복을 위한 변수
	insertion_sort(dataSet, length); // 삽입정렬 함수 실행

	for (i = 0; i < length; i++) // 정렬이 잘 되었는지 확인을 위한 출력 반복문
	{
		printf("%d ", dataSet[i]);
	}

	putchar('\n'); // 딱 한 바이트를 출력할 수 있는 putchar 함수

	return 0;
}

/*************************************************
 ** End Line
*************************************************/

데브맷 풀이.c