[알고리즘] 병합 정렬

https://www.youtube.com/watch?v=oHRChO--Hjs

이보다 친절한 수업은 없다

 

 

내가 짠 코드

#include <stdio.h>
#include <stdlib.h>
 
void merge(int* a, int p, int q, int r);

void mergeSort(int* a, int p, int r) {
	int q;
	if (p < r) {
		q = (p + r) / 2;
		mergeSort(a, p, q);	// 전반부
		mergeSort(a, q + 1, r);	// 후반부
		merge(a, p, q, r);
	}
}
void merge(int* a, int p, int q, int r) {
	int i;
	int p_idx = p;
	int q_idx = q + 1;
	int r_idx = r;
	int a_idx = p;
	int* tmp = (int*)malloc(sizeof(int) * (r - p + 1));

	for (i = p; i <= r; i++)
		tmp[i - p] = a[i];	// 배열 복사

	while (p_idx <= q && q_idx <= r) {	
		if (tmp[p_idx - p] < tmp[q_idx - p])
			a[a_idx++] = tmp[p_idx++ - p];
		else
			a[a_idx++] = tmp[q_idx++ - p];
	}

	while (p_idx <= q) {
		a[a_idx++] = tmp[p_idx++ - p];
	}
	while (q_idx <= r) {
		a[a_idx++] = tmp[q_idx++ - p];
	}
	free(tmp);
}
int main(void) {
	int arr[10] = { 22,10,2,3,1,5,7,4,8,11 };
	mergeSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);

	return 0;
}

 

 

정석 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#pragma warning (disable : 4996)

//매크로 함수 : 호출하고 리턴하는 것이 아니라 호출부를 정의부로 대체하기 때문에 실행 성능이 향상된다.
#define SWAP(type, p1, p2) do{ type temp = p1; p1 = p2; p2 = temp; }while(0)

void randomize(int* arr, int size, int begin, int end)
{
	int range = (end - begin) + 1;
	int i;

	srand((unsigned int)time(NULL));
	for (i = 0; i < size; i++)
		arr[i] = rand() % range + begin;
}

void display(int* arr, int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%8d", arr[i]);
	puts("");
}

void merge(int* arr, int* temp, int left, int mid, int right)
{
	int i;
	int p1 = left;
	int p2 = mid + 1;
	int pM = left;

	//데이터 복사
	for (i = left; i <= right; i++)
		temp[i] = arr[i];

	//값 비교 후, arr배열에 저장
	while (p1 <= mid && p2 <= right)
	{
		if (temp[p1] < temp[p2])
			arr[pM++] = temp[p1++];
		else
			arr[pM++] = temp[p2++];
	}

	while (p1 <= mid)
		arr[pM++] = temp[p1++];

	while (p2 <= right)
		arr[pM++] = temp[p2++];
}

void mergeSortUtil(int* arr, int* temp, int left, int right)
{
	int mid;

	if (left < right)
	{
		mid = (left + right) / 2;
		mergeSortUtil(arr, temp, left, mid); //왼쪽 재귀호출(나누기)
		mergeSortUtil(arr, temp, mid + 1, right); //오른쪽 재귀호출(나누기)

		merge(arr, temp, left, mid, right); //병합
	}
}

//O(N * logN) : 평균, 최선, 최악 모두 보장
void mergeSort(int* arr, int size)
{
	//공간복잡도 : O(N) => 배열의 크기만큼 별도의 공간이 필요하다.
	int* temp = (int*)malloc(sizeof(int) * size);

	//정렬할 배열, 임시배열, 첫번째 인덱스, 마지막 인덱스
	mergeSortUtil(arr, temp, 0, size - 1);
}

int main()
{
	int* arr;
	int size;
	int begin, end;

	printf("\n\n배열의 크기 입력 : ");
	scanf("%d", &size);
	while (getchar() != '\n');

	arr = (int*)malloc(sizeof(int) * size);

	printf("랜덤 시작 수 / 끝 수 (공백 구분) : ");
	scanf("%d %d", &begin, &end);
	while (getchar() != '\n');

	randomize(arr, size, begin, end); //begin ~ end사이의 정수를 랜덤하게 저장하는 함수

	printf("\n\n\t\t *** 정렬 전 데이터 출력 ***\n\n");
	display(arr, size);

	mergeSort(arr, size);

	printf("\n\n\t\t *** 정렬 후 데이터 출력 ***\n\n");
	display(arr, size);
	return 0;
}
​

 

이론은 이해가는데 코드 구현이 생각보다 어려웠다. 재귀 사용해서 배열 자르고 병합하는 과정 다시 복습해야 할 듯