분할 정복 기법을 기반으로 한 정렬 알고리즘인 병합 정렬. 병합 정렬의 시간 복잡도는 O(n log n)입니다. 알고리즘은 먼저 배열을 동일한 반으로 나눈 다음 특정 방식으로 병합합니다.
반복 병합 정렬
반복 병합 정렬에서는 재귀 접근 방식을 사용하여 요소를 동일한 반으로 나눈 다음 반복 방식을 사용하여 정렬된 배열로 다시 병합합니다.
반복적 병합 정렬을 위한 프로그램
/* 병합 정렬을 위한 재귀 C 프로그램 */
예시
#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void iterativeMergeSort(int arr[], int l, int r) {
if (l < r){
int mid = l+(r-l)/2;
iterativeMergeSort(arr, l, mid);
iterativeMergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
}
int main(){
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr)/sizeof(arr[0]);
printf("\t\t ITERATIVE MERGE SORT \n");
printf("Unsorted Array : \t");
for (int i=0; i < size; i++)
printf("%d ",arr[i]);
iterativeMergeSort(arr, 0, size - 1);
printf("\nSorted array : \t");
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
} 출력
ITERATIVE MERGE SORT Unsorted Array : 12 11 13 5 6 7 Sorted array : 5 6 7 11 12 13