[합병 정렬] 단일연결리스트를 이용한 합병정렬 구현

분할통치법

1. 분할

2. 재귀

3. 통치

 

합병정렬: 분할통치법에 기초한 정렬 알고리즘

- 힙 정렬과 달리 우선순위 큐 사용하지 X

- 데이터를 순차적 방식으로 접근

 

 

단일연결리스트를 이용한 합병정렬 구현(중복 입력 O)

 

입력 예시 1
3 ↦ n
4 9 1

출력 예시 1
□1 4 9 ↦ 정렬 결과

입력 예시 2
8 ↦ n
73 65 48 31 29 20 8 3

출력 예시 2
□3 8 20 29 31 48 65 73 ↦ 정렬 결과

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

//합병정렬

typedef struct ListNode {
	int elem;
	struct ListNode* next;
}node;

void addList(node** L, int elem) {// 리스트에 원소 추가
	node* q = (node*)malloc(sizeof(node));
	q->elem = elem;
	q -> next = NULL;

	node* p = *L;
	if (*L == NULL) {
		*L = q;
	}
	else {
		while (p->next != NULL) {
			p = p->next;
		}
		p->next = q;
	}
}

void partition(node* L, node** L1, node** L2, int size) {
	node* p = L;

	*L1 = L;
	for (int i = 0; i < (size / 2) - 1; i++) {
		p = p->next;
	}
	*L2 = p->next;
	p->next = NULL;
}

node* merge(node* L1, node* L2) {
	node* p = NULL;

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

	if (L1->elem < L2->elem) {
		p = L1;
		p->next = merge(L1->next, L2);
	}
	else {
		p = L2;
		p->next = merge(L1, L2->next);
	}

	return p;
}

void mergeSort(node** L, int size) {
	node* L1, * L2, * p = *L;

	if (size <= 1)
		return;

	partition(p, &L1, &L2, size);
	if (size % 2 == 0) {
		mergeSort(&L1, size / 2);
		mergeSort(&L2, size / 2);
	}
	else {
		mergeSort(&L1, size / 2);
		mergeSort(&L2, (size / 2) + 1);
	}

	*L = merge(L1, L2);
}

void printList(node* L) {
	node* p = L;

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

void freeList(node* L) {
	node* p = L;

	while (p != NULL) {
		L = L->next;
		free(p);
		p = L;
	}
}

int main() {
	int n, e;

	node* L = NULL;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &e);
		getchar();
		addList(&L, e);
	}

	mergeSort(&L, n);
	printList(L);

	freeList(L);// 노드 free

	return n;
}

 

*연결리스트 링크 연결 하는 부분 잘 이해하기

**partition 함수 부분이 잘 이해가 안됨 복습 하기