삽입 정렬 (Insertion Sort) 완벽 가이드

카드를 정렬할 때 사람이 흔히 사용하는 방식과 가장 유사한 알고리즘, **삽입 정렬(Insertion Sort)**에 대해 알아보겠습니다.

1. 삽입 정렬이란?

삽입 정렬은 두 번째 원소부터 시작하여, 그 앞의 (이미 정렬된) 원소들과 비교하여 **자신의 들어갈 알맞은 위치를 찾아 ‘삽입’**하는 알고리즘입니다.

앞부분이 항상 정렬된 상태를 유지하며 배열의 끝까지 범위를 넓혀가는 방식입니다.

2. 동작 과정 (오름차순 기준)

두 번째 원소를 타겟(Target)으로 선택합니다. (첫 번째 원소는 이미 정렬되어 있다고 가정)
타겟 원소를 그 앞의 원소들과 뒤에서부터 차례대로 비교합니다.
타겟 원소보다 앞의 원소가 더 크다면, 앞의 원소를 뒤로 한 칸 밉니다.
타겟 원소가 들어갈 올바른 위치를 찾으면 (즉, 자신보다 작은 원소를 만나면) 그 자리에 삽입합니다.
다음 원소를 새로운 타겟으로 선택하고 위 과정을 끝까지 반복합니다.

3. 파이썬(Python) 구현 예시

def insertion_sort(arr):
    # 인덱스 1부터 시작 (두 번째 원소부터 타겟)
    for i in range(1, len(arr)):
        target = arr[i] # 현재 삽입할 원소
        j = i - 1
        
        # 타겟 원소가 들어갈 위치를 찾을 때까지 앞의 원소들을 뒤로 이동
        # j가 0 이상이고, 앞의 원소가 타겟보다 크면 반복
        while j >= 0 and arr[j] > target:
            arr[j + 1] = arr[j] # 앞의 원소를 한 칸 뒤로 밈
            j -= 1
            
        # 적절한 위치에 타겟 원소 삽입
        arr[j + 1] = target
        
    return arr
 
# 사용 예시
data = [12, 11, 13, 5, 6]
print("정렬 전:", data)
print("정렬 후:", insertion_sort(data))

4. 시간 복잡도 및 공간 복잡도

시간 복잡도:
- 최악의 경우 (역순 정렬): $O (N^{2})$ (매번 맨 앞까지 다 비교하고 밀어내야 함)
- 최선의 경우 (이미 정렬됨): $O (N)$ (앞의 원소가 더 작으면 바로 while문을 빠져나오기 때문)
- 평균의 경우: $O (N^{2})$
공간 복잡도: $O (1)$ (제자리 정렬(In-place Sort))

5. 특징

장점:
- 배열이 거의 정렬되어 있는 상태(Partially Sorted)라면 매우 빠릅니다 ( $O (N)$ 에 가까움).
- 구현이 간단하고, 안정 정렬(Stable Sort)입니다.
단점: 배열의 길이가 길어지고 역순에 가까울수록 비교 및 이동 연산이 많아져 성능이 저하됩니다 ( $O (N^{2})$ ).

요약

삽입 정렬은 타겟 값을 정렬된 앞부분의 적절한 위치에 삽입하며 정렬을 완성해 나가는 알고리즘입니다. 일반적인 상황에서는 $O (N^{2})$ 이지만, ‘거의 정렬된 배열’에서는 $O (N)$ 으로 매우 빠르다는 강력한 특징을 가집니다. 이 때문에 실무에서 다른 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)과 섞어서 사용할 때, 크기가 작은 부분 배열을 정렬하는 용도로 자주 활용됩니다 (예: 파이썬의 Timsort).

anonymous.rs

Explorer

정렬 알고리즘: 삽입 정렬 (Insertion Sort)