Divide and Conquer
merge sort는 병합 정렬로 배열의 개수가 1~n까지 n개라고 했을때 재귀호출을 통해 정렬할 요소가 하나만 있을때까지 절반으로 나누고 그후 merge함수를 통해 정렬하는 방식이다.
단계는 분할, 정복, 병합 3가지로 나눌 수 있다.
Divide: 배열을 절반씩 나눈다.
Conquer: 양쪽 하위 배열을 각각 정렬한다(재귀).
Merge(Combine): 두 정렬된 배열을 선형 시간에 합친다
의사코드
MERGE_SORT(A, p, r)
1 if p < r
2 then q <- [(p+r)/2]
3 MERGE_SORT(A, p, q)
4 MERGE_SORT(A, q+1, r)
5 MERGE(A, p, q, r)
간단한 설명
A = 배열 , p = 정렬하고자하는 배열의 왼쪽 index, q = 중간 index
if p < r
p가 r와 같으면 정렬할 필요가 없고 p는 정렬할 배열의 제일 왼쪽 요소의 인덱스이기때문에 p는 r보다 클수 없음
q ← (p+r)/2
배열을 가운데에서 쪼개기 위해 중간 인덱스 q를 계산
왼쪽: A[p..q], 오른쪽: A[q+1..r]
MERGE_SORT(A, p, q)
왼쪽 절반을 재귀적으로 정렬
MERGE_SORT(A, q+1, r)
오른쪽 절반을 재귀적으로 정렬
MERGE(A, p, q, r)
정렬된 두 부분 배열을 합쳐서 하나의 정렬된 배열을 만든다
C언어 (동적배열할당과 배열 첫번째 시작을 1로 둠)
#include <stdio.h>
#include <stdlib.h>
void merge(int A[], int p, int q, int r, int temp[]) {
int i = p, j = q + 1, k = p;
while (i <= q && j <= r) {
if (A[i] <= A[j]) temp[k++] = A[i++];
else temp[k++] = A[j++];
}
while (i <= q) temp[k++] = A[i++];
while (j <= r) temp[k++] = A[j++];
for (int t = p; t <= r; t++) A[t] = temp[t];
}
void merge_sort_rec(int A[], int p, int r, int temp[]) {
if (p < r) {
int q = (p + r) / 2;
merge_sort_rec(A, p, q, temp);
merge_sort_rec(A, q + 1, r, temp);
merge(A, p, q, r, temp);
}
}
void merge_sort(int A[], int n) {
int *temp = malloc(sizeof(int) * (n + 1)); // 1-based라 n+1
if (!temp) { perror("malloc"); exit(1); }
merge_sort_rec(A, 1, n, temp);
free(temp);
}
int main(void) {
int n;
printf("정렬할 원소 개수 입력: ");
scanf("%d", &n);
// 원본 배열 동적 할당
int *A = malloc(sizeof(int) * (n + 1)); // index 1~n 사용
if (!A) { perror("malloc"); exit(1); }
printf("%d개의 원소를 입력하세요:\n", n);
for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
printf("Before: ");
for (int i = 1; i <= n; i++) printf("%d ", A[i]);
puts("");
merge_sort(A, n);
printf("After : ");
for (int i = 1; i <= n; i++) printf("%d ", A[i]);
puts("");
free(A); // 원본 배열 메모리 해제
return 0;
}코드쓰면서 느낀점
정렬하려는 배열이 홀수개면 문제가 있나 생각해봤는데 소수점은 정수로 다운처리되고 배열도 정렬후 남은건 앞or뒤에 붙이는 알고리즘이니 문제가 없었다. 배열은 수정이 들어가는 함수여도 파라메터로 []을 쓰면 int *a=int a[]나 같은것도 배우면서 포인터 개념도 복습하는데 도움이 된 것 같다.
시간복잡도구하기(worst case)
문제정의:
정렬할 구간의 크기는 r-p+1
merge_sort는 divide 2개 combine 1개니까
재귀식:
𝑇(𝑛) = 𝑇(⌊𝑛/2⌋)+𝑇(⌈𝑛/2⌉)+𝑐𝑛 , 𝑇(1)=Θ(1)
“레벨”로 나눠 생각하기
병합정렬은 배열을 반씩 나누기 때문에 재귀 깊이가
log2의 n이다
레벨 0: 배열 전체 크기
n
레벨 1: 두 구간
n/2
레벨 2: 네 구간
n/4
…
레벨 logn:
원소 크기 1씩
레벨별 실행 횟수(1 based 배열일때)
블록 크기= n/2^(k-1) , 병합 개수=2^(k-1) ,
각 레벨마다 merge의 비교횟수 2^(k-1) * (n/2^(k-1) -1)
=n-2^(k-1) <- 일반항
전체 비용합
각 레벨 수열의 합으로 전부 합치면 n-1 + n-2 + ~~~ + = nlogn -n +1 이 나온다
시간 복잡도는 O(nlogn)
하나하나 일반항 따져가며 수열의 합으로 구했지만 간단하게 한다면 레벨비용은 n에 가깝고 레벨수는 logn이니 O(nlogn)이다.
빅오구해보고 느낀점
생각해보면 best case나 average 케이스도 레벨별 실행횟수가 O(n)으로 나올거기때문에 이 경우에도 같은 시간복잡도일 것이라는 생각이 들었다. 또한 정렬하는부분에서 다른 알고리즘을 넣는다면 실행횟수(T(n))를 더 줄일 수 있을 것 같을것 같다
마무리
병합정렬은 Divide & Conquer 대표 알고리즘으로, 항상 O(n log n)의 안정적인 시간복잡도를 가진다. Best/Average/Worst 모두 동일하다.
구현 과정에서 포인터 개념을 복습할 수 있었고, 홀수 크기의 배열도 별도 예외처리 없이 자연스럽게 처리된다는 점을 알아갔다.
또한 레벨별 비용을 일반항으로 세어 합하면 nlogn-n+1이라는 결과가 나오고, 이를 통해 O(nlogn)임을 직접 확인할 수 있었다.
생각해보면, 특정 구간을 다른 정렬(예: 삽입정렬)로 대체하는 하이브리드 접근은 실행 시간을 줄일 수 있지만, 병합정렬 자체 구조로는 O(nlogn)을 더 낮출 수 없다는 점도 깨달았다.
