자료구조 :: 병합정렬 Merge sort (c/c++ 구현)

병합정렬 (Merge sort)

 

병합정렬도 분할정복을 이용하기 때문에

퀵 정렬과 똑같이 O(N*logN)이다.

 

퀵정렬과 다르게 피봇값이 없다.

항상 반으로 나누기 때문에 logN을 보장한다. 

 

반으로 나눠서 나중에 합치면서 정렬을 하자.

 

 

#include <stdio.h>
 
int sorted[8]; // 정렬된 배열
 
void merge(int *data, int start, int mid, int end){
    int i = start;
    int j = mid+1;
    int k = start;
    
    while(i <= mid && j <= end)    {
        if(data[i] <= data[j]){
            sorted[k] = data[i];
            i++;
        }else{
            // data[i] > data[j]
            sorted[k] = data[j];
            j++;
        }
        k++;
    }
    if(i > mid){
        for(int t = j; t<=end; t++){
            sorted[k] = data[t];
            k++;
        }
    }else{
        for(int t = i; t<=mid; t++){
            sorted[k] = data[t];
            k++;
        }
    }
    
    // 정렬된 배열을 삽입
    for(int t=start; t<=end; t++){
        data[t] = sorted[t];
    } 
} 
 
void merge_sort(int *data, int start, int end){
    if(start < end){
        int mid = (start+end)/2;
        merge_sort(data, start, mid); // 좌측 정렬 
        merge_sort(data, mid+1, end); // 우측 정렬 
        merge(data, start, mid, end);
    }
}
 
int main(void){
 
    int data[8] = {3, 6, 7, 1, 2, 4, 8, 5};
    
    merge_sort(data, 0, 7);
    
    // 결과 확인
    for(int i=0; i<8; i++){
        printf("%d ", data[i]);
    } 
    return 0;
}​

 

 

병합정렬의 시간복잡도는 O( N * logN )

 

항상 절반씩 나눠서 실행하기 때문에

최악의 경우도 똑같이 O(N*logN)이다.

 

단점이라고 한다면, 정렬된 배열을 담을 임시 배열이 하나 더 필요하다.

그래서 메모리 공간을 조금 더 사용한다는 단점이 있다.

 

관련 글

2018/04/28 - [Algorithm] - 자료구조 :: 선택정렬 Selection sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

2018/04/29 - [Algorithm] - 자료구조 :: 힙 정렬 Heap sort (c/c++ 구현)

2018/04/30 - [Algorithm] - 자료구조 :: 계수정렬 Counting sort (c/c++ 구현)