[알고리즘] 병합정렬(Merge sort)

알고리즘

 

병합정렬(Merge sort)

 

 

 

 

간단 요약

 

가정) Array[8]= { 20, 18, 50, 40, 9, 19, 5, 25 } 을 오름차순으로 정렬한다.

 

1. 배열을 반으로 분할

 

2. 반으로 나누어진 배열들을 다시 반으로 분할한다.

 

3. 각각의 배열의 인덱스가 하나만 남을 때까지 분할

 

4. 하나씩 남은 배열들을 빈배열에 오름차순으로 합친다.

 

-> 병합정렬은 이해하기 까다로울수 있다. 복잡하지만 이렇게 하는 이유는

시간복잡도를 줄이기 위해서 이다. 예를 들어 n*n 의 시간복잡도를 갖고 있다고 하자

10개 의 배열을 정렬하는데 걸리는 시간은 100 이된다.

하지만 반으로 쪼개서 5개씩 정렬후 합치는 작업을 한다면

25 + 25 = 50 이라는 시간이 걸린다. 이런 부분에서 분할정복이 강함을 알 수 있다.

 

 

상세 설명

 

 

병합 정렬은 분할, 정복, 결합 세단계의 과정을 거쳐서 완성된다.

분할 : 동등한 크기를 갖는 두개의 배열로 분할한다.

정복 : 각 배열의 크기가 더 이상 분할 할 수 없을 때 까지 함수를 재귀하여 분할을 반복한다.

결합 : 크기가 1인 배열들끼리 크기를 비교하여 작은 것부터 빈배열에 채워 넣는다.

 

 

 

 

< 주의 할점 >

 

1. merge sort 함수 안에서 자기 자신을 재귀적으로 부르는 작업이 필요하다.

-> merge sort 의 내부를 보면 처음에 가운데 값을 정하고 왼쪽배열에서 재귀 호출 , 오른쪽배열에서 재귀 호출, merge 순으로 진행이 된다. 따라서 첫번쨰 재귀호출이 반으로 쪼개진 왼쪽 배열에서 일어나고, 재귀 함수 내에서도 다시 왼쪽 배열이 먼저 호출이 된다.

따라서 위에 그림처럼 동시에 분할이 일어나지 않고 왼쪽 배열이 더 이상 분할이 안될때 까지 분할을 한 후에 순차적으로 올라가서 오른쪽을 분할 후 정복 하고 다시 위로 올라가서 오른쪽 배열의 왼쪽을 분할후 올라가서 오른쪽 분할 후 정복. 굉장히 복잡하지만 과정을 하나 하나 보자면 이런식이 될것이다.

 

병합정렬 부터는 작업의 순서가 눈에 잘 들어오지 않는다. 그래서 작업이 진행되는 순서를 하나하나 보여주는 사이트가 있다.

 

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

 

여기서 merge sort 를 클릭하면 된다.

 

 

2. merge sort 에서 결합과정에서 작은 수 부터 빈배열에 삽입하는 반복문을 작성하면 한쪽 배열의 삽입이 끝나면 반복문을 빠져나온다. 이때 남은 배열을 빈배열에 다시 삽입하는 조건문이 필요하다.

 

 

 

 

시간복잡도

 

 

 

 

 

 

코드

 

 

#include <iostream>
 
using namespace std;
 
int size;
int sorted[100]; // 결합할때 사용하는 빈배열이므로 전역변수로 선언 
int count = 0;
 
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) {
        for (int t = j; t <= n; t++) {
            sorted[k] = a[t];
            k++;
        }
    }
    else {
        for (int t = i; t <= middle; t++) {
            sorted[k] = a[t];
            k++;
        }
    }
    // 정렬이 끝난 배열을 원래 배열에 삽입
    for (int t = m; t <= n; t++) {
        a[t] = sorted[t];
    }
}
 
void mergeSort(int a[], int m, int n) {
    // m >= n : 크기가 1인 경우 정렬x
    if (m < n) {
        int middle = (m + n) / 2;
        mergeSort(a, m, middle);
        mergeSort(a, middle + 1, n);
        merge(a, m, middle, n);
    }
}
 
int main(void) {
    int N;
    cin >> N;
    int arr[100];
    int arr2[100];
    for (int i = 0; i < N; i++) {
        arr[i] = rand() % 100;
    }
    
    cout << "정렬 전  : ";
 
    for (int i = 0; i < N; i++) {
            cout << arr[i] << ' ';
        }
    cout << "\n";
    mergeSort(arr, 0, N - 1);
 
    cout << "정렬 후  : ";
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

출처 : https://terms.naver.com/entry.nhn?docId=2270437&cid=51173&categoryId=51173