All
힙 정렬(Heap sort)
힙 정렬 개념
•
힙(Heap) 자료구조를 이용한 정렬 알고리즘
•
완전 이진트리 형태로, 특히 최대 힙은 모든 부모 노드가 자식 노드들보다 크거나 같은 값을 갖도록 구성된 트리
•
힙은 임의의 값 삽입 및 최댓값 삭제가 용이함
•
일차원 배열로 구현하여 효율적인 접근 가능
초기 힙 생성
방법 1 삽입을 반복하여 힙 구축하기 (상향식)
•
주어진 배열의 원소를 차례로 하나씩 빈 힙에 삽입하면서 최대 힙을 구성하는 방식
•
춴소를 추가할 때마다 최대 힙 조건을 유지하도록 삽입위치 찾아 힙을 재구성하는 과정이 필요
•
각 원소를 삽입하면서 위쪽(루트방향) 으로 이동하며 힙 성질을 만족시키도록 조정하는 방식
1. 빈 힙에 30 삽입
→ [30]
2. 45 삽입 (부모와 비교, 더 크므로 교환)
→ [45, 30]
3. 20 삽입 (부모보다 작으므로 그대로 유지)
→ [45, 30, 20]
4. 15 삽입 (부모(30)보다 작으므로 유지)
→ [45, 30, 20, 15]
5. 40 삽입 (부모(30)보다 크므로 교환)
→ [45, 40, 20, 15, 30]
6. 25 삽입 (부모(20)보다 크므로 교환)
→ [45, 40, 25, 15, 30, 20]
7. 35 삽입 (부모(25)보다 크므로 교환 후, 그 위의 부모(45)는 더 크므로 중단)
→ [45, 40, 35, 15, 30, 20, 25]
8. 10 삽입 (부모(15)보다 작으므로 유지)
→ [45, 40, 35, 15, 30, 20, 25, 10]
Plain Text
복사
방법 2 주어진 배열을 완전 이진트리로 만든 뒤 힙으로 변환하기(하향식)
•
입력 배열을 완전 이진트리라고 생각한뒤, 힙의 조건을 리프노드에서부터 루트노드로 조정해 나가며 구축하는 방법
•
배열의 중간부터 루트까지 올라오면서 각 노드에 대해 아래로 내려가며 최대 힙을 만드는 방식
30(0)
/ \\
45(1) 20(2)
/ \\ / \\
15(3) 40(4) 25(5) 35(6)
/
10(7)
- 노드 인덱스 (7, 6, 5, 4)는 자식이 없으므로 이미 최대 힙.
- 인덱스 3(값:15) 검사:
자식(10)과 비교 → 15가 더 큼 (그대로 유지)
- 인덱스 2(값:20) 검사:
자식 중 큰 값(35)과 비교 → 35가 더 크므로 교환
→ [30, 45, 35, 15, 40, 25, 20, 10]
- 인덱스 1(값:45) 검사:
자식 중 큰 값(40)과 비교 → 45가 더 크므로 유지
- 인덱스 0(값:30) 검사:
자식 중 큰 값(45)과 비교 → 45가 더 크므로 교환
→ [45, 30, 35, 15, 40, 25, 20, 10]
바뀐 30은 다시 자식(40, 15)과 비교, 40이 더 크므로 교환
→ [45, 40, 35, 15, 30, 25, 20, 10]
최종 구축된 최대 힙:
[45, 40, 35, 15, 30, 25, 20, 10]
Plain Text
복사
•
방법 2는 방법 1보다 더 효율적인 O(n)에 가까운 시간복잡도를 보이며 일반적으로 방법 2를 실제 힙 정렬 구현에서 선호
•
리프에 가까운 노드일수록 작업량이 거의 없고, 루트 노드는 1개, 즉 작업량이 많은 노드는 매우 적기 때문에 전체적으로 보면 총 작업량이 선형에 수렴
총 작업량 ≈ Σ (노드 수 × 깊이)
= n/2 * 0 + n/4 * 1 + n/8 * 2 + ... + 1 * log n
= O(n)
Plain Text
복사
성능과 특징
•
시간 복잡도: O(n log n) (최선-최악-평균)
◦
바깥 루프 > 입력크기 n에 비례
◦
안쪽루프 > 완전 이진 트리의 높이 logn에 비례
•
불안정 정렬
•
제자리 정렬 (추가 저장 공간 거의 필요 없음)
def heapify(arr, n, i):
largest = i
left = 2 * i + 1 # 왼쪽 자식
right = 2 * i + 2 # 오른쪽 자식
# 자식들과 비교해서 최대값 찾기
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
# 루트가 최대값이 아니면 교환 후 재귀 호출
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 초기 최대 힙 만들기 (하향식 방법)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 하나씩 꺼내서 정렬
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 최댓값을 뒤로
heapify(arr, i, 0)
return arr
# 예시
arr = [30, 45, 20, 15, 40, 25, 35, 10]
print("힙 정렬:", heap_sort(arr))
Python
복사
비교 기반 정렬 알고리즘의 성능의 하한 > O(nlogn)
데이터 분포 정보를 활용하는 정렬 알고리즘
계수 정렬(Counting Sort)
계수 정렬 개념
•
계수 정렬은 데이터의 분포 정보를 활용한 정렬로, 입력값의 범위가 제한적일 때 매우 빠르게 동작하는 정렬 알고리즘
동작 원리
•
각 원소보다 작거나 같은 원소의 개수를 카운트
•
누적 개수를 통해 각 원소의 정확한 위치를 찾아 정렬
동작 과정:
1.
입력값의 범위만큼 배열을 만들어 각 값의 빈도수를 기록
2.
빈도수 누적 합을 계산하여 각 원소의 위치를 결정
3.
입력 배열을 뒤에서부터 확인하여 바로 정렬된 위치에 삽입
성능과 특징
•
시간 복잡도: O(n) (입력값 범위가 데이터 크기와 비례할 때)
•
안정적 정렬 (같은 값을 가진 데이터 순서 유지)
•
제자리 정렬 아님 (입력 배열 크기의 추가 배열 필요)
•
입력값의 범위가 크면 배열이 엄청나게 커져 메모리 많이 사용하고 효율 떨어짐 → 범위가 제한적일 때 유리
def counting_sort(arr):
if len(arr) == 0:
return arr
max_val = max(arr)
count = [0] * (max_val + 1)
# 빈도 세기
for num in arr:
count[num] += 1
# 누적합으로 정렬된 위치 계산
for i in range(1, len(count)):
count[i] += count[i - 1]
output = [0] * len(arr)
for num in reversed(arr): # 안정성을 위해 뒤에서부터 처리
count[num] -= 1
output[count[num]] = num
return output
# 예시
arr = [4, 2, 2, 8, 3, 3, 1]
print("계수 정렬:", counting_sort(arr))
Python
복사
기수 정렬(Radix Sort)
기수 정렬 개념
기수 정렬은 입력값을 자릿수별로 나누어 정렬하는 알고리즘
내부적으로는 각 자릿수에 대해 계수 정렬과 같은 안정적 정렬을 적용
동작 원리
•
최하위 자릿수부터 최상위 자릿수까지 순차적으로 정렬
•
각 단계에서는 계수 정렬을 수행하여, 최종적으로 전체 데이터를 정렬
[170, 45, 75, 90, 802, 24, 2, 66]
1단계(1의 자리): [170, 90, 802, 2, 24, 45, 75, 66]
2단계(10의 자리): [802, 2, 24, 45, 66, 170, 75, 90]
3단계(100의 자리): [2, 24, 45, 66, 75, 90, 170, 802] (정렬 완료)
Plain Text
복사
성능과 특징
•
시간 복잡도: O(n) (데이터의 자릿수가 상수일 때)
•
안정적 정렬
•
제자리 정렬 아님 (추가 배열 사용)
•
데이터 자릿수가 많을 경우 성능 저하 가능성 있음
def counting_sort_by_digit(arr, digit):
count = [0] * 10
output = [0] * len(arr)
# 해당 자릿수로 빈도 세기
for num in arr:
index = (num // digit) % 10
count[index] += 1
# 누적합 계산
for i in range(1, 10):
count[i] += count[i - 1]
# 출력 배열 채우기 (뒤에서부터 → 안정성 유지)
for num in reversed(arr):
index = (num // digit) % 10
count[index] -= 1
output[count[index]] = num
return output
def radix_sort(arr):
if len(arr) == 0:
return arr
max_val = max(arr)
digit = 1
while max_val // digit > 0:
arr = counting_sort_by_digit(arr, digit)
digit *= 10
return arr
# 예시
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("기수 정렬:", radix_sort(arr))
Python
복사
버킷 정렬(Bucket Sort)
버킷 정렬 개념
•
버킷 정렬은 데이터를 여러 개의 버킷(구간)으로 나누어 각 버킷 내에서 정렬 후 합치는 방식
일반적으로 데이터가 균등한 분포를 보일 때 효과적인 알고리즘
동작 원리
1.
데이터 값 범위를 균등하게 나누어 버킷을 여러 개 생성
2.
데이터를 해당하는 버킷에 할당
3.
각 버킷 내에서 삽입 정렬 등의 안정적인 정렬 알고리즘을 수행
4.
각 버킷 순서대로 데이터를 합쳐 최종 정렬 배열 완성
성능과 특징
•
시간 복잡도: O(n) (입력 데이터가 균등 분포, 버킷 개수가 데이터 개수에 비례할 때)
•
안정적 정렬
•
제자리 정렬 아님 (추가적인 버킷 저장 공간 필요)
•
데이터 분포가 편향적이면 성능 저하 가능성 있음
def bucket_sort(arr):
if len(arr) == 0:
return arr
# 1. 버킷 개수 정하기 (입력 크기만큼)
num_buckets = len(arr)
# 2. 각 버킷 초기화 (빈 리스트로 시작)
buckets = [[] for _ in range(num_buckets)]
# 3. 최대/최소값으로 범위 계산 (0~1 범위가 아닐 수도 있으니까!)
min_value = min(arr)
max_value = max(arr)
range_size = (max_value - min_value + 1) / num_buckets
# 4. 각 값을 적절한 버킷에 넣기
for value in arr:
# 인덱스 계산
index = int((value - min_value) / range_size)
if index == num_buckets: # max_value edge case
index -= 1
buckets[index].append(value)
# 5. 각 버킷 정렬
for i in range(num_buckets):
buckets[i] = sorted(buckets[i]) # 삽입 정렬 등으로 대체 가능
# 6. 버킷 순서대로 이어붙이기
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(bucket)
return sorted_arr
# 예시 사용
arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
sorted_arr = bucket_sort(arr)
print("정렬된 배열:", sorted_arr)
Python
복사