📌 삽입 정렬 (Insertion Sort)
1. 개념
삽입 정렬은 배열의 왼쪽부터 차례대로 하나씩 원소를 꺼내, 그것을 앞에 있는 정렬된 부분에 적절한 위치에 삽입하면서 정렬을 완성하는 방식이다.
→ 마치 카드를 손에 들고 정렬하는 것과 비슷하다.
2. 정렬 과정 (동작 방식)
- 두 번째 원소부터 시작한다.
- 현재 원소(
key)를 정렬된 부분(왼쪽)에 있는 원소들과 비교한다.
key보다 큰 원소들은 오른쪽으로 한 칸씩 이동시킨다.key를 빈자리에 삽입한다.
3. 예시
int arr[] = {5, 2, 4, 6, 1, 3};
| 단계 | key | 결과 |
|---|
| 초기 | - | 5 2 4 6 1 3 |
| 1단계 | 2 | 2 5 4 6 1 3 |
| 2단계 | 4 | 2 4 5 6 1 3 |
| 3단계 | 6 | 2 4 5 6 1 3 |
| 4단계 | 1 | 1 2 4 5 6 3 |
| 5단계 | 3 | 1 2 3 4 5 6 |
코드 (C 언어)
void insertionSort(int arr[], int n){
int i, j, key;
for(i = 1; i < n; i++){
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
4. 시간 복잡도
| 상황 | 시간 복잡도 | 설명 |
|---|
| 최선 (이미 정렬됨) | O(n) | 비교만 하고 이동 없음 |
| 평균 | O(n²) | 일반적인 경우 |
| 최악 (역순 정렬) | O(n²) | 매번 모든 값 이동 필요 |
5. 특징 요약
- 정렬 방식: 내부 정렬, 제자리 정렬 (In-place)
- 안정성: 안정 정렬 (Stable Sort)
- 장점: 구현이 간단, 거의 정렬된 배열에서 효율적
- 단점: 대규모 데이터에 비효율적 (O(n²))
6. 예시 코드
#include <stdio.h>
void insertionSort(int arr[], int n){
int i, j, key;
for(i = 1; i < n; i++){
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
int main()
{
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("정렬 결과: ");
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
✅ 정리
삽입 정렬은 간단한 알고리즘이지만, 배열이 거의 정렬되어 있는 경우 빠르게 동작하며, 데이터 개수가 적을 때 유용하다.
📌 Selection Sort (선택 정렬)
✅ 개념
- Selection Sort는 정렬되지 않은 데이터 중에서 가장 작은(또는 큰) 값을 선택하여 앞쪽의 자리와 교환하는 방식으로 동작하는 정렬 알고리즘이다.
- 이름 그대로 "선택"에 기반하여, 각 반복(iteration)에서 가장 적합한 값을 골라 위치를 확정한다.
🔁 알고리즘 동작 흐름
- 배열의 첫 번째 원소부터 시작해서 오른쪽으로 비교해나가며 가장 작은 값(min)을 찾음.
- 찾은 가장 작은 값을 현재 인덱스(i)의 값과 교환(swap).
- 이후 i를 증가시키며 남은 배열 구간에서 반복 수행.
- 전체 배열의 길이가 n일 때, 총 n-1번 outer 루프가 돌면 정렬이 완료됨.
🧠 단계별 설명 (오름차순 예시)
배열: [5, 2, 4, 6, 1, 3]
- i = 0 → 최소값 1 → index 4 → swap(0,4) →
[1, 2, 4, 6, 5, 3]
- i = 1 → 최소값 2 → 그대로 →
[1, 2, 4, 6, 5, 3]
- i = 2 → 최소값 3 → index 5 → swap(2,5) →
[1, 2, 3, 6, 5, 4]
- i = 3 → 최소값 4 → index 5 → swap(3,5) →
[1, 2, 3, 4, 5, 6]
- i = 4 → 최소값 5 → 그대로 → 완료
🔍 루프 범위
- Outer Loop (i):
0 ~ n-2 → 기준 요소 선택
- Inner Loop (j):
i+1 ~ n-1 → 최소값 탐색
⏱ 시간 복잡도
| 경우 | 시간 복잡도 | 설명 |
|---|
| 최악 | O(n²) | 모든 쌍 비교 필요 |
| 평균 | O(n²) | 비교 횟수 고정 |
| 최선 | O(n²) | 이미 정렬되어 있어도 비교함 |
- 비교 횟수: 항상 n(n-1)/2
- 교환 횟수: 최대 n-1
⚙️ 공간 복잡도
🟩 장점
- 구현이 매우 단순하고 직관적
- 교환 횟수가 적음 → Bubble Sort보다 효율적일 수 있음
- 입력 데이터 상태에 관계없이 일정한 성능
🟥 단점
- 비교 횟수가 많아 성능이 좋지 않음
- 대규모 데이터에는 부적합
- 불안정 정렬: 동일한 값의 상대적 순서가 바뀔 수 있음
🧷 요약 정리표
| 항목 | 내용 |
|---|
| 정렬 방식 | 선택 정렬 (Selection-Based) |
| 안정성 | ❌ 불안정 정렬 |
| 시간 복잡도 | O(n²) (최선, 평균, 최악 모두 동일) |
| 공간 복잡도 | O(1) (추가 메모리 불필요) |
| 실제 활용 | 주로 학습용, 데이터가 매우 작을 때 |
💻 전체 코드 예제
#include <stdio.h>
void swap(int* a, int* b){
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int arr[], int n){
int i, j, min;
for(i = 0; i < n - 1; i++){
min = i;
for(j = i + 1; j < n; j++){
if(arr[j] < arr[min])
min = j;
}
swap(&arr[min], &arr[i]);
}
}
int main()
{
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("정렬 결과: ");
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
💡 관련 개념 비교 (요약)
| 정렬 알고리즘 | 시간 복잡도 | 안정성 | 특징 |
|---|
| 선택 정렬 | O(n²) | ❌ | 선택 후 교환, 교환 적음 |
| 버블 정렬 | O(n²) | ✅ | 인접 비교, 교환 많음 |
| 삽입 정렬 | O(n²)/O(n) | ✅ | 거의 정렬된 경우 매우 빠름 |
