[자료구조/알고리즘] 삽입 정렬(Insertion Sort)에 대해서

1.삽입 정렬이란?

삽입 정렬(Insertion Sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나로, 요소를 적절한 위치에 삽입하여 정렬하는 방법입니다. 배열의 일부를 정렬된 상태로 유지하면서 요소를 하나씩 삽입하여 전체 배열을 정렬합니다. 이 알고리즘은 작은 규모의 배열에서 높은 효율성을 보이며, 이미 정렬된 부분 배열에 새로운 요소를 삽입하는 과정이기 때문에 어떤 상태의 배열에서도 유용하게 사용될 수 있습니다.

2. 동작 방식

삽입 정렬의 동작 방식은 다음과 같습니다

1. 배열의 두 번째 요소부터 시작하여, 현재 요소를 기준으로 삼습니다.
2. 이전의 요소들은 이미 정렬된 상태로 간주합니다.
3. 현재 요소를 정렬된 부분 배열의 적절한 위치에 삽입합니다.
4. 배열 전체가 정렬될 때까지 위의 과정을 반복합니다.

구체적으로 삽입 정렬을 수행하는 방법은 다음과 같습니다

1. 배열의 두 번째 요소부터 시작하여 반복문을 돌면서 현재 요소를 key로 저장합니다.
2. key보다 큰 요소들을 오른쪽으로 이동시키면서 삽입할 위치를 찾습니다.
3. 삽입할 위치를 찾았으면 key를 해당 위치에 삽입합니다.
4. 위의 과정을 반복하여 배열이 정렬될 때까지 진행합니다.

3. 코드

#include <stdio.h>
void InsertionSort(int a[], int n) {
	int i, j, key;
	for (i = 1; i < n; i++) {
		key = a[i];
		for (j = i - 1; j >= 0; j--) {
			if (key >= a[j]) break;
			a[j + 1] = a[j];
		}
		a[j + 1] = key;
	}
}
int main(void) {
	int a[] = { 7, 12, 6, 11, 3, 8, 5, 2 };
	int i, n = sizeof(a) / sizeof(int);
	printf("정렬 전 : ");
	for (i = 0; i < n; i++) printf(" % d ", a[i]);
	InsertionSort(a, n);
	printf("\n삽입 정렬 후 : ");
	for (i = 0; i < n; i++) printf(" % d ", a[i]);
	return 0;
}

주어진 코드는 C 언어로 구현된 삽입 정렬 알고리즘입니다. 이 코드는 주어진 배열을 오름차순으로 정렬하는 함수 InsertionSort와 메인 함수 main으로 구성되어 있습니다.

함수 InsertionSort는 삽입 정렬 알고리즘을 구현한 것으로, 입력으로 주어진 배열 a를 오름차순으로 정렬합니다.

메인 함수 main은 주어진 배열 a를 출력하고, 삽입 정렬 알고리즘을 이용하여 정렬 후 배열을 다시 출력하는 역할을 합니다.

이 코드의 동작은 다음과 같습니다

1. 주어진 배열 a를 출력합니다. (정렬 전)
2. 함수 InsertionSort를 호출하여 배열 a를 오름차순으로 정렬합니다.
3. 정렬된 배열 a를 출력합니다. (삽입 정렬 후)

예를 들어, 주어진 배열 a가 {7, 12, 6, 11, 3, 8, 5, 2}인 경우, 출력은 다음과 같을 것입니다:

정렬 전: 7 12 6 11 3 8 5 2
삽입 정렬 후: 2 3 5 6 7 8 11 12

정렬이 잘 이루어진 것을 확인할 수 있습니다. 위 코드는 삽입 정렬 알고리즘을 제대로 구현하고 있으며, C 언어로 배열을 정렬하는 데 사용될 수 있습니다.

4. 시간 복잡도

시간 복잡도는 입력 크기 n에 대하여 알고리즘이 수행하는 기본 연산 횟수를 나타내는 것으로, 알고리즘의 성능을 평가하는 데 사용됩니다.

삽입 정렬의 시간 복잡도를 구하는 과정은 다음과 같이 진행됩니다

1. 단계별 최대 비교 횟수를 구하는데, 이는 1 + 2 + 3 + ... + (n-1)까지의 합입니다. 이는 등차수열의 합을 이용하여 (n-1) * n / 2로 구할 수 있습니다.
2. 따라서, 삽입 정렬의 시간 복잡도는 O(n^2)입니다.
3. 최선의 경우, 이미 정렬되어 있는 데이터에 대해서는 단계별로 한 번씩만 비교하면 되므로 O(n)의 시간 복잡도를 가집니다.
4. 반대로, 역으로 정렬되어 있는 경우에는 최대로 비교해야 하므로 O(n^2)의 시간 복잡도를 가집니다.

따라서 삽입 정렬은 일반적으로 입력 크기가 커질수록 비효율적인 알고리즘이며, 빠른 정렬 알고리즘들보다 성능이 떨어집니다. 하지만 작은 규모의 배열이나 이미 정렬된 배열을 다룰 때는 효과적인 알고리즘이라고 할 수 있습니다.