알고리즘 - 병합 정렬(Mearge Sort)

병합정렬

- '분할 정복' 방법을 채택한 알고리즘

- O(N * logN)의 시간 복잡도를 가진다.

- 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합친다. 

 

기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬한다

 

계속 반으로 나누어서 한 개씩 남을 때 까지 나눈다.

예를 들어 a = { 8, 3, 4, 5, 1, 3, 2, 5} 이란 배열이 있을 경우

반을 나눌 경우 8 3 4 5           1 3 2 5

또 나눌 경우 8 3       4 5       1 3      2 5

또 반을 나눌 경우 8     3     4     5     1     3     2    5     

한 개씩 남게된다.  다 나눴을 때 합치게 된다. 합치게 되는 과정은 보통 2의 배수만큼 합친다.

 

첫 번째 병합

첫 번째 합칠 때는 두 개씩 합치는데 합치면서 정렬을 하게 된다

8 3       4 5       1 3      2 5       8과 3비교, 4와 5비교, 1과 3비교, 2와 5비교

처음 합친 결과는 이렇다.

3 8       4 5       1 3      2 5 이런 모양이 나오게 된다.

이런 모양은 정렬이 되긴 되었는데 두 개씩 합쳤으니 두 개의 배열 안에서만 정렬이 된 것.

---

두 번쨰 병합

두 번째 병합에선 2의 배수만큼 합친다고 했으니 4 개씩 합치게 된다

 

첫 병합의 결과)

3 8       4 5       1 3      2 5 

 

두 번째 병합에선 3 8과 4 5를 비교해서 새로운 배열을 만든다. 또 1 3과 2 5를 비교해서 새로운 배열을 만든다 첫 번째 병합과 같이 이런 결과가 나온다.

 

두 번쨰 병합 결과)

3 4 5 8       1 2 3 5

---

세 번째 병합)

세 번째 병합에선 8개씩 합치게 된다.

두 번째 병합 결과 3 4 5 8       1 2 3 5 에서 

1 2 3 3 4 5 5 8이 된다.

 

---

시간 복잡도

N * logN이 되는 이유.

8     3     4     5     1     3     2    5 의 넓이 값은 N = 8이다

 

첫 번째 병합: 3 8       4 5       1 3      2 5

두 번째 병합: 3 4 5 8       1 2 3 5

세 번째 병합: 1 2 3 3 4 5 5 8

 

병합은 총 3회 발생했다. 고로 높이는 3이다. 그 이유는 log2의 8 = 3이기 때문이다.

1단계에서 처리하는 데이터의 개수: 2^1

2단계에서 처리하는 데이터의 개수: 2^2

3단계에서 처리하는 데이터의 개수: 2^3

 

지수적으로 증가하기 때문에 증가하는 폭이 굉장히 크다. 그렇기 때문에 단계를 조금만 내려가더라도 많은 데이터를 처리하게된다.

 

그렇기 때문에 높이는 logN이며 넓이는 N이기 때문에 병합정렬의 시간복잡도는 N*logN이다.

중요 한 점은 합치는 순간에 정렬을 수행한다.

---

소스코드

middle은 컴퓨터 메모리 상으론 붙어있고 단일의 주소다. 

m = 시작점

n = 끝점

void merge(int a[], int m, int middle, int n){

}

이제 변수를 설정해주는데 i와 j와 k를 설정한다. 

void merge(int a[], int m, int middle, int n){
    int i = m;
    int j = middle + 1;
    int k = m;
}

이 후에 작은 순서대로 배열에 삽입한다.

i는 middle까지 가게되고 j는  n까지 가게된다.

삽입하는 과정에서 i와 j를 비교해서 더 작은값을 k에 넣게된다.

i가 삽입되었다면 i를 증가, j가 삽입되었다면 j를 증가.

둘 중 한 수를 집어넣은 이후엔 k를 증가시켜준다.

void merge(int a[], int m, int middle, int n){
    int i = m;
    int j = middle + 1;
    int k = m;
    //작은 순서대로 배열에 삽입
    while (i <= middle && j <= n) {
        if(a[i] <= a[j]){
            a[k] = a[i];
            i++;
        }else{
            a[k] = a[j];
            j++;
        }
        k++;
    }
}

 

최종 소스코드.

//두개의 정렬된 부분 배열을 이용해서 새롭게 정렬된 배열을 만드는 함수.
void merge(int a[], int m, int middle, int n){
    int i = m;
    int j = middle + 1;
    int k = m;
    //작은 순서대로 배열에 삽입
    while (i <= middle && j <= n) {
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }else{
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    
    if(i > middle){                      //만약 i가 middle보다 크다면 i 가 먼저 끝난거기 때문에
        for (int t = j; t <= n ; t++) {  //남은 j값을 넣어준다. 비교는 필요하지 않다 이미 정렬된 데이터이기 때문
            sorted[k] = a[t];
            k++;
        }
    }else{                                //j가 먼저 끝났다면 남은 i값을 다넣어준다
        for (int t = i; t <= n; t++) {   //비교는 필요하지 않다 이미 정렬된 데이터이기 때문
            sorted[k] = a[t];
            k++;
        }
    }
    
    //정렬된 배열을 실제 배열에 삽입.
    for (int t = m; t <= n; t++) {
        a[t] = sorted[t];
    }
}

//일단 반으로 나누는 함수
//두 가지로 나뉜다는 점에서 재귀함수가 효율적.
//a[] = 정렬할 배열, m = 시작점, n = 끝점
void mergeSort(int a[], int m, int n){
    //크기가 1보다 큰 경우에서만 나눈다.
    //m이 n보다 작다는 것은 시작점과 끝점의 차이가 1 이상이라는 뜻.
    if(m < n){
        int middle = (m + n) / 2; // 시작점과 끝점을 더해서 나누면 정 중앙의 값.
        mergeSort(a, m, middle);  // 중앙을 기점으로 왼쪽으로 병합 정렬을 수행하고 !!m(시작점)부터 middle(중간)까지
        mergeSort(a, middle + 1, n); //중앙을 기점으로 오른쪽으로 병합 정렬을 수행함 !!중간부터 n(끝점)까지
        merge(a, m, middle, n);  // 정렬된 두 개의 배열을 나중에 합친다.
    }
}

동빈나님 영상으로 공부.