(5)[Chapter12]분할정복_1_병합정렬(이론_노트)

##이론 노트 PDF파일 :

분할정복_1_병합정렬_이론노트.pdf

2.00MB

##이론 노트 사진:

 

 

 

 

## 퀵소트와 머지소트의 공통점과 차이점 :

• 공통점 : 분할 정복을 알고리즘을 이용한다.(구간을 나누고, 재귀호출 이용)
• 차이점 :

- 퀵소트 : 분할할 때, 구간을 나누는 기준이 PIVOT값이다.

- 머지소트 : 분할할 때, 구간을 나누는 기준이 절반(MID)이다.

 

##코드 내용 :

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
//2_ 정복 구현부 Merge()
void Merge(int* A, int start, int mid , int end) 
{
    //1_ 정찰대 2명 선언 , 초기화
    int L = start;
    int R = mid + 1;
    //2_ 임시 배열 동적 할당,임시배열 지정용 인덱스 선언
    int* B = (int*)malloc(sizeof(int) * (end - start + 1));
    int B_index = 0;
    //3_ 정찰_1 시작 : 둘 중 하나가 SCAN이 끝날 때 까지
 
    while (L<=mid&&R<=end) {
        if (A[L] < A[R]) {
            B[B_index] = A[L];
            L++;
        }
        else {
            B[B_index] = A[R];
            R++;
        }
        B_index++;
    }
 
    //4_정찰_2 : 둘중 하나가 SCAN이 끝났다면, => 나머지 안끝난 배열을 임시배열에 몽땅 순차적 저장 작업
    if (L <= mid) 
    {
        while (L <= mid) 
        {
            B[B_index] = A[L];
            L++;
            B_index++;
        }
    }
 
    if (R <= end) {
        while (R <= end)
        {
            B[B_index] = A[R];
            R++;
            B_index++;
        }
    }
 
    //5_ 임시배열 B의 내용을 A에 다시 복사 + 붙여넣기
    for (int i = 0; i < (end - start + 1); i++) {
        A[i + start] = B[i];
    }
 
    //6_임시 배열 메모리 해제
    free(B);
 
}
 
//1_ 분할 정복 MergeSort()
void MergeSort(int* A, int start, int end)
{
    //1_ 재귀 종료 조건 : start +1 > end
    if (start + 1 > end) return;
 
    //2_ mid 지정
    int mid = (start + end) / 2;
 
    //3_ 분할(start ~ ★mid(포함) / mid + 1 ~ end)
    MergeSort(A, start, mid);
    MergeSort(A, mid+1, end);
 
    //4_ 정복
    Merge(A, start, mid, end);
 
}
 
void PrintArr(int* arr , int size) {
    for (int i = 0; i < size; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}
 
int main() 
{
    int N;
    int* arr = NULL;
 
    scanf("%d", &N);
 
    arr = (int*)malloc(sizeof(int)*N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    MergeSort(arr, 0, N - 1);
 
    PrintArr(arr, N);
 
    free(arr);
 
    return 0;
}