5. 병합 정렬

< 병합 정렬 >

: '분할 정복' 방법을 채택한 알고리즘이다.

: 시간복잡도 O ( N * logN ) 으로 보장이 된다.

: 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O ( N * logN ) 을 보장한다.

: 퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징이 있다. 

-> 반으로 나눈다는 특징이 단계의 크기가 logN이 되도록 만들어준다.

: 퀵 정렬보다 딱히 빠르진 않다. 하지만 시간 복잡도를 보장 할 수 있다는 것. 

: '기존의 데이터를 담을 추가적인 배열 공간이 필요하다'는 점에서 메모리 활용이 비효율적이라는 문제가 있다.

 

▼ 7 6 5 8 3 5 9 1 숫자들을 오름차순으로 정렬하는 코드

 

#include <stdio.h>
#include <stdlib.h>

int number =  8;
int sorted[8];   //정렬된 결과 배열을 담을 수 있는 공간 
				//정렬 배열은 반드시 전역 변수로 선언

/*merge 함수= 두개의 정렬된 부분 배열을 이용해서 
새롭게 정렬된 배열을 만들어내는 함수
m = 시작점, middle = 중간점, n = 끝점 */
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) {
	//크기가 1보다 큰 경우
	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 array[number] = {7, 6, 5, 8, 3, 5, 9, 1};

	mergeSort(array, 0, number - 1);

	for(int i = 0; i < number; i++) {
		printf("%d ", array[i]);
	}

}	

 

int sorted[8]; 에서 정렬 배열은 반드시 전역 변수로 선언하는 것이 중요!

 

 

 

 

[ 동빈나 유튜브 - 실전 알고리즘 강의 정리 ]