삽입 정렬(Insertion Sort)은 마치 손에 든 카드를 정리하듯 요소를 하나씩 제자리에 삽입하며 데이터를 정렬하는 대표적인 정렬 알고리즘입니다. 배열을 왼쪽에서 오른쪽으로 순회하되, 첫 번째 요소는 이미 정렬된 것으로 간주하고 나머지 요소들을 왼쪽의 정렬된 목록에 차례대로 삽입합니다. 각 요소는 자신이 들어갈 올바른 위치를 찾을 때까지 왼쪽 목록의 요소들과 계속 비교하게 됩니다.
삽입 정렬 알고리즘
int arr[5] = { 5, 4, 2, 1, 3 };
int i, j;
j = i + 1부터 j < 배열 크기까지 순회합니다.
각 요소 arr[j]를 arr[0 ~ i] 범위의 요소들과 비교하여 arr[i] < arr[j]이고 arr[i+1] >= arr[j]가 되는 위치를 찾습니다.
arr[j]를 해당 위치에 삽입하고, 더 큰 값들은 한 칸씩 오른쪽으로 이동시킵니다.
종료
재귀 삽입 정렬의 동작 원리
배열 길이가 1이면 그대로 반환합니다. (기저 사례)
인덱스 0부터 배열 크기 - 1까지의 요소들을 재귀적으로 정렬합니다.
마지막 요소를 정렬된 배열의 올바른 위치에 삽입합니다.
예제
입력 − Arr[] = { 5, 7, 2, 3, 1, 4 }; 길이 = 6
출력 − 정렬된 배열: 1 2 3 4 5 7
설명 −
5 7 2 3 1 4 → 5는 이미 정렬된 상태 5 7 2 3 1 4 → 7은 올바른 위치에 있음 2 5 7 3 1 4 → 2를 5, 7과 비교한 뒤 삽입 2 3 5 7 1 4 → 3을 5, 7과 비교한 뒤 삽입 1 2 3 5 7 4 → 1을 2, 3, 5, 7과 비교한 뒤 삽입 1 2 3 4 5 7 → 4를 5, 7과 비교한 뒤 삽입
입력 − Arr[] = { 1, 2, 3, 3, 2 };
출력 − 정렬된 배열: 1 2 2 3 3
설명 −
1, 2, 3, 3, 2 → 1은 이미 정렬된 상태 1, 2, 3, 3, 2 → 2는 올바른 위치에 있음 1, 2, 3, 3, 2 → 3은 올바른 위치에 있음 1, 2, 3, 3, 2 → 3은 올바른 위치에 있음 1, 2, 2, 3, 3 → 2를 3, 3과 비교한 뒤 삽입
프로그램의 접근 방식
재귀적 접근에서 기저 사례(base case)는 배열 길이가 1인 경우입니다. 그 외의 경우에는 재귀 호출을 통해 앞부분을 먼저 정렬한 뒤, 마지막 요소를 적절한 위치에 삽입하는 방식으로 동작합니다.
입력 배열 Arr[]와 요소 개수인 길이를 받습니다.
함수 recurInsSort(int arr[], int len)는 배열과 그 길이를 인자로 받아 재귀적으로 삽입 정렬을 수행합니다.
배열 길이가 1 이하이면 아무 작업 없이 반환(void)합니다.
그렇지 않으면 recurInsSort(arr, len - 1)을 재귀 호출하여 앞의 len - 1개 요소를 먼저 정렬합니다.
마지막 요소(key)를 왼쪽의 정렬된 부분과 비교하며, key보다 큰 요소들은 한 칸씩 오른쪽으로 밀어냅니다.
key를 올바른 위치에 삽입합니다.
모든 재귀 호출이 끝나 len이 1이 되면 재귀를 빠져나오며, 이때 배열은 정렬된 상태가 됩니다.
main 함수 안에서 정렬된 배열을 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void recurInsSort(int arr[], int len){
// 기저 사례: 요소가 1개 이하면 이미 정렬된 상태
if (len <= 1){
return;
}
// 앞의 len-1개 요소를 재귀적으로 정렬
recurInsSort(arr, len - 1);
// 마지막 요소를 정렬된 부분에 삽입
int key = arr[len - 1];
int j = len - 2;
while (j >= 0 && arr[j] > key){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
int main(){
int Arr[] = {21, 34, 20, 31, 78, 43, 66};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurInsSort(Arr, length);
cout<<"Sorted array : ";
for(int i=0;i<length;i++){
cout<<Arr[i]<<" ";
}
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Sorted array : 20 21 31 34 43 66 78
시간 및 공간 복잡도
시간 복잡도: 최선의 경우(이미 정렬된 입력) O(n), 평균 및 최악의 경우 O(n²)
공간 복잡도: 재귀 호출 스택으로 인해 O(n)