C++ 병합 정렬(합병 정렬) - 정렬5

이 정렬 알고리즘은 대단하다

평균 O(nlogn)이 나오는 아주 대단한 정렬이라고 볼 수 있다.

병합 정렬.

나는 비록 합병 정렬이라고 부르지만.

 

아무튼 이 대단한 합병 정렬은 분할 정복법의 교과서 같은 알고리즘이라고 볼 수 있다

병합 정렬의 아이디어는

1. 배열의 모든 원소를 분할 시킨다

2. 분할된 모든 원소를 합병하면서 정렬한다

 

합병 정렬에서 합병은 실제 정렬이 일어나는 부분이다

1. i, j 로 합병할 두 배열의 첫원소를 가르킨다 (이때 두 배열 이미 정렬이 되어있는 상태이다)

2. i와 j를 비교하여 더 작은 원소를 sorted 배열에 추가하고 + 1을 해준다

3. i 또는 j가 합병할 배열의 끝에 도달했다면

4. 나머지들을 sorted 배열에 추가한다

5. 마지막으로 sorted 배열의 내용물을 arr에 넣는다.

 

아주 간단하다.

int* Merge(int* arr, int start, int middle, int end){
    int i = start, j = middle+1, k = 0;
    int sorted[end-start+1];
    while(i <= middle && j <= end){
        if(arr[i] <= arr[j]){
            sorted[k] = arr[i];
            i++; 
        }
        else{
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }
    if(i > middle){  
        while(j <= end){
            sorted[k] = arr[j];
            k++;j++;
        } 
    }
    else{
        while(i <= middle){
            sorted[k] = arr[i];
            k++;i++;
        } 
    }
    for(int l=start; l<=end; l++){
        arr[l] = sorted[l-start];
    }
    return arr;
}

int* MergeSort(int* arr, int start, int end){
    if(start < end){
        int middle = (start + end) / 2;
        MergeSort(arr, start, middle);
        MergeSort(arr, middle+1, end);
        Merge(arr, start, middle, end);
    }
    return arr;
}

저번 퀵정렬에서 나온 설명이지만

7, 8, 4, 3, 2, 1, 5, 6을 정렬 한다면

O(n²)의 시간 복잡도를 가진 선택, 버블, 삽입 정렬의 경우

8 * 8 = 64의 시간 복잡도를 가지지만

 

이 두 배열을

7, 8 | 4, 3 | 2, 1 | 그리고 5, 6으로 갈라 정렬을 한다면

2*2 + 2*2 + 2*2 + 2*2 = 16

모두 합하여 정렬을 한다면 N의 시간을 소요하여

16 + 8 = 24 즉 nlogn = 8*log₂8 = 24

총 24의 시간 복잡도를 가진다 

 

이때 퀵정렬의 경우 피봇이 거지같이 선정될 수 있는 가능성 때문에

O(nlogn)를 보장하지 못하지만

 

합병정렬의 경우 항상 반으로 나누기 때문에

O(nlogn)의 시간 복잡도를 보장한다.