병합 정렬 (Merge sort)
정렬 알고리즘 중 병합 정렬(Merge sort)은 분할 정복으로 리스트를 정렬합니다. 아래는 병합 정렬의 프로세스를 잘 보여주는 그림입니다.
이 글에서는 연결 리스트에 대해 병합 정렬을 적용해 보겠습니다.
연결 리스트의 병합 정렬
다음과 같이 연결 리스트 구조체를 선언하고 노드를 만드는 함수와 새롭게 만들어진 노드를 리스트에 추가하는 함수를 작성해 보겠습니다.
#include <stdlib.h>
typedef struct s_list
{
void *content;
size_t content_size; // size_t 자료형은 string.h, stdlib.h 등에 선언되어 있습니다.
struct s_list *next;
} t_list;
// 새로운 노드를 만드는 함수
t_list *lstnew(const void *content, size_t content_size)
{
t_list *list;
list = (t_list *)malloc(sizeof(t_list));
if (list == NULL)
return (NULL);
if (content == NULL)
{
list->content = NULL;
list->content_size = 0;
}
else
{
list->content = malloc(content_size);
if (list->content != NULL)
{
memcpy(list->content, content, content_size);
list->content_size = content_size;
}
}
list->next = NULL;
return (list);
}
// 새로운 노드를 리스트의 가장 앞에 추가하는 함수
void lstadd(t_list **alst, t_list *n)
{
if (alst == NULL || n == NULL)
return ;
n->next = *alst;
*alst = n;
}
연결 리스트에 대한 병합 정렬 알고리즘의 순서는 다음과 같습니다.
MergeSort(head)
- 만약
head가NULL이거나head->next가NULL이면, 즉 리스트의 길이가 0 또는 1이면 아무 것도 반환하지 않습니다.- 아니라면 리스트를 절반으로 나눕니다. (함수
split)- 나눠진 리스트를 재귀적으로 분할 정렬합니다.
MergeSort(a)MergeSort(b)- 분할 정렬된 리스트들을 병합합니다. 이 때 이미 정렬되어 있는 두 리스트에 대해 순차적으로 비교 연산해 병합합니다. (함수
sorted_merge)
먼저 리스트를 절반으로 나누는 함수 split 을 작성해 보겠습니다.
void split(t_list *head, t_list **front, t_list **back)
{
t_list *fast;
t_list *slow;
slow = head;
fast = head->next;
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
}
*front = head;
*back = slow->next;
slow->next = NULL;
}변수 slow 가 한번 전진할 때 fast 는 두 번 전진해 리스트의 중간을 찾습니다. 이 후 매개변수 front 에 두 개로 나뉠 리스트 중 앞의 리스트의 첫번째 노드를, back 에 뒤의 리스트의 첫번째 노드를 저장하게 됩니다. 마지막 줄의 slow->next = NULL 는 앞의 리스트의 끝을 알리기 위함입니다.
다음으로 두 개로 나뉜 리스트를 병합하는 함수 sorted_merge 입니다.
t_list *sorted_merge(t_list *front, t_list *back,\
int (*compare)(t_list *, t_list *))
{
t_list *res;
res = NULL;
if (front == NULL)
return (back);
else if (back == NULL)
return (front);
if (compare(front, back) > 0)
{
res = back;
res->next = sorted_merge(front, back->next, compare);
}
else
{
res = front;
res->next = sorted_merge(front->next, back, compare);
}
return (res);
}만약 두 개의 리스트 front 와 back 에 각각 [1, 3], [2, 4] 가 저장되어 있다면 sorted_merge 함수는 아래와 같이 병합 정렬합니다.
- 두 리스트의 가장 앞선 값 1과 2를 비교해 1을 가진 노드를
res에 저장합니다. 이후 다음 올 노드는[3]과[2, 4]에 대해 재귀적으로 정렬합니다. - 두 리스트의 가장 앞선 값 3과 2를 비교해 2를 가진 노드를
res에 저장합니다. 이 때 변수res는 함수를 호출한 이전 재귀함수의 변수res->next에 저장됩니다. 이후 다음 올 노드는[3]과[4]에 대해 재귀적으로 정렬합니다. - 두 리스트의 가장 앞선 값 3과 4를 비교해 3을 가진 노드를
res에 저장합니다. 이 때 변수res는 함수를 호출한 이전 재귀함수의 변수res->next에 저장됩니다. 이후 다음 올 노드는[]과[4]에 대해 재귀적으로 정렬합니다. front는 값이 없는 리스트이므로 4를 가진 노드를 반환합니다. 이 때 반환된 노드는 함수를 호출한 이전 재귀함수의 변수res->next에 저장됩니다.
마지막으로 분할과 병합을 재귀적으로 호출할 함수 merge_sort 입니다.
void merge_sort(t_list **head,\
int (*compare)(t_list *, t_list *))
{
t_list *front;
t_list *back;
if (head == NULL)
return ;
if (*head == NULL || (*head)->next == NULL)
return ;
split(*head, &front, &back);
merge_sort(&front, compare);
merge_sort(&back, compare);
*head = sorted_merge(front, back, compare);
}앞서 작성한 두 함수 split 과 sorted_merge 를 완벽히 이해했다면 재귀함수 merge_sort 를 이해하는데 크게 어려움은 없을 것입니다. 함수 merge_sort 는 리스트의 길이가 0 또는 1이 될 때까지 분할을 계속하고 나눠진 리스트에 대해 병합 정렬합니다.
아래 메인 함수로 직접 테스트해 보겠습니다.
int compare(t_list *a, t_list *b)
{
return (*(int *)(a->content) - *(int *)(b->content));
}
int main(void)
{
int arr[5] = {3, 4, 2, 1, 5};
t_list *list;
t_list *cur;
list = NULL;
for (int i=0; i < 5; i++)
lstadd(&list, lstnew((void *)(&(arr[i])), sizeof(int)));
cur = list;
for (int i=0; i < 5; i++)
{
printf("%d ", *((int *)(cur->content)));
cur = cur->next;
}
printf("\n");
merge_sort(&list, &compare);
cur = list;
for (int i=0; i < 5; i++)
{
printf("%d ", *((int *)(cur->content)));
cur = cur->next;
}
printf("\n");
return (0);
}
/*
* 출력 결과
* 5 1 2 4 3
* 1 2 3 4 5
*/
