병합 정렬
안정 정렬을 알아봅니다
병합 정렬은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
안정 정렬
병합 정렬은 배열을 절반으로 나누고 각 절반을 정렬한 다음 다시 병합하는 분할 정복 정렬입니다. 모든 경우에 O(n log n)이며 안정적입니다.
분할 단계
각 조각의 원소가 하나가 될 때까지 배열을 중간 지점에서 재귀적으로 나눕니다. 원소 하나는 자명하게 정렬된 상태이므로 기본 경우가 됩니다.
병합 단계
핵심 연산은 이미 정렬된 두 실행 구간을 하나로 병합하는 것입니다. 인덱스 포인터로 두 구간을 탐색하면서 앞에 있는 원소 중 더 작은 것을 항상 다음에 복사합니다.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}안정적인 이유
병합에서는 a[i] <= a[j]를 사용하므로 두 원소가 같을 때 왼쪽 실행 구간의 원소를 먼저 가져옵니다. 왼쪽 구간에는 더 앞에 있던 원소가 들어 있으므로 원래 순서가 보존됩니다.
재귀 실행 함수
병합 정렬은 각 절반에 재귀적으로 적용한 다음 병합합니다. 호출할 때마다 메모리를 할당하지 않도록 공유 임시 버퍼를 전달합니다.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}메모리 사용량
퀵 정렬과 달리 병합 정렬은 병합 버퍼에 O(n)의 추가 메모리가 필요합니다. 메모리가 제한된 환경에서 매우 큰 배열을 처리할 때 이것이 주요 단점입니다.
보장되는 O(n log n)
재귀는 항상 절반으로 나뉘므로 log n개의 레벨이 생기고, 각 레벨에서는 n개의 원소를 병합합니다. 따라서 병합 정렬은 퀵 정렬과 달리 최선, 평균, 최악의 모든 경우에 O(n log n)입니다.
병합 레벨 세기
재귀 레벨 수는 ceil(log2 n)입니다. 여러 크기에 대해 계산해 보겠습니다.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}상향식 병합 정렬
반복형 변형은 크기가 1인 실행 구간을 병합한 다음 2, 4로 진행하며 각 단계마다 크기를 두 배로 늘립니다. 재귀를 완전히 사용하지 않으며 연결 리스트에도 적합합니다.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}병합 정렬을 선택할 때
다음이 필요할 때 병합 정렬을 우선 고려하십시오.
- 나쁜 경우가 없는 O(n log n) 보장
- 안정성
- 연결 리스트 정렬(임의 접근이 필요하지 않음)
- RAM에 담기에는 너무 큰 데이터의 외부 정렬
병합 정렬과 퀵 정렬 비교
퀵 정렬은 일반적으로 실제 환경에서 더 빠르고 제자리에서 정렬되지만, 최악의 경우가 나쁠 수 있으며 안정적이지 않습니다. 병합 정렬은 안정적이고 실행 시간이 보장되지만 추가 메모리를 사용합니다. 제약 조건에 따라 선택하십시오.
빠른 확인
병합 정렬에 대한 이해도를 확인해 보십시오.
복습
병합 정렬을 배웠습니다.
- 절반으로 나누고 각각 정렬한 다음 병합합니다.
- 병합할 때 같은 키는 왼쪽을 먼저 처리하므로 안정성이 유지됩니다.
- 모든 경우에 O(n log n)이 보장됩니다.
- O(n)의 추가 메모리가 필요하며 연결 리스트와 외부 정렬에 적합합니다.
자주 묻는 질문
“병합 정렬” 강의는 무료인가요?
네 — “병합 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“병합 정렬”에서 뭘 배우나요?
안정 정렬을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“병합 정렬” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.