[알고리즘] ep1-5) 병합정렬(merge sort)

ㅁ분할정복법 == 분할통치법(Divide and Conquer): 문제를 작은 부분으로 나누어 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방법

e.g. 병합정렬, 퀵정렬, 이진탐색, 하노이탑

 

 

 

ㅇ병합정렬 = 합병정렬(merge sort): 비교 기반의 정렬 알고리즘 중 하나로, 분할 정복 기법을 사용

"제자리 X + stable" O(nlog(n))

폰 노이만이 개발했으며 stable 특성 때문에 실무에서 많이 사용된다

 

 

병합(merge) 예시 - 연결리스트로 구현한 merge 함수

 

L1과 L2를 비교하며 L을 완성시킨다

 

 

 

 

(참고)      

합병정렬 트리: mergeSort의 실행을 이진트리로 보이기

이진트리의 각 노드는 mergeSort의 재귀호출을 표현하며 다음을 저장한다

- 실행 이전의 무순리스트 및 분할

- 실행 이후의 정렬리스트

루트는 초기 호출을 의미한다

리프들은 크기 1의 부리스트에 대한 호출을 의미한다

 

초기호출, 분할, 재귀호출

 

분할, 재귀호출

 

분할, 재귀호출, base case

 

재귀호출, base case

 

합병

 

재귀호출, ..., 합병

 

합병

 

재귀 호출, ..., 합병

 

합병

 

 

 

 

 

 

(병합정렬 구현 코드)

 

test case

 

 

1) 병합정렬 배열 버전

// 병합정렬 배열 버전
#include <stdio.h>
#include <stdlib.h>

int* g_arr; // 전역 배열 포인터
int g_n; // 전역 배열의 크기

void mergeSort(int left, int right); // 병합정렬 함수 선언
void merge(int left, int mid, int right); // 병합 함수 선언
void printArray();

int main() {
    scanf("%d", &g_n);
    g_arr = (int*)malloc(g_n * sizeof(int));
    for (int i = 0; i < g_n; i++) {
        scanf("%d", &g_arr[i]);
    }

    mergeSort(0, g_n - 1);
    printArray();

    free(g_arr);
    return 0;
}

// 병합 정렬 함수 정의
void mergeSort(int left, int right) {
    if (left < right) {
        // 중간 인덱스 계산 - 오버플로우 방지
        // mid = (left + right) / 2
        int mid = left + (right - left) / 2;

        // 왼쪽 절반 정렬
        mergeSort(left, mid);
        // 오른쪽 절반 정렬
        mergeSort(mid + 1, right);

        // 두 절반을 병합
        merge(left, mid, right);
    }
}

// 병합 함수 정의
void merge(int left, int mid, int right) {
    // 왼쪽 서브 배열의 크기 계산
    int n_L = mid - left + 1;
    // 오른쪽 서브 배열의 크기 계산
    int n_R = right - mid;

    // 왼쪽 서브 배열을 동적으로 할당
    int* L = (int*)malloc(n_L * sizeof(int));
    // 오른쪽 서브 배열을 동적으로 할당
    int* R = (int*)malloc(n_R * sizeof(int));

    // 왼쪽 서브 배열에 값 복사
    for (int i = 0; i < n_L; i++)
        L[i] = g_arr[left + i];
    // 오른쪽 서브 배열에 값 복사
    for (int j = 0; j < n_R; j++)
        R[j] = g_arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    // 두 서브 배열의 요소들을 비교하여 병합
    while (i < n_L && j < n_R) {
        if (L[i] <= R[j]) {
            g_arr[k] = L[i];
            i++;
        } 
        else {
            g_arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 왼쪽 서브 배열의 남은 요소들을 복사
    while (i < n_L) {
        g_arr[k] = L[i];
        k++;
        i++;
    }
    // 오른쪽 서브 배열의 남은 요소들을 복사
    while (j < n_R) {
        g_arr[k] = R[j];
        k++;
        j++;
    }

    free(L);
    free(R);
}

void printArray() {
    for (int i = 0; i < g_n; i++) {
        printf(" %d", g_arr[i]);
    }
    printf("\n");
}

/*
3
4 9 1

8
73 65 48 31 29 20 8 3

5
3 3 2 1 5
*/

 

 

 

 

 

 

2) 병합정렬 리스트 버전

// 병합정렬 리스트 버전
#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
    int e;
    struct NODE* next;
} NODE;

NODE* g_head = NULL;

NODE* newNode(int e);
void insert(int e);
void mergeSort(NODE** headReference);
void partition(NODE* head, NODE** frontReference, NODE** backReference);
NODE* merge(NODE* L1, NODE* L2);
void printList();
void freeList(NODE* head);

int main() {
    int n;
    int e;

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

    mergeSort(&g_head);
    printList();

    freeList(g_head);
    return 0;
}

NODE* newNode(int e) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->e = e;
    newNode->next = NULL;
    return newNode;
}

void insert(int e) {
    if (g_head == NULL) {
        g_head = newNode(e);
        return;
    }

    NODE* cur = g_head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode(e);
}

// 병합정렬 함수
void mergeSort(NODE** headReference) {
    NODE* head = *headReference;
    NODE* a;
    NODE* b;

    // 기본 경우 - 길이가 0 또는 1인 경우
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    // 리스트를 'a'와 'b' 하위 리스트로 분할
    partition(head, &a, &b);

    // 하위 리스트를 재귀적으로 정렬
    mergeSort(&a);
    mergeSort(&b);

    // 두 개의 정렬된 리스트를 합병
    *headReference = merge(a, b);
}

// 리스트를 두 개의 하위 리스트로 분할하는 함수
void partition(NODE* head, NODE** frontReference, NODE** backReference) {
    NODE* fast;
    NODE* slow;
    slow = head;
    fast = head->next;

    // 'fast'를 두 노드씩 이동하고, 'slow'를 한 노드씩 이동
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    // 'slow'는 리스트의 중간점 앞에 있으므로 그 지점에서 리스트를 둘로 나눔
    *frontReference = head;
    *backReference = slow->next;
    slow->next = NULL;
}

// 병합 함수
NODE* merge(NODE* L1, NODE* L2) {
    NODE* res = NULL;

    // 예외처리
    if (L1 == NULL) 
        return L2;
    else if (L2 == NULL) 
        return L1;

    // L1 또는 L2를 선택하고 재귀 호출
    if (L1->e <= L2->e) {
        res = L1;
        res->next = merge(L1->next, L2);
    } 
    else {
        res = L2;
        res->next = merge(L1, L2->next);
    }
    return res;
}

void printList() {
    NODE* cur = g_head;
    while (cur != NULL) {
        printf(" %d", cur->e);
        cur = cur->next;
    }
}

void freeList(NODE* head) {
    while (head != NULL) {
        NODE* cur = head;
        head = head->next;
        free(cur);
    }
}

/*
3
4 9 1

8
73 65 48 31 29 20 8 3

5
3 3 2 1 5
*/

 

 

 

 

 

 

 

 

(참고)

https://www.youtube.com/watch?v=FCAtxryNgq4

배열버전의 mergeSort 코드를 이해하는 데에 이만한 영상이 없다.. 꼭 보도록 하자!

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan), Discrete Mathematics and Its Applications(Kenneth H. Rosen)