정렬(Sorting)이란 데이터 요소들을 오름차순 또는 내림차순으로 배열하는 과정을 말합니다. 효율적인 데이터 처리를 위해 다양한 정렬 알고리즘이 개발되어 왔으며, 그중 병합 정렬(Merge Sort)은 안정성과 일관된 성능으로 널리 사용되는 대표적인 알고리즘입니다.
C 언어의 5가지 대표 정렬 기법
C 언어에서 주로 사용되는 정렬 기법은 다음과 같습니다.
- 버블 정렬(Bubble Sort, 교환 정렬)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort, 선형 정렬)
- 퀵 정렬(Quick Sort, 분할 교환 정렬)
- 병합 정렬(Merge Sort, 외부 정렬)
병합 정렬(Merge Sort)이란?
병합 정렬은 분할 정복(Divide and Conquer) 방식에 기반한 정렬 알고리즘입니다. 동작 원리는 다음 세 단계로 요약할 수 있습니다.
- 분할(Divide): 배열을 절반으로 나눕니다.
- 정복(Conquer): 나눈 각 부분 배열을 재귀적으로 정렬합니다.
- 병합(Merge): 정렬된 두 부분 배열을 하나로 합칩니다.
병합 정렬 동작 예시
다음과 같은 정렬되지 않은 배열에 병합 정렬을 적용해 보겠습니다.
38, 27, 43, 3, 9, 82, 10
먼저 배열을 반복적으로 절반씩 분할하여 더 이상 나눌 수 없을 때까지 쪼갭니다.
그다음, 분할된 요소들을 두 개씩 비교하며 정렬하고, 이를 다시 병합하는 과정을 반복하면 최종적으로 다음과 같이 정렬된 배열을 얻습니다.
3, 9, 10, 27, 38, 43, 82
C 언어 구현 예제
다음은 병합 정렬 기법을 사용해 배열의 요소를 정렬하는 C 프로그램입니다.
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}실행 결과
위 프로그램을 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.
List before sorting 10 14 19 26 27 31 33 35 42 44 0 List after sorting 0 10 14 19 26 27 31 33 35 42 44
병합 정렬의 시간 복잡도
병합 정렬의 시간 복잡도는 데이터 상태와 무관하게 항상 O(n log n)으로 일정합니다. 최악의 경우에도 성능이 보장되며, 같은 값의 순서가 유지되는 안정 정렬(Stable Sort)이라는 장점이 있습니다. 다만 병합 과정에서 추가 메모리 공간(O(n))이 필요하다는 점은 고려해야 합니다.