삽입 정렬(Insertion Sort)은 제자리(in-place)에서 수행되는 비교 기반 정렬 알고리즘입니다. 이 알고리즘은 각 요소를 이미 정렬된 부분 배열 내에서 자신의 올바른 위치에 삽입하는 방식으로 동작합니다. 즉, 현재 요소 앞에 있는 부분 배열은 항상 정렬된 상태를 유지합니다.
알고리즘 동작 원리
삽입 정렬의 기본적인 진행 과정은 다음과 같습니다.
1단계 − 인덱스 1부터 n-1까지 반복문을 수행합니다.
2단계 − 위치 i에 있는 요소 array[i]를 선택합니다.
3단계 − 선택한 요소를 array[0]부터 arr[i]까지의 정렬된 부분 배열 내에서 적절한 위치에 삽입합니다.
예시로 이해하기
배열 = [34, 7, 12, 90, 51]
i = 1일 때, arr[1] = 7이므로 부분 배열 arr[0] ~ arr[1] 범위 내에서 올바른 위치에 배치합니다.
[7, 34, 12, 90, 51]
i = 2일 때, arr[2] = 12이므로 부분 배열 arr[0] ~ arr[2] 범위 내에서 올바른 위치에 배치합니다.
[7, 12, 34, 90, 51]
i = 3일 때, arr[3] = 90이므로 부분 배열 arr[0] ~ arr[3] 범위 내에서 올바른 위치에 배치합니다.
[7, 12, 34, 90, 51]
i = 4일 때, arr[4] = 51이므로 부분 배열 arr[0] ~ arr[4] 범위 내에서 올바른 위치에 배치합니다.
[7, 12, 34, 51, 90]
재귀 삽입 정렬의 개념
재귀 삽입 정렬은 일반적인 반복 방식과 달리 역방향으로 문제를 접근합니다. 먼저 재귀적으로 recursiveInsertionSort() 함수를 호출하여 n-1개 요소로 이루어진 배열을 정렬한 뒤, 함수가 반환한 정렬된 배열에 n번째 요소를 자신의 위치에 삽입하는 방식으로 동작합니다.
재귀 호출이 n이 1이 될 때까지 반복되면, 그 시점부터는 각 재귀 단계가 돌아오면서 해당 요소가 정렬된 부분 배열에 순차적으로 삽입됩니다. 이는 분할 정복(divide and conquer) 사고방식과 유사한 구조라고 볼 수 있습니다.
재귀 삽입 정렬 C 프로그램
코드 예제
#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
if (n <= 1)
return;
recursiveInsertionSort( arr, n-1 );
int nth = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > nth){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = nth;
}
int main(){
int array[] = {34, 7, 12, 90, 51};
int n = sizeof(array)/sizeof(array[0]);
printf("Unsorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
recursiveInsertionSort(array, n);
printf("\nSorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
return 0;
}실행 결과
Unsorted Array: 34 7 12 90 51 Sorted Array: 7 12 34 51 90
시간 복잡도 및 특징
재귀 삽입 정렬의 시간 복잡도는 일반 삽입 정렬과 동일하게 최선의 경우 O(n), 최악의 경우 O(n²)입니다. 다만 재귀 호출로 인해 함수 호출 스택이 추가로 사용되므로, 메모리 측면에서는 반복 버전보다 다소 비효율적일 수 있습니다. 작은 크기의 배열이나 거의 정렬된 데이터를 다룰 때 효과적인 알고리즘입니다.