2025-07-30 22:11
Status:
Tags: 알고리즘
삽입 정렬
- 배열을 한번에 한 요소씩 정렬된 위치에 삽입
- 평균, 최악은 O(n^2) 최선은 O(n)
- 거의 정렬된 데이터나 소규모 데이터에 유용 마치 카드를 정렬하는 것 처럼 가다가 알맞은 위치에 해당 값 넣는 식
def insertion_sort(arr):
"""
삽입 정렬 함수
입력: 정수 또는 비교 가능한 요소의 리스트 arr
출력: 오름차순으로 정렬된 리스트
"""
# 리스트를 직접 수정(in-place)
for i in range(1, len(arr)):
key = arr[i] # 삽입할 요소
j = i - 1
# 정렬된 부분(0…i-1)에서 key보다 큰 요소를 한 칸씩 오른쪽으로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# 빈 자리에 key 삽입
arr[j + 1] = key