<삽입 정렬 구현>
[InsertionSort.c]
/*
* 알고리즘 - 삽입 정렬(Insertion Sort)
* 파일명: InsertionSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 삽입 정렬 구현
* 이전 버전 내용:
*/
#include <stdio.h>
void InsertionSort(int arr[], int n)
{
int i, j;
int insertData;
for (i = 1; i < n; i++) // 첫 번째가 아닌 두 번째 요소부터 마지막 요소까지 -> 첫 번째 요소는 데이터가 정렬이 되었다고 보기 때문
{
insertData = arr[i]; // 정렬 대상을 별도로 저장
for (j = i - 1; j >= 0; j--) // i-1 번째 요소부터 첫 번째 요소까지 역순으로 -> 정렬이 된 영역과 비교
{
if (arr[j] > insertData)
arr[j + 1] = arr[j]; // 비교 대상을 한 칸 이동
else
break; // 삽입 위치를 찾았으므로 반복문 탈출
}
arr[j + 1] = insertData; // 찾은 위치에 정렬 대상 삽입
}
}
int main()
{
int arr[5] = { 5, 3, 2, 4, 1 };
int i;
InsertionSort(arr, sizeof(arr) / sizeof(int));
for (i = 0; i < 5; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[삽입 정렬의 이해]
얼핏 보면 선택 정렬과 헷갈릴 수 있지만, 삽입 정렬은 ‘옮기면서 정렬이 되는’ 알고리즘이다.
선택 정렬은 데이터의 처음부터 끝까지 훑어가며 우선순위가 가장 높은 것은 왼쪽부터 쌓아가는 방식이다.
삽입 정렬은 데이터의 맨 처음이 정렬이 되어있다고 본다.
그리고 정렬이 된 영역과 안 된 영역을 나눠서 정렬이 안 된 영역의 데이터를 옮긴다.
옮기면서 기존의 정렬이 된 영역의 데이터와 비교해 정렬을 하는 방식.
좀 정리해서 표현하면 이렇게 할 수 있을 것 같다.
"맨 처음 데이터는 정렬이 되어있다고 하고 하나하나 우선순위를 비교해가며 정렬이 된 영역을 넓혀가는 방식이다."
위의 코드를 예시로 든다면, 맨 처음에는 5는 정렬이 되어있다 치고, 뒤에 있는 3과 비교하게 된다.
3의 우선 순위가 높다면 5를 한 칸 밀어내고 원래 5의 자리에 3이 들어가서 3, 5, 2, 4, 1이 된다.
그리고 정렬된 영역은 3, 5까지가 정렬이 된 상황.
그 다음은 2가 정렬 대상이 되고, 정렬 대상에 있는 3, 5와 비교를 하게 된다.
그래서 5와 비교했을 때, 5가 한 칸 밀려나고 3과 비교했을 때에도 3이 밀려난다.
그리고 마지막에 2가 들어오면서 2, 3, 5, 4, 1 순으로 2, 3, 5까지 정렬이 된 영역이 된다.
[성능 평가]
버블, 선택 정렬과 마찬가지로 데이터가 $n$개가 있다면 $n-1$단계를 거쳐서 정렬을 수행하게 된다.
최선의 경우는 정렬 대상의 대부분이 이미 정렬이 되어 있는 경우다.
이 때 삽입 정렬은 빠르게 동작할 수 있다.
완전히 정렬이 되어 있는 상태라고 가정하면 안쪽 for문의 조건은 항상 break문을 실행한다.
그래서 데이터의 이동은 일절 없게 되고, 조건 비교 역시 바깥쪽 for문의 횟수 이상 진행을 하지 않는다.
이 경우에는 $O(n)$이 될 수 있다.
최악의 경우일 때는, 삽입 정렬에서도 데이터 갯수가 $n$개일 때, 진행이 되는 비교와 이동의 횟수는 다음과 같아진다.
$1 + 2 + 3 + ... + (n-2) + (n-1)$
이는 이전의 정렬들과 마찬가지로 등차수열의 합으로 표현할 수 있으며, 다음과 같이 계산된다.
$$
\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}
$$
그리고 비교와 이동 연산 모두 안쪽의 for문에서 진행이 된다.
그렇기 때문에 삽입 정렬의 비교와 이동 연산에 대한 빅-오는 최악의 경우는 $O(n^2)$이다.
