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

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

분할통치법

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 #include //합병정렬 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 함수 부분이 잘 이해가 안됨 복습 하기

from http://code731.tistory.com/28 by ccl(A) rewrite - 2021-10-19 03:26:47