[자료구조] 정렬 #4 - 합병정렬 (Merge Sort)

합병정렬이란?

: devide and conquer(분할 정복) 알고리즘 중 하나

 

분할 정복 알고리즘: 문제를 작은 두 개의 문제로 분할하고 각각 해결 한 후 결과를 모아서 원래 문제를 해결하는 방법

- devide : 입력 배열을 같은 크기의 두 개의 배열로 분할

- conquer : 부분 배열 정렬

- combine : 정렬된 부분 배열들을 합병

 

* 레코드를 linked list로 구성하면 index만 변경되어 데이터 이동이 적다.

 

시간복잡도: O(nlogn)

 

구현 (오름차순)

void merge(int a[], int left, int mid, int right){
	int temp[MAX_SIZE]; //레코드를 배열로 구성하면 임시배열 필요
    
    for(int i=left; i<=right; i++){
    	temp[i] = a[i];
    }
    
    int i = left; // 왼쪽 배열 시작점
    int j = mid + 1; // 오른쪽 배열 시작점
    int k = left; //정렬될 배열의 index 시작점
    
    while(i<=mid && j<=right){
    	if(temp[i] <= temp[j])
        	a[k++] = temp[i++];
        else
        	a[k++] = temp[j++];
    }
    while(i<=mid)
    	a[k++] = temp[i++];
    while(j<=right)
    	a[k++] = temp[j++];
}

void mergeSort(int a[], int left, int right) {
    if(left == right){
    	return;
    }
    
    int mid = (left + right)/2; //분할(devide)
    mergeSort(a, left, mid); // 왼쪽 정렬
    mergeSort(a, mid+1, right); // 오른쪽 정렬
    merge(a,left, mid, right); // 합병
}

int main(){
	v = [1,2,3,4,5,6,7];
	mergesort(v,0,7);
    
    return 0;
}

 

출처

gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html