-
힙 정렬(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]방법 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]- 방법 2는 방법 1보다 더 효율적인 O(n)에 가까운 시간복잡도를 보이며 일반적으로 방법 2를 실제 힙 정렬 구현에서 선호
- 리프에 가까운 노드일수록 작업량이 거의 없고, 루트 노드는 1개, 즉 작업량이 많은 노드는 매우 적기 때문에 전체적으로 보면 총 작업량이 선형에 수렴
총 작업량 ≈ Σ (노드 수 × 깊이) = n/2 * 0 + n/4 * 1 + n/8 * 2 + ... + 1 * log n = O(n)성능과 특징
- 시간 복잡도: 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))비교 기반 정렬 알고리즘의 성능의 하한 > O(nlogn)
데이터 분포 정보를 활용하는 정렬 알고리즘
계수 정렬(Counting Sort)
계수 정렬 개념
- 계수 정렬은 데이터의 분포 정보를 활용한 정렬로, 입력값의 범위가 제한적일 때 매우 빠르게 동작하는 정렬 알고리즘
동작 원리
- 각 원소보다 작거나 같은 원소의 개수를 카운트
- 누적 개수를 통해 각 원소의 정확한 위치를 찾아 정렬
동작 과정:
- 입력값의 범위만큼 배열을 만들어 각 값의 빈도수를 기록
- 빈도수 누적 합을 계산하여 각 원소의 위치를 결정
- 입력 배열을 뒤에서부터 확인하여 바로 정렬된 위치에 삽입
성능과 특징
- 시간 복잡도: 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))기수 정렬(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] (정렬 완료)성능과 특징
- 시간 복잡도: 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))버킷 정렬(Bucket Sort)
버킷 정렬 개념
- 버킷 정렬은 데이터를 여러 개의 버킷(구간)으로 나누어 각 버킷 내에서 정렬 후 합치는 방식
일반적으로 데이터가 균등한 분포를 보일 때 효과적인 알고리즘
동작 원리
- 데이터 값 범위를 균등하게 나누어 버킷을 여러 개 생성
- 데이터를 해당하는 버킷에 할당
- 각 버킷 내에서 삽입 정렬 등의 안정적인 정렬 알고리즘을 수행
- 각 버킷 순서대로 데이터를 합쳐 최종 정렬 배열 완성
성능과 특징
- 시간 복잡도: 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)'알고리즘' 카테고리의 다른 글
그래프(1) - DFS, BFS, 위상정렬, 연결성분, 강연결성분 (0) 2025.04.29 탐색&해싱 (0) 2025.04.24 정렬(2) - 퀵정렬, 합병정렬 (0) 2025.03.23 정렬(1) - 선택, 삽입, 버블, 셸 (0) 2025.03.16 알고리즘 소개 (0) 2025.03.02 댓글
일단 시작하는 블로그
내가 보려고 만드는 블로그
