4. 합병정렬

🔍분할통치법(분할정복)

분할: 입력데이터를 둘 이상의 부분집합으로 나눈다

재귀: 각각에 대한 부문제를 재귀적으로 해결한다.

• 재귀의 베이스케이스: 상수 크기의 작은 문제들

통치: 부문제들에 대한 해결을 합쳐 해결을 구한다.

예: 합병정렬, 퀵정렬

 

🔍합병정렬(merge-sort)

힙정렬처럼 비교에 기초한 정렬

O(n log n)의 시간복잡도

외부의 우선순위 큐를 사용하지 않고,

데이터를 순차적 방식으로 접근(디스크의 데이터 정렬에 적합)

합병정렬 알고리즘의 순서

1. 분할: 입력리스트 L을 n/2개 원소를 가진 리스트로 분할
2. 재귀: 위에서 나눈 L들을 정렬
3. 통치: 합병하며 순서리스트 형태로 정렬

merge(L1, L2)

L1 과 L2를 비교하며 넣어준다.

 

실제 구현

아래는 내가 실제로 구현한 합병정렬 알고리즘이다.

연결리스트로 구현한 정렬이며, 

오름차순으로 정렬했다.

typedef struct node {
	int data;
	struct node* next;
}node;

node* head = NULL;

node* createNode(int data) {
	node* newNode = (node*)malloc(sizeof(node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

void appendNode(int data) {
	node* newNode = createNode(data);
	if (head == NULL) {
		head = newNode;
		return;
	}
	node* now = head;
	while (now->next != NULL) {
		now = now->next;
	}
	now->next = newNode;
}

연결리스트 구현부이다.

node* mergeSort(node* list, int k) {
	if (list == NULL) {
		return;
	}
	node* L1 = list;
	node* L2 = partition(list, (k+1)/2);

	if ((k+1)/2 > 1) {
		L1 = mergeSort(L1, (k + 1) / 2);
	}
	if (k - (k + 1) / 2 > 1) {
		L2 = mergeSort(L2, k - (k + 1) / 2);
	}
	
	return merge(L1, L2);
}

합병정렬 구현부이다.

L1에는 현재 들어온 리스트의 처음 주소를, L2에는 partition함수를 작성해 절반의 주소를 넣어주었다.

L1과 L2또한 각각 분할하여 최종적으로 1개의 노드로 된 리스트가 될때 까지 분할한다. 

마지막으로 둘을 합병한 값을 반환하여 L1, L2를 갱신한다.

node* partition(node* L, int k) {
	node* now = L;
	node* prev = L;
	for (int i = 0; i < k; i++) {
		prev = now;
		now = now->next;
	}
	prev->next = NULL;
	return now;
}

partition의 구현부이다.

단일 연결리스트이므로 절반만큼 앞으로 가서 그부분을 리턴해준다.

이전 값과의 연결을 끊어준다.

node* merge(node* L1, node* L2) {
	node* L;
	if (L1->data < L2->data) {
		L = L1;
		L1 = L1->next;
	}
	else {
		L = L2;
		L2 = L2->next;
	}
	L->next = NULL;
	node* now = L;
	while (L1 != NULL && L2 != NULL) {
		if (L1->data < L2->data) {
			now->next = L1;
			L1 = L1->next;
		}
		else {
			now->next = L2;
			L2 = L2->next;
		}
		now = now->next;
		now->next = NULL;
	}
	if (L1 != NULL) {
		now->next = L1;
	}
	if (L2 != NULL) {
		now->next = L2;
	}
	return L;
}

병합 구현부이다.

첫 노드를 삽입한 이후, 두 리스트에서 더 큰 값을 삽입시켜준다.

반복하다 값 하나가 사라질 경우 나머지 값들을 모두 넣는다.

전체코드

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

typedef struct node {
	int data;
	struct node* next;
}node;

node* head = NULL;

node* createNode(int data) {
	node* newNode = (node*)malloc(sizeof(node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

void appendNode(int data) {
	node* newNode = createNode(data);
	if (head == NULL) {
		head = newNode;
		return;
	}
	node* now = head;
	while (now->next != NULL) {
		now = now->next;
	}
	now->next = newNode;
}

node* partition(node* L, int k) {
	node* now = L;
	node* prev = L;
	for (int i = 0; i < k; i++) {
		prev = now;
		now = now->next;
	}
	prev->next = NULL;
	return now;
}
node* merge(node* L1, node* L2) {
	node* L;
	if (L1->data < L2->data) {
		L = L1;
		L1 = L1->next;
	}
	else {
		L = L2;
		L2 = L2->next;
	}
	L->next = NULL;
	node* now = L;
	while (L1 != NULL && L2 != NULL) {
		if (L1->data < L2->data) {
			now->next = L1;
			L1 = L1->next;
		}
		else {
			now->next = L2;
			L2 = L2->next;
		}
		now = now->next;
		now->next = NULL;
	}
	if (L1 != NULL) {
		now->next = L1;
	}
	if (L2 != NULL) {
		now->next = L2;
	}
	return L;
}

node* mergeSort(node* list, int k) {
	if (list == NULL) {
		return;
	}
	node* L1 = list;
	node* L2 = partition(list, (k+1)/2);

	if ((k+1)/2 > 1) {
		L1 = mergeSort(L1, (k + 1) / 2);
	}
	if (k - (k + 1) / 2 > 1) {
		L2 = mergeSort(L2, k - (k + 1) / 2);
	}
	
	return merge(L1, L2);
}




int main() {
	int n, data;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &data);
		appendNode(data);
	}
	head = mergeSort(head, n);

	node* now = head;
	while (now != NULL) {
		printf(" %d", now->data);
		now = now->next;
	}

	

	return 0;
}