삽입 정렬 (Insertion Sort)

삽입 정렬

"각 요소를 적절한 위치에 삽입하며 정렬하는 방식"

• 현재 요소를 앞쪽 정렬된 부분과 비교하여 올바른 위치에 삽입
• 거의 정렬된 데이터에서 빠르게 동작(O(n))하지만, 일반적으로 비효율적(O(n²))

---

삽입 정렬 동작 원리

• 첫 번째 요소는 이미 정렬된 상태로 간주
• 두 번째 요소를 앞쪽 정렬된 부분과 비교하여 적절한 위치에 삽입
• 세 번째 요소도 앞쪽 정렬된 부분과 비교하여 삽입
• 이 과정을 마지막 요소까지 반복

# Pseudo Code
FUNCTION InsertionSort(arr)
    FOR i FROM 1 TO length(arr) - 1
        key = arr[i]
        j = i - 1
        WHILE j >= 0 AND arr[j] > key DO
            arr[j + 1] = arr[j]
            j = j - 1
        END WHILE
        arr[j + 1] = key
    END FOR
    RETURN arr
END FUNCTION


# Full Code
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):  # 두 번째 요소부터 시작
        key = arr[i]  # 현재 비교할 요소 저장
        j = i - 1
        while j >= 0 and arr[j] > key:  # 앞쪽 요소와 비교하며 이동
            arr[j + 1] = arr[j]  # 한 칸씩 이동
            j -= 1
        arr[j + 1] = key  # 올바른 위치에 삽입
    return arr
    

# 테스트
arr = [5, 3, 8, 4, 2]
print("삽입 정렬 결과:", insertion_sort(arr))

---

삽입 정렬의 시간복잡도

경우	시간복잡도
최선 (이미 정렬됨)	O(n)
평균	O(n²)
최악 (역순 정렬)	O(n²)

 

✅ 거의 정렬된 데이터에서는 O(n) → 매우 빠름!

❌ 랜덤 데이터에서는 O(n²) → 비효율적!

---

삽입 정렬의 장단점

장점

• 거의 정렬된 데이터에서는 O(n)으로 매우 빠름
• 추가 메모리 필요 없음(O(1))
• 실시간으로 데이터가 들어올 때 유용 (온라인 정렬)

단점

 

• 일반적인 정렬에서는 O(n²)로 비효율적
• 큰 데이터셋에서는 퀵 정렬(O(n log n))이 훨씬 빠름

결론

삽입 정렬은 거의 정렬된 데이터에서 빠르고, 실시간 정렬에 유용하지만, 일반적인 정렬에는 퀵 정렬(O(n log n))이나 병합 정렬(O(n log n))이 더 적합합니다.