병합 정렬

 

다음 수를 오름차순 정렬하시오

>7 6 5 8 3 5 9 1

 

병합 정렬

시간복잡도

병합 정렬도 분할 정복 알고리즘이기에 퀵 정렬과 같이 시간복잡도가 O(N*logN)이다.

 

정렬 구조

일단 나누고 나중에 합쳐서 정렬하는 방식이다. 퀵 정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징을 가지고 있다. 이 특징이 단계의 크기를 logN이 되도록 만들어준다.

 

(S) | 7 | 6 | 5 | 8 | 3 | 5 | 9 | 1 |

(1) | 6 7 | 5 8 | 3 5 | 1 9|

(2) | 5 6 7 8 | 1 3 5 9|

(3) | 1 3 5 5 6 7 8 9 |

 

이런 방식이 N*logN을 만드는 원리가 무엇일까

 

먼저 너비는 숫자의 개수인 N(=8)이라고 할 수 있다. 하지마 세로는 3개이다 이때 log2N은 3이다.

 

따라서 반반씩 쪼개서 처리하면 데이터의 개수가 지수적으로 증가한다. 그러기에 작은 단계만 확인해도 전체 데이터를 확인할 수 있고 따라서 병합 정렬은 N*logN을 보장한다고 할 수 있다.

 

너비가 왜 N인지 궁금할 수 있다. 각 단계마다 비교해야 할 데이터 수가 N이라고 할 수 있다.

 

#include<bits/stdc++.h>
using namespace std;
int number = 8;
int sorted[8]; //정렬 배열은 반드시 전역 변수 

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) {
	if(m<n){
		int middle = (m+n)/2;
		mergeSort(a,m,middle);
		mergeSort(a,middle+1, n);
		merge(a,m,middle,n);
	}
}
int main()
{
	int arr[number] = {7,6,5,8,3,5,9,1};
	mergeSort(arr, 0 ,number-1);
	for(int i=0; i<number; i++)
		cout << arr[i] << ' ';
	return 0;
}