[알고리즘 심층분석 #3] 삽입 정렬(Insertion Sort) 동작 원리, O(N) 유도, 코드 구현 완벽 정리

기본 정렬 알고리즘 3대장(버블, 선택, 삽입) 중 실제 활용도가 가장 높고 효율적인 삽입 정렬(Insertion Sort)입니다.

"손 안의 카드를 정렬할 때 우리는 어떤 방식을 사용할까?"

"왜 삽입 정렬은 이미 정렬된 데이터가 들어올 때 O(N)이라는 압도적인 속도를 보일까?"

삽입 정렬의 직관적인 개념부터 회전별 동작 과정, 파이썬 코드 구현, 최선의 경우 O(N) 유도 과정, 그리고 시험 단골 핵심 특징까지 심층 분석해 드립니다!

1. 삽입 정렬(Insertion Sort)이란?

삽입 정렬은 배열의 두 번째 원소부터 시작하여, 앞쪽의 이미 정렬된 영역 내에서 자신의 적절한 위치를 찾아 '삽입'하는 정렬 알고리즘입니다.

• 비유: 포커나 손안의 카드를 들고 있을 때, 새로운 카드를 한 장씩 뽑아 이미 순서대로 정리된 카드들 사이의 올바른 위치에 쏙 넣는 방식과 정확히 같습니다.
• 핵심 특징: 항상 앞쪽 영역은 정렬된 상태를 유지하며, 현재 비교할 대상 원소를 정렬된 영역의 오른쪽에서 왼쪽 방향으로 비교하며 들어갈 자리를 만듭니다.

현재 원소를 앞쪽의 정렬된 영역과 비교하며 적절한 위치에 삽입하는 과정. 출처: 그적 - 티스토리

2. 단계별 동작 예시 (Step-by-Step)

배열 [8, 5, 6, 2]를 오름차순으로 정렬하는 과정을 살펴보겠습니다. 첫 번째 원소 8은 그 자체로 이미 정렬된 영역으로 봅니다.

• 1회전: target = 5 (index 1)
  • 정렬된 영역 [8]과 비교
  • 8이 5보다 크므로 오른쪽으로 한 칸 밀어냄 ([8, 8, 6, 2])
  • 맨 앞에 5 삽입 -> [5, 8, 6, 2]
  • 👉 1회전 완료: 정렬 영역 [5, 8]
• 2회전: target = 6 (index 2)
  • 정렬된 영역 [5, 8]과 뒤에서부터 비교
  • 8이 6보다 크므로 오른쪽 밀어냄 ([5, 8, 8, 2])
  • 5는 6보다 작으므로 정지
  • 8이 있던 자리에 6 삽입 -> [5, 6, 8, 2]
  • 👉 2회전 완료: 정렬 영역 [5, 6, 8]
• 3회전: target = 2 (index 3)
  • 정렬된 영역 [5, 6, 8]과 비교
  • 8, 6, 5가 모두 2보다 크므로 전부 오른쪽으로 한 칸씩 밀어냄
  • 맨 앞에 2 삽입 -> [2, 5, 6, 8]
  • 👉 3회전 완료: 전체 정렬 완료!

3. 코드 구현 (Python)

Python

 

def insertion_sort(arr):
    n = len(arr)
    
    # 2번째 원소(index 1)부터 시작
    for i in range(1, n):
        target = arr[i]  # 현재 삽입할 대상 값
        j = i - 1        # 정렬된 영역의 맨 뒤 인덱스
        
        # target보다 큰 원소들은 오른쪽으로 한 칸씩 이동(Shift)
        while j >= 0 and arr[j] > target:
            arr[j + 1] = arr[j]
            j -= 1
            
        # 알맞은 위치에 target 삽입
        arr[j + 1] = target

4. 복잡도 및 특성 분석 (★시험 유도 포인트)

🔹 최선의 경우 시간 복잡도 유도: O(N)

배열이 이미 완벽히 정렬된 상태([1, 2, 3, 4, 5])로 입력되는 경우를 생각해 보겠습니다.

1. target 원소를 잡고 바로 앞 원소와 딱 1번 비교합니다.
2. 앞 원소가 target보다 작으므로 while 루프 조건이 즉각 거짓(False)이 되어 탈출합니다.
3. 원소 이동(Shift) 없이 다음 회전으로 넘어갑니다.
4. 따라서 N개의 데이터에 대해 각각 1번씩만 비교하므로 총 비교 횟수는 (N-1)번이 됩니다.
5. 👉 최선의 시간 복잡도: O(N)

🔹 평균 및 최악의 시간 복잡도: O(N^2)

• 최악의 경우 (역순 정렬): 회전마다 정렬된 영역의 모든 원소와 비교하며 끝까지 밀어내야 합니다.
  • 총 비교 횟수: 1 + 2 + 3 + ... + (N-1) = N(N-1) / 2
  • 👉 최악의 시간 복잡도: O(N^2)
• 평균의 경우: 평균적으로 정렬 영역의 절반 정도를 탐색하므로 O(N^2)입니다.

🔹 공간 복잡도

• 기존 배열 내부에서 위치 이동이 이루어지므로 제자리 정렬(In-Place Sort)입니다. -> O(1)

🔹 안정성 (Stability)

• 중복된 값이 들어왔을 때, arr[j] > target 조건처럼 자신보다 '엄격히 큰' 값만 밀어내므로 동등한 값의 상대적 위치가 바뀌지 않는 안정 정렬(Stable Sort)입니다.

5. 한눈에 끝내는 핵심 요약표 (★시험 필수)

구분	주요 내용 및 특징
기본 매커니즘	두 번째 원소부터 앞쪽 정렬 영역 내 알맞은 위치를 찾아 삽입
시간 복잡도	최악 O(N^2), 평균 O(N^2), 최선 O(N)
공간 복잡도	O(1) (제자리 정렬 - In-Place)
안정성 여부	안정 정렬 (Stable Sort)
장점	이미 정렬되어 있거나 거의 정렬된 데이터에 대해 매우 뛰어난 성능(O(N)) 발휘
단점	데이터 양이 많고 정렬되어 있지 않을수록 원소 이동(Shift) 횟수가 많아져 비효율적