이 글에서는 배열을 힙 정렬(Heap Sort) 알고리즘으로 정렬하는 파이썬 프로그램을 다룹니다. 힙 정렬의 기본 개념부터 실제 구현 코드와 실행 결과까지 단계별로 살펴보겠습니다.
문제 정의
문제: 주어진 배열을 힙 정렬(Heap Sort)의 개념을 이용해 오름차순으로 정렬합니다.
힙 정렬의 핵심 아이디어는 다음과 같습니다. 먼저 배열을 최대 힙(Max Heap) 구조로 만든 뒤, 루트에 위치한 최댓값을 배열의 마지막 요소와 교환(swap)합니다. 이 과정을 정렬이 완료될 때까지 반복하면, 최댓값부터 차례대로 배열 뒤쪽에 배치되어 최종적으로 오름차순 정렬이 완성됩니다.
힙 정렬의 동작 원리
힙 정렬은 크게 두 단계로 진행됩니다.
1단계 – 힙 구성(heapify): 입력 배열을 최대 힙 형태로 변환합니다. 각 노드가 자식 노드보다 크거나 같도록 재배열하는 과정입니다.
2단계 – 요소 추출: 힙의 루트(최댓값)를 배열의 끝으로 보내고, 남은 부분에 대해 다시 heapify를 수행하여 힙 속성을 유지합니다. 이를 반복하면 배열 전체가 정렬됩니다.
구현 예제
# heapify 함수
def heapify(arr, n, i):
largest = i # 가장 큰 값의 인덱스
l = 2 * i + 1 # 왼쪽 자식
r = 2 * i + 2 # 오른쪽 자식
# 왼쪽 자식이 존재하고 루트보다 큰 경우
if l < n and arr[i] < arr[l]:
largest = l
# 오른쪽 자식이 존재하고 현재 최댓값보다 큰 경우
if r < n and arr[largest] < arr[r]:
largest = r
# 루트가 최댓값이 아니라면 교환 후 재귀 호출
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
heapify(arr, n, largest)
# 힙 정렬 함수
def heapSort(arr):
n = len(arr)
# 최대 힙 구성
for i in range(n, -1, -1):
heapify(arr, n, i)
# 요소 하나씩 추출하며 정렬
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# 메인
arr = [2, 5, 3, 8, 6, 5, 4, 7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=" ")실행 결과
Sorted array is 2 3 4 5 5 6 7 8
코드 설명
위 코드에서 사용된 모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 변수의 역할은 다음과 같습니다.
- i: 현재 처리 중인 노드의 인덱스
- l, r: 각각 왼쪽 자식과 오른쪽 자식의 인덱스 (배열 기반 힙에서는 i의 자식이 2i+1, 2i+2로 계산됨)
- n: 힙의 크기, 즉 정렬 대상이 되는 요소의 개수
heapify 함수는 특정 노드를 기준으로 서브트리가 힙 속성을 만족하도록 조정하고, heapSort 함수는 전체 배열에 대해 힙 구성과 요소 추출을 반복 수행합니다.
시간 복잡도
힙 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n log n)으로 안정적인 성능을 보이며, 추가 메모리 사용이 거의 없는 제자리(in-place) 정렬 알고리즘이라는 장점이 있습니다.
결론
이번 글에서는 파이썬으로 힙 정렬 프로그램을 작성하는 방법을 알아보았습니다. heapify를 통한 최대 힙 구성과 루트 요소 추출의 반복이라는 두 가지 핵심 단계만 이해하면, 어떤 배열이든 효율적으로 정렬할 수 있습니다.