삽입 정렬 (Insertion Sort)
개요
삽입 정렬은 배열을 정렬할 때, 두 번째 원소부터 시작하여 왼쪽에 정렬된 부분에 적절한 위치로 값을 삽입하는 방식입니다.
이 예제는 while문 없이 for문만 사용하고, 각 단계마다 배열 상태를 출력하여 정렬 과정을 시각적으로 확인할 수 있도록 구성되어 있습니다.
정렬 알고리즘 설명
- 두 번째 원소부터 시작 (
i = 1) - 현재 값(
key)을 왼쪽 정렬된 구간의 값들과 비교 - key보다 큰 값은 한 칸씩 뒤로 이동
- 적절한 위치에 key 삽입
- 이 과정을 배열 끝까지 반복
삽입 정렬 시간 복잡도
| 경우 | 비교 횟수 | 시간 복잡도 |
|---|---|---|
| 최선 (Best) | n - 1 | O(n) |
| 평균 (Average) | 약 n² / 4 | O(n²) |
| 최악 (Worst) | n(n - 1) / 2 | O(n²) |
예제 코드
#include <stdio.h>
void insertion_sort(int arr[], int n);
void print_array(int arr[], int n);
int main() {
int arr[6] = {5, 3, 4, 1, 2, 6};
printf("정렬 전 배열: ");
print_array(arr, 6);
insertion_sort(arr, 6);
printf("정렬 후 배열: ");
print_array(arr, 6);
return 0;
}
void insertion_sort(int arr[], int n) {
int key;
for (int i = 1; i < n; i++) {
key = arr[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (arr[j] > key)
arr[j + 1] = arr[j];
else
break;
}
arr[j + 1] = key;
// i회전 후 배열 상태 출력
printf("%d회전 후: ", i);
print_array(arr, n);
}
}
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}실행 예시 (입력: {5, 3, 4, 1, 2, 6})
정렬 전 배열: 5 3 4 1 2 6
1회전 후: 3 5 4 1 2 6
2회전 후: 3 4 5 1 2 6
3회전 후: 1 3 4 5 2 6
4회전 후: 1 2 3 4 5 6
5회전 후: 1 2 3 4 5 6
정렬 후 배열: 1 2 3 4 5 6특징 요약
- 거의 정렬된 경우 매우 빠름 (최선 O(n))
- 데이터가 랜덤하거나 역순일 경우 느림 (평균/최악 O(n²))
- 코드 구현이 간단함
- 작은 데이터나 정렬된 데이터에 실용적