[C 알고리즘] 병합 정렬 - Merge Sort Algorithm

정렬 알고리즘에서 퀵 정렬을 배운뒤 병합정렬 알고리즘을 접해보았습니다. 나동빈님의 블로그와 유튜브 강의를 통해 개념을 학습했는데 설명이 잘되어있어서 참고용으로 기록을 하기 위해 포스트를 씁니다.

 

이해한 내용을 저만의 언어로 설명하면서 학습해보겠습니다

 

 

출처:

https://blog.naver.com/ndb796/221227934987

7. 병합 정렬(Merge Sort)

 

 

병합 정렬은 시간복잡도 O(N*logN)을 가집니다. 코드에서도 알수있듯이 정렬을 분할해서 하기때문에 대표적인 분할정복 알고리즘이면서, 어떠한 경우에도 반씩 나누기때문에 최악의경우에도 시간복잡도 N*logN을 보장받습니다.

 

병합정렬을 이해할때 가장 핵심적인 키워드는 "일단 나누고 나중에 정렬" 입니다. 저도 처음에 이해하는데 시간이 오래걸렸지만 일단 나누고 나중에 정렬한다는 핵심에 집중하니 알고리즘의 전체적인 그림이 받아들여졌습니다

 

병합정렬 알고리즘의 전체적인 도식화입니다. 시작모습을 보면 알겠지만 배열의 원소들이 다 나누어져있습니다.

이 시작부분을 제대로 이해해야합니다.

 

여기서 mergeSort함수는

1. mergeSort함수(strat ~ middle)

2. mergeSort함수(middle +1 ~end) 범위 두가지의 호출을 재귀적으로 호출합니다.

 

이게 시작으로 가는 과정입니다. 배열을 각각 다 분리하고 그때부터 합치면서 정렬하는 전체적인 그림을 이해하고

이전의 포스트 퀵 정렬을 이해한다면 어렵지않게 이해할 수 있습니다.

 

#대표적인 분할정복 병합정렬의 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <stdio.h> #define number 8   void merge(int a[], int start, int middle, int end); void mergeSort(int a[], int start, int end);   int sorted[8];   void merge(int a[], int start, int middle, int end) {       int i, j, k; //각각 start middle middle+1 에 해당     i = start;     j = middle + 1;     k = start;       // 3가지의 경우중에 교차되는 경우먼저따져보자     while (i <= middle && j <= end) {              if (a[i] <= a[j]) {             sorted[k] = a[i];             i++;         }         else { //그 반대의 경우라면             sorted[k] = a[j];             j++;              }         k++;//정렬배열의 다음 칸에 담아야 하므로     }       //교차되는 경우가 아니라 특정 하나가 먼저 채워진다면?     if (i > middle) {// i가 먼저채워졌기때문에 middle보다 커진것         for (int t = j; t <= end; t++) {             sorted[k] = a[t];             k++;         }     }     else{ // j가 먼저채워졌기때문에              for (int t = i; t <= middle; t++) {                          sorted[k] = a[t];                          k++;                         }     }     //정렬된 배열을 삽입       for (int t = start; t <= end; t++) {         a[t] = sorted[t];                                         } }   void mergeSort(int a[], int start, int end) {       if (start < end) {         int middle;         middle = (start + end) / 2;         mergeSort(a, start, middle);         mergeSort(a, middle + 1, end);//계속 분할         merge(a, start, middle, end);       } }   int main() {     int array[number] = { 31,3,5,2,9,11,21,6 };     mergeSort(array, 0, number - 1);     for (int i= 0; i < number; i++) {         printf("%d ", array[i]);     } } Colored by Color Scripter

cs