이 글에서는 이진 삽입 정렬(Binary Insertion Sort)을 파이썬으로 구현하는 방법을 단계별로 알아보겠습니다.
문제 정의
문제 – 주어진 배열을 이진 삽입 정렬 개념을 활용해 오름차순으로 정렬해야 합니다.
이름에서 알 수 있듯이, 이진 삽입 정렬은 삽입 정렬(Insertion Sort) 알고리즘에 이진 탐색(Binary Search) 개념을 결합한 정렬 방식입니다. 일반적인 삽입 정렬은 새 요소가 들어갈 위치를 찾기 위해 정렬된 앞부분을 처음부터 한 칸씩 비교하지만, 이진 삽입 정렬은 이진 탐색으로 삽입 위치를 빠르게 찾아내기 때문에 비교 횟수를 크게 줄일 수 있습니다. 다만 요소를 밀어내는 이동 연산은 그대로 남아 있으므로, 최악의 경우 시간 복잡도는 여전히 O(n²)입니다.
동작 원리
- 배열의 두 번째 요소부터 마지막 요소까지 순서대로 순회합니다.
- 현재 요소를 임시 변수에 저장하고, 앞쪽의 정렬된 구간에서 이진 탐색을 수행해 삽입할 위치를 찾습니다.
- 해당 위치 뒤의 요소들을 한 칸씩 뒤로 밀어낸 뒤, 현재 요소를 그 위치에 삽입합니다.
- 모든 요소에 대해 위 과정을 반복하면 배열 전체가 정렬됩니다.
이제 아래 구현 예시를 통해 해결 과정을 살펴보겠습니다.
예제 코드
# 정렬 함수
def insertion_sort(arr):
for i in range(1, len(arr)):
temp = arr[i]
# 이진 탐색으로 삽입 위치를 찾음
pos = binary_search(arr, temp, 0, i) + 1
# 요소들을 한 칸씩 뒤로 이동
for k in range(i, pos, -1):
arr[k] = arr[k - 1]
arr[pos] = temp
def binary_search(arr, key, start, end):
# 탐색 구간이 충분히 좁혀진 경우
if end - start <= 1:
if key < arr[start]:
return start - 1
else:
return start
mid = (start + end) // 2
if arr[mid] < key:
return binary_search(arr, key, mid, end)
elif arr[mid] > key:
return binary_search(arr, key, start, mid)
else:
return mid
# 메인 부분
arr = [1, 5, 3, 4, 8, 6, 3, 4]
n = len(arr)
insertion_sort(arr)
print("Sorted array is:")
for i in range(n):
print(arr[i], end=" ")출력 결과
Sorted array is : 1 3 3 4 4 5 6 8
코드 설명
insertion_sort 함수는 배열의 두 번째 요소부터 차례대로 순회하며, 현재 값을 temp에 임시 저장합니다. 그다음 binary_search 함수를 호출해 정렬된 앞쪽 구간(인덱스 0부터 i까지)에서 temp가 들어갈 위치를 찾고, 그 위치까지 뒤쪽 요소들을 한 칸씩 뒤로 밀어낸 후 temp를 삽입합니다.
binary_search 함수는 재귀 방식으로 동작합니다. 탐색 구간의 중간값(mid)과 찾고자 하는 값(key)을 비교해 탐색 범위를 절반씩 좁혀 나가며, 구간이 충분히 좁혀지면 key가 삽입되어야 할 인덱스를 반환합니다. 모든 변수는 지역 범위(local scope) 내에서 선언되며, 함수 호출 과정에서 각 변수의 값 변화를 추적해 보면 알고리즘의 동작을 더욱 명확하게 이해할 수 있습니다.
결론
이 글에서는 삽입 정렬에 이진 탐색을 결합해 비교 연산 횟수를 줄이는 이진 삽입 정렬을 파이썬으로 구현하는 방법을 살펴보았습니다. 삽입 정렬의 단순한 구조에 이진 탐색을 더하는 것만으로도 비교 연산이 O(n log n) 수준으로 줄어들어 실질적인 성능 향상을 기대할 수 있습니다. 정렬 알고리즘의 기본기를 다지기에 좋은 예제이니, 직접 코드를 실행하고 다양한 입력값으로 테스트해 보시기 바랍니다.