[정글 베이직 9]삽입 정렬 (Insertion Sort) 구현

 

[정글 베이직 9]
삽입 정렬 (Insertion Sort) 구현

카드 게임처럼 — 손에 든 패를 적절한 위치에 끼워 넣는 정렬 알고리즘

▶ BEFORE (입력)

12 11 13 5 6

정렬되지 않은 배열

✓ AFTER (출력)

5 6 11 12 13

오름차순 정렬 완료

01 문제 설명

삽입 정렬(Insertion Sort)은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 부분에서 원소를 하나씩 꺼내 정렬된 부분의 적절한 위치에 삽입하는 알고리즘입니다.

🃏 비유하자면 카드 게임에서 손에 든 카드를 정렬할 때, 새 카드를 뽑으면 이미 정렬된 카드들 사이에서 알맞은 자리를 찾아 끼워 넣는 방식과 동일합니다.

📌 핵심 입출력
입력: 정렬되지 않은 정수 배열 arr
출력: 오름차순으로 정렬된 배열

예제 1: [12, 11, 13, 5, 6] → [5, 6, 11, 12, 13]
예제 2: [64, 34, 25, 12, 22, 11, 90] → [11, 12, 22, 25, 34, 64, 90]

02 핵심 개념 — 삽입 정렬의 원리

삽입 정렬의 핵심은 "key" 값을 잡고, 정렬된 부분을 오른쪽으로 밀어내면서 key가 들어갈 자리를 만드는 과정입니다.

💡 핵심 원리: 인덱스 i의 원소를 key로 잡고, 인덱스 0 ~ i-1 (정렬된 부분)에서 key보다 큰 원소들을 오른쪽으로 한 칸씩 밀다가, 더 이상 크지 않은 위치 j+1에 key를 삽입합니다.

while 루프 조건 분석:

조건	의미
j >= 0	배열의 왼쪽 경계를 벗어나지 않도록 보호
arr[j] > key	현재 원소가 key보다 크면 계속 오른쪽으로 이동
루프 종료 시	arr[j] <= key → j+1이 key의 올바른 위치

03 단계별 시각화 — [12, 11, 13, 5, 6]

🔍 패스별 삽입 과정

초기

12

11

13

5

6

index 0은 이미 정렬된 상태로 시작

i=1

12

11

13

5

6

→

11

12

13

5

6

key=11 < 12 → 12를 오른쪽으로 이동 후 0번 자리에 삽입

i=2

11

12

13

5

6

→

11

12

13

5

6

key=13 ≥ 12 → 이동 없이 제자리 유지

i=3

11

12

13

5

6

→

5

11

12

13

6

key=5 < 11, 12, 13 모두 → 세 원소 전부 오른쪽으로, 맨 앞에 삽입

i=4

5

11

12

13

6

→

5

6

11

12

13

key=6: 5 ≤ 6이므로 5 다음 자리(index 1)에 삽입 → 완료!

✅ 색상 범례: 황색 = key (삽입할 원소) 적색 = 이동 중인 원소 녹색 = 정렬 완료 청색 = 최종 정렬

04 기본 구현 — O(n²)

 

 

 

Python 3

def insertion_sort(arr): """삽입 정렬 기본 구현 - O(n²)""" arr = arr.copy() # 원본 배열 보호 n = len(arr) for i in range(1, n): key = arr[i] # 현재 삽입할 원소 j = i - 1 # 정렬된 부분의 마지막 인덱스 # key보다 큰 원소들을 오른쪽으로 한 칸씩 이동 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # 적절한 위치에 삽입 return arr # 테스트 arr = [12, 11, 13, 5, 6] result = insertion_sort(arr) print(result) # [5, 6, 11, 12, 13]

⚠️ while 루프 핵심 분석
while j >= 0 and arr[j] > key:

• j >= 0: 배열 왼쪽 경계 초과 방지 (인덱스 -1 방지)
• arr[j] > key: 정렬된 부분의 원소가 key보다 크면 계속 이동
• 루프가 끝나면 arr[j] <= key 이거나 j == -1 (key가 가장 작은 경우)

05 단계별 과정 출력 버전

 

 

 

Python 3

def insertion_sort_with_steps(arr): """삽입 정렬 - 단계별 과정 반환""" arr = arr.copy() n = len(arr) steps = [] 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 steps.append((i, key, arr.copy())) return arr, steps # 실행 결과 result, steps = insertion_sort_with_steps([12, 11, 13, 5, 6]) for step_i, key, state in steps: print(f"i={step_i}, key={key} 삽입 → {state}") # i=1, key=11 삽입 → [11, 12, 13, 5, 6] # i=2, key=13 삽입 → [11, 12, 13, 5, 6] # i=3, key=5 삽입 → [5, 11, 12, 13, 6] # i=4, key=6 삽입 → [5, 6, 11, 12, 13]

06 시간 복잡도 분석

케이스	시간 복잡도	설명	예시
최선 (Best)	O(n)	이미 정렬된 배열 — while 루프 한 번도 실행 안 됨	[1, 2, 3, 4, 5]
평균 (Average)	O(n²)	랜덤 배열 — 평균적으로 절반씩 이동	[3, 1, 4, 1, 5]
최악 (Worst)	O(n²)	역순 배열 — 매번 전체 이동 필요	[5, 4, 3, 2, 1]
공간 복잡도	O(1)	제자리 정렬 — 추가 배열 불필요	key 변수 하나만 사용

💡 삽입 정렬 최선 케이스가 O(n)인 이유
이미 정렬된 배열이라면 각 i마다 while 루프 조건 arr[j] > key가 즉시 False가 되어 루프 본체가 실행되지 않습니다. 따라서 외부 for 루프만 n-1번 실행되어 O(n)이 됩니다. 이 점에서 버블 정렬의 최적화 버전(swapped 플래그)과 유사한 특성을 가집니다.

07 버블 정렬 vs 삽입 정렬 비교

⚡ 버블 정렬 (베이직 8)

for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = \ arr[j+1], arr[j] # 인접 원소 비교·교환 반복

✨ 삽입 정렬 (베이직 9)

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 # key를 적절한 위치에 삽입

항목	버블 정렬	삽입 정렬
방식	인접 원소 비교 후 교환 (swap)	key를 정렬된 부분에 삽입 (shift)
최선 복잡도	O(n) (swapped 플래그 사용 시)	O(n) (자연스럽게)
평균/최악	O(n²)	O(n²)
실제 성능	상대적으로 느림 (교환 횟수 많음)	상대적으로 빠름 (이동만, 교환 없음)
안정 정렬	✅ 예	✅ 예
적합한 상황	거의 정렬된 데이터	거의 정렬된 데이터 (더 효율적)

08 테스트 결과

 

 

 

실행 결과

입력: [12, 11, 13, 5, 6] 출력: [5, 6, 11, 12, 13] ✓ 입력: [64, 34, 25, 12, 22, 11, 90] 출력: [11, 12, 22, 25, 34, 64, 90] ✓ 입력: [1] 출력: [1] ✓ (단일 원소) 입력: [] 출력: [] ✓ (빈 배열) 입력: [3, 3, 3] 출력: [3, 3, 3] ✓ (중복 원소) 입력: [5, 4, 3, 2, 1] # 최악 케이스 (역순) 출력: [1, 2, 3, 4, 5] ✓ 입력: [1, 2, 3, 4, 5] # 최선 케이스 (이미 정렬) 출력: [1, 2, 3, 4, 5] ✓

09 파이썬 문법 정리

arr.copy()

얕은 복사 — 원본 배열 보호

len(arr)

배열 길이 반환

range(1, n)

1부터 n-1까지 반복 (index 1부터 시작)

while j >= 0 and ...

단락 평가 — j가 0 미만이면 뒤 조건 미평가

arr[j + 1] = arr[j]

원소를 오른쪽으로 한 칸 이동 (shift)

j -= 1

왼쪽으로 한 칸 이동

arr[j + 1] = key

while 종료 후 최종 삽입 위치에 key 배치

steps.append((i, key, arr.copy()))

튜플로 단계 정보 저장

🚨 흔한 실수 주의!
arr[j + 1] = key는 while 루프 밖에 있어야 합니다. 루프 안에 넣으면 매 이동마다 key를 덮어써 버립니다.

또한 while j >= 0 조건을 빠뜨리면 j = -1일 때 arr[-1]을 참조해 Python의 음수 인덱싱 특성으로 엉뚱한 원소와 비교하게 됩니다.

10 언제 삽입 정렬을 선택할까?

상황	추천 정렬	이유
데이터가 거의 정렬됨	삽입 정렬	O(n)에 가까운 성능 발휘
소규모 데이터 (n < 50)	삽입 정렬	오버헤드 없이 빠름, 실제 상수 인자 작음
온라인 정렬 (데이터가 실시간 유입)	삽입 정렬	새 데이터를 바로 삽입 가능
대규모 랜덤 데이터	병합/퀵 정렬	O(n log n) 필요
Python 기본 정렬	timsort	Merge Sort + Insertion Sort 혼합

🐍 재미있는 사실: Python의 내장 sorted()와 list.sort()는 Timsort를 사용합니다. Timsort는 실제로 삽입 정렬과 병합 정렬을 조합한 알고리즘으로, 소규모 서브배열(run)에는 삽입 정렬을 적용해 효율을 높입니다.

---

#크래프톤정글 #베이직9 #삽입정렬 #InsertionSort #알고리즘 #정렬알고리즘 #Python #OnCampus