[C] 단일연결리스트 합병정렬 (singly linked list merge sort)

합병정렬에 관한 포스팅은 따로 알고리즘 창고에 하겠습니다.

보통 배열로 이루어진 정렬만 해서 애를 먹었습니다. 특히 분할하는 부분에서 힘들었는데, 그래도 깔끔한 방법을 찾아내 만들었습니다. 

구조체 및 함수설명

NODE : 단일연결리스트를 구성하는 노드 구조체

TMP : partition 함수를 위한 구조체. 두 개의 반환값을 받아내기 위함

NODE* addNode(int n) : 노드를 추가하는 함수. 단일연결리스트 끝부분에 계속 붙여나가므로 새 노드 값의 next는 항상 NULL이다.

void mergeSort(NODE **L, int k) : 합병정렬함수. 재귀방식으로 구성돼있다. L은 리스트의 시작 주소, k는 리스트의 크기이다.

NODE* merge(NODE *L1, NODE *L2) : 합병함수. 두 개의 리스트를 주소연결을 바꾸어 정렬된 하나의 리스트로 만들어 주소값으로 반환한다.

TMP partition(NODE *L, int k) : 분할함수. 하나의 리스트를 |L|-k 크기, k 크기의 부 리스트 두개로 만들어 반환한다. 따로 저장공간 할당 없이 주소값으로 반환한다.  

소스코드

#include <stdio.h>
#include <stdlib.h>


typedef struct node {

	int n;

	struct node *next;

}NODE;

typedef struct {

	NODE *L1;
	NODE *L2;

}TMP;

NODE* addNode(int n);
void mergeSort(NODE **, int);
NODE* merge(NODE *, NODE *);
TMP partition(NODE *, int);

void printAll(NODE *node);

int main() {

	NODE *head;

	int n;
	int i;
	NODE *tmp;
	int t;

	head = (NODE *)malloc(sizeof(NODE));
	head->next = NULL;

	scanf("%d", &n);

	for (i = 0, tmp = head; i < n; i++) {

		scanf("%d", &t);

		tmp->next = addNode(t);

		tmp = tmp->next;

	}

	mergeSort(&head->next, n);

	printAll(head->next);

}

NODE* addNode(int n) {

	NODE *new_node;

	new_node = (NODE *)malloc(sizeof(NODE));

	new_node->n = n;
	new_node->next = NULL;

	return new_node;

}

void mergeSort(NODE **L, int k) {

	NODE *L1 = NULL, *L2 = NULL;
	TMP tmp;

	NODE *i;

	if (k > 1 && *L != NULL) {

		tmp = partition(*L, k / 2);
		L1 = tmp.L1;
		L2 = tmp.L2;

		mergeSort(&L1, k / 2);
		mergeSort(&L2, (int)((k / 2.0) + 0.5));

		*L = merge(L1, L2);

	}

}

NODE* merge(NODE *L1, NODE *L2) {

	NODE *result = NULL;

	if (L1 == NULL) return L2;
	else if (L2 == NULL) return L1;

	if (L1->n < L2->n) {
		result = L1;
		result->next = merge(L1->next, L2);
	}
	else {
		result = L2;
		result->next = merge(L1, L2->next);
	}
	
	return result;

}

TMP partition(NODE *L, int k) {

	NODE *p;
	TMP result;
	NODE *L1, *L2;

	int i;

	p = L;
	L1 = L;

	for (i = 0; i < k - 1; i++) {
		p = p->next;
	}

	L2 = p->next;

	p->next = NULL;

	result.L1 = L1;
	result.L2 = L2;

	return result;

}

void printAll(NODE *node) {

	NODE *i = node;

	while (i != NULL) {
		printf(" %d", i->n);
		i = i->next;
	}

	printf("\n");

}

요즘 프로젝트 때문에 C 안하니까 어색해서 엄청 오래걸렸다. 틈틈이 연습해야겠다.