[알고리즘][정렬] 합병 정렬

병합 정렬

정의

출처- https://imgur.com/

• 같은 개수의 원소를 가지는 부분 집합으로 기존 자료를 분할(divide)하고 분할된 각 부분 집합을 병합(merge)하면서 정렬 작업을 완성(conquer)하는 분할 정복(divide and conquer)기법에 의한 정렬
• 여러 개의 정렬된 부분 집합을 결합하여 정렬된 집합을 만듬
  • 2-way 병합: 2개의 정렬된 자료 집합을 병합하는 경우
  • n-way 병합: n개의 정렬된 자료 집합을 결합하는 경우
• 추가적인 배열 필요
• 합병 정렬의 단계
  1. 분할(divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다
  2. 정복(conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
  3. 결합(combine): 정렬된 부분 배열들을 하나의 배열에 통합한다.

반으로 나누고 합치는 순간에 정렬한다

병합 정렬은 크게 두 가지의 단계가 있다. 첫째 분할 단계이다. 분할 단계는 동일한 개수의 원소를 가지는 부분 집합으로 분할하며 더 이상 나눌 수 없을 때까지 계속한다. 둘째 병합 단계는 기존의 분할된 부분 집합의 자료를 합치면서 정렬을 실행하는 단계이다. 이미지에서는 숫자가 아닌 색 순서대로 오름차순 정렬하는 과정을 보여준다.

구현1

#include <stdio.h>
#include <stdlib.h>
void printArray(int value[], int count) {
	int i = 0;
	for (i = 0; i < count; i++) {
		printf("%d ", value[i]);
	}
	printf("\n");
}

void mergeSortInternal(int value[], int buffer[], int start, int middle, int end) {
	int i = 0, j = 0, k = 0, t = 0;
	i = start;//첫 번째 부분 집합의 원소를 가리키는 인덱스
	j = middle + 1;//두 번째 부분 집합의 원소를 가리키는 인덱스
	k = start;//결과 버퍼의 현재 위치를 가리키는 인덱스
	while (i <= middle && j <= end) {
		if (value[i] <= value[j]) {
			buffer[k] = value[i];
			i++;
		}
		else {
			buffer[k] = value[j];
			j++;
		}
		k++;
	}
	if (i > middle) {//첫 번째 부분집합의 원소는 모두 복사되었지만 다른 부분집합의 원소가 남아있음
		for (t = j; t <= end; t++,k++) {
			buffer[k] = value[t];
		}
	}
	else {
		for (t = i; t <= middle; t++,k++) {
			buffer[k] = value[t];
		}
	}
	for (t = start; t <= end; t++) {
		value[t] = buffer[t];
	}
	printf("start- %d, middle- %d, end- %d ", start, middle, end);
	for (t = start; t <= end; t++) {
		printf("%d ", value[t]);
	}
	printf("\n");
}


void mergeSort(int value[], int buffer[], int start, int end) {
	int middle = 0;
	if (start < end) {//원소의 개수가 1개가 될때까지 반복
		middle = (start + end) / 2;//2개의 부분 집합으로 나누기 위해 중간 위치 middle구하기 
		mergeSort(value, buffer, start, middle);
		mergeSort(value, buffer, middle + 1, end);
		//왼쪽 부분 집합(start,middle)과 오른쪽 부분 집합(middle+1,end)에 대해 병합 정렬 실행
		mergeSortInternal(value, buffer, start, middle, end);
		//병합 정렬이 완료된 두개의 부분집합에 대해 병합을 실시한다. 
	}
}

int main() {
	int values[] = { 80,50,70,10,60,20,40,30 };
	printf("Before Sort\n");
	printArray(values, 8);

	int* pBuffer=NULL;
	pBuffer = (int*)malloc(sizeof(int) * 8);
	if (pBuffer != NULL) {
		mergeSort(values, pBuffer, 0, 7);
		free(pBuffer);
	}

	printf("After Sort\n");
	printArray(values, 8);
	
}

• 위 코드는 정렬한 배열을 main함수에서 생성하여 매개변수로 받음

구현2

#include <stdio.h>
#pragma warning(disable:4996)
int number = 8;
int sorted[8];
void merge(int a[], int m, int middle, int n) {
	int i = m;
	int j = middle+1;
	int k = m;
	while (i <= middle && j <= n) {
		if (a[i] < a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if (i > middle) {
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	for (int t = m; t <= n; t++) {
		a[t] = sorted[t];
	}
}
void mergeSort(int a[], int m, int n) {
	if (m < n) {
		int middle = (m + n) / 2;
		mergeSort(a, m, middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}
int main(void) {
	int array[8] = { 7,6,5,8,3,5,9,1 };
	mergeSort(array, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d ", array[i]);
	}
}

• 위 코드는 정렬한 배열을 전역 변수로 설정하여 사용함

구현3

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_SIZE 10
int list[MAX_SIZE];
int n;
int sorted[MAX_SIZE];
void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;
	while (i <= mid && j <= right) {
		if (list[i] <= list[j]) {
			sorted[k++] = list[i++];
		}
		else {
			sorted[k++] = list[j++];
		}
	}
	if (i > mid) {
		for (l = j; l <= right; l++) {
			sorted[k++] = list[l];
		}
	}
	else {
		for (l = i; l <= mid; l++) {
			sorted[k++] = list[l];
		}
	}
	for (l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
}
void merge_sort(int list[], int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}
int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;
	}
	merge_sort(list, 0,MAX_SIZE-1);
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

특성

• 최선,평균,최악: O($nlogn$)
• 우수한 효율성을 가짐
• 안정성이 유지됨
• 추가 메모리 공간 필요
• 자료의 이동 횟수가 많음 -> 자료의 크기가 큰 경우 연결 리스트를 사용하여 연결 포인터만을 변경하는 방식 이용