병합 정렬 C언어 코드

2023.02.16  최초 작성

 

#include <stdio.h>
#include <stdlib.h>
void marge(int arr[], int left, int mid, int right) {
	printf("left : %d, mid : %d, right : %d", left, mid, right);
	int size = right + 1 - left;
	printf(", tmpArr size : %d\n", size);
	printf("[");
	for (int i = left; i <= mid; i++) {
		printf("%d ", arr[i]);
	}
	printf("] vs [");
	for (int i = mid + 1; i <= right; i++) {
		printf("%d ", arr[i]);
	}
	printf("]\n");
	int* tmpArr = (int*)malloc(sizeof(int) * size);
	if (tmpArr == NULL) {
		puts("정렬을 위한 임시 배열 공간 할당에 실패하였습니다.");
		return;
	}
	int lp = left, rp = mid + 1, index = 0;
	while (lp <= mid && rp <= right) {
		if (arr[lp] <= arr[rp]) {
			*(tmpArr + index) = arr[lp++];	index++;
		}
		else {
			*(tmpArr + index) = arr[rp++];	index++;
		}
	}
	while (lp <= mid) {
		*(tmpArr + index) = arr[lp++];	index++;
	}
	while (rp <= right) {
		*(tmpArr + index) = arr[rp++];	index++;
	}
	printf("marge 정렬 후 -- [");
	for (int i = 0; i < size; i++) {
		printf("%d ", *(tmpArr + i));
	}
	printf("]\n\n");
	for (int i = left, index = 0; i <= right; i++, index++) {
		arr[i] = *(tmpArr + index);
	}
	free(tmpArr);
}
void margeSort(int arr[], int left, int right) {
	if (left == right) {
		return;
	}

	printf("arr[");
	for (int i = left; i <= right; i++) {
		printf("%d ", arr[i]);
	}
	printf("]\n");
	int mid = (left + right) / 2;
	margeSort(arr, left, mid); // 왼쪽 배열을 다시 분할
	margeSort(arr, mid + 1, right); // 오른쪽 배열을 다시 분할
	marge(arr, left, mid, right); // 정렬과 병합
}
void main() {
	int arr[14] = { 19,34,24,5,47,12,4,1,37,42,21,3,13,29 };
	int size = sizeof(arr) / sizeof(int);
	puts("정렬 전 ======");
	for (int i = 0; i < size; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	margeSort(arr, 0, size - 1);
	puts("정렬 후 ======");
	for (int i = 0; i < size; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

[실행 결과]

정렬 전 ======
19 34 24 5 47 12 4 1 37 42 21 3 13 29
arr[19 34 24 5 47 12 4 1 37 42 21 3 13 29 ]
arr[19 34 24 5 47 12 4 ]
arr[19 34 24 5 ]
arr[19 34 ]
left : 0, mid : 0, right : 1, tmpArr size : 2
[19 ] vs [34 ]
marge 정렬 후 -- [19 34 ]

arr[24 5 ]
left : 2, mid : 2, right : 3, tmpArr size : 2
[24 ] vs [5 ]
marge 정렬 후 -- [5 24 ]

left : 0, mid : 1, right : 3, tmpArr size : 4
[19 34 ] vs [5 24 ]
marge 정렬 후 -- [5 19 24 34 ]

arr[47 12 4 ]
arr[47 12 ]
left : 4, mid : 4, right : 5, tmpArr size : 2
[47 ] vs [12 ]
marge 정렬 후 -- [12 47 ]

left : 4, mid : 5, right : 6, tmpArr size : 3
[12 47 ] vs [4 ]
marge 정렬 후 -- [4 12 47 ]

left : 0, mid : 3, right : 6, tmpArr size : 7
[5 19 24 34 ] vs [4 12 47 ]
marge 정렬 후 -- [4 5 12 19 24 34 47 ]

arr[1 37 42 21 3 13 29 ]
arr[1 37 42 21 ]
arr[1 37 ]
left : 7, mid : 7, right : 8, tmpArr size : 2
[1 ] vs [37 ]
marge 정렬 후 -- [1 37 ]

arr[42 21 ]
left : 9, mid : 9, right : 10, tmpArr size : 2
[42 ] vs [21 ]
marge 정렬 후 -- [21 42 ]

left : 7, mid : 8, right : 10, tmpArr size : 4
[1 37 ] vs [21 42 ]
marge 정렬 후 -- [1 21 37 42 ]

arr[3 13 29 ]
arr[3 13 ]
left : 11, mid : 11, right : 12, tmpArr size : 2
[3 ] vs [13 ]
marge 정렬 후 -- [3 13 ]

left : 11, mid : 12, right : 13, tmpArr size : 3
[3 13 ] vs [29 ]
marge 정렬 후 -- [3 13 29 ]

left : 7, mid : 10, right : 13, tmpArr size : 7
[1 21 37 42 ] vs [3 13 29 ]
marge 정렬 후 -- [1 3 13 21 29 37 42 ]

left : 0, mid : 6, right : 13, tmpArr size : 14
[4 5 12 19 24 34 47 ] vs [1 3 13 21 29 37 42 ]
marge 정렬 후 -- [1 3 4 5 12 13 19 21 24 29 34 37 42 47 ]

정렬 후 ======
1 3 4 5 12 13 19 21 24 29 34 37 42 47

 

 

728x90

반응형