1. 병합 정렬 (Merge Sort)
- 병합 정렬은 말 그대로 "나누고 합치는" 과정을 통해 전체를 정렬하는 방식
- 아무리 복잡한 문제라도 작게 나누면 해결하기 쉽다는 '분할 정복(Divide and Conquer)' 철학에 가장 충실한 알고리즘
1. 어떻게 동작하나요?
- 분할 (Divide):
- 배열의 원소가 1개가 될 때까지 계속해서 절반으로 나눔
- 원소가 하나만 남은 배열은 그 자체로 '정렬된' 상태라고 할 수 있음 - 병합 (Merge):
- 이제 나누어진 작은 배열들을 다시 합침
- 이때 그냥 합치는 게 아니라, 두 배열의 첫 번째 원소끼리 비교해서 더 작은 값을 먼저 가져오는 방식으로 정렬
- 이 과정을 반복하면 최종적으로 완벽하게 정렬된 배열이 완성
# 두 개의 정렬된 부분을 하나로 합치는 함수
def merge(arr, p, q, r):
# 왼쪽과 오른쪽 하위 배열의 크기를 계산
n1 = q - p + 1
n2 = r - q
# 임시 배열 생성 및 데이터 복사
L = [0] * n1
R = [0] * n2
for i in range(n1):
L[i] = arr[p + i]
for j in range(n2):
R[j] = arr[q + 1 + j]
# 임시 배열들의 인덱스와 원본 배열의 인덱스 초기화
i = 0 # 왼쪽 배열의 초기 인덱스
j = 0 # 오른쪽 배열의 초기 인덱스
k = p # 병합될 배열의 초기 인덱스
# 두 배열의 첫 번째 원소들을 비교하며 작은 값부터 정렬 (사용자 주석 내용)
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# 남아있는 요소들 복사
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# 병합 정렬 메인 함수
def merge_sort(arr, p, r):
# 의사 코드 1, 2번 줄: 재귀의 종료 조건 (원소가 하나 이하일 때)
# p < r은 원소가 2개 이상인 경우를 의미
if p < r:
# 의사 코드 3번 줄: 배열의 중간 지점(q) 계산
q = (p + r) // 2
# 의사 코드 4번 줄: 왼쪽 부분을 재귀적으로 정렬
merge_sort(arr, p, q)
# 의사 코드 5번 줄: 오른쪽 부분을 재귀적으로 정렬
merge_sort(arr, q + 1, r)
# 의사 코드 6, 7번 줄: 정렬된 두 부분을 병합
merge(arr, p, q, r)
# --- 실행 예시 ---
if __name__ == "__main__":
my_list = [38, 27, 43, 3, 9, 82, 10]
print("정렬 전:", my_list)
# merge_sort 함수 호출 (리스트 전체를 정렬하기 위해 0부터 길이-1까지 전달)
merge_sort(my_list, 0, len(my_list) - 1)
print("정렬 후:", my_list)
2. 성능과 장단점
- 시간 복잡도:
- 분할 과정은 트리의 깊이만큼() 발생하고, 각 깊이에서 병합 연산은 원소 개수()만큼 걸림
- 병합 정렬은 최선, 평균, 최악의 경우 모두 - 단점: 병합 정렬의 유일한 단점은 정렬 과정에서 임시 배열을 담아둘 추가적인 메모리 공간이 필요함
- 식 확장하기:
... 이 과정을 k번 확장하면 다음과 같은 일반식을 얻을 수 있음. - 재귀 종료 시점 찾기:
- 재귀 호출은 문제의 크기 n/2^k가 1(또는 2)이 될 때 멈춤
이 되는 k값을 찾으면, 이므로 이 됨 - 최종 계산:
- 위에서 구한 을 일반식에 대입
빅오(Big O) 표기법에서는 가장 영향력이 큰 항만 고려하므로, 최종 시간 복잡도는 이 됨
이고, $T(1)$은 상수 시간이므로, 식을 정리하면 다음과 같습니다.
2. 힙 정렬(Heap Sort)
- 완전 이진 트리를 기반
- 항상 부모 노드가 자식 노드보다 큰 값을 가지는(최대 힙 기준) 특징
힙(Heap)이란?
- 두 가지 중요한 규칙을 따르는 자료구조
- 구조 규칙: 완전 이진 트리 형태를 가짐
- 값 규칙 (최대 힙 기준): 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같음
장점: 배열만으로도 쉽게 구현할 수 있다는 점(링크드 리스트 사용 x)
1. 어떻게 동작하나요?
- '힙 만들기'**와 '정렬하기' 두 단계로 나뉨
- 힙 만들기 (Build Heap):
- 먼저, 정렬되지 않은 배열 전체를 최대 힙 구조로 만듬
- 배열의 중간 노드부터 루트까지 Heapify(힙 속성을 만족시키는 작업)를 순차적으로 수행하여 $O(n)$의 시간 복잡도로 효율적으로 처리할 수 있음 - 정렬하기 (Sorting Phase):
힙이 만들어지면 정렬은 매우 간단함.- 힙의 루트(배열의 첫 번째 원소)는 항상 최댓값. 이 값을 배열의 가장 마지막 원소와 교환
- 이제 가장 큰 값이 제자리를 찾았으니, 힙의 크기를 1 줄임
- 루트로 올라온 새로운 값 때문에 깨진 힙 구조를 정렬하는데 시간이 걸림
- MAX-HEAPIFY를 통해 복원
- 이 작업은 트리의 높이에 비례하는 힙에 원소가 하나 남을 때까지 이 과정을 반복하면, 배열이 완벽하게 정렬
2. 성능과 장단점
- n-1개의 원소를 추출하고 재정렬하는 데 $O(n \log n)$이 걸림
- 힙 정렬의 총 시간 복잡도는
- 시간 복잡도: 힙을 만드는 데 $O(n)$이 걸리고, 힙에서 원소를 추출해서 정렬하는데 $O(logn)$이 걸림
- n * logn
3. 퀵 정렬 (Quick Sort):
- 퀵 정렬은 이름 그대로 평균적으로 매우 빠른 성능을 자랑하는 정렬 알고리즘
- 병합 정렬과 달리 추가적인 메모리 공간을 거의 사용하지 않는다는 큰 장점
1. 어떻게 동작하나요?
- 분할 (Partition):
- 먼저 배열 내에서 **임의의 기준점(pivot)**을 하나 정함
- 그리고 피벗보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 모두 옮겨 피벗의 위치를 확정
- 이 과정을 '파티션'이라고 부름 - 정복 (Conquer):
- 피벗을 기준으로 나뉜 왼쪽과 오른쪽 두 개의 하위 배열에 대해 다시 퀵 정렬을 재귀적으로 수행
2. 성능과 장단점
- 평균 시간 복잡도:
- 파티션이 균형 있게 잘 나누어질 경우 의 매우 빠른 성능 - 최악 시간 복잡도:
- 만약 피벗으로 계속해서 가장 작거나 큰 값이 선택될 경우
이라는 비효율적인 성능을 보이게 됨
- 이미 정렬된 배열에서 항상 맨 오른쪽 원소를 피벗으로 삼는 경우, 파티션은 n-1개와 0개로 나뉘게 됨. - 해결책:
- 최악의 경우를 피하기 위해 피벗을 무작위로 선택하거나(Randomized Quicksort)
- 배열의 처음/중간/끝 세 값 중 중간값을 피벗으로 사용하는 등의 개선 방법
'ALGORITHM' 카테고리의 다른 글
| [알고리즘] 이진 탐색 트리(Binary Search Tree) (0) | 2025.09.25 |
|---|---|
| [알고리즘] 재귀란? (일반 재귀 vs 꼬리 재귀) (0) | 2025.09.22 |
| [알고리즘] k번째 원소 찾기 (Selection Algorithm) (0) | 2025.09.18 |
| [알고리즘] 정렬 알고리즘이란?(Counting Sort, Radix Sort, Bucket Sort) - Linear Time Sort (0) | 2025.09.15 |
| [알고리즘] 정렬 알고리즘이란?(Insertion Sort, Bubble Sort) (0) | 2025.09.07 |