병합 정렬(Merge Sort)

Goal

      - Merge Sort 에 대해 설명할 수 있다.

      - Merge Sort 과정에 대해 설명할 수 있다.

      - Merge Sort를 구현할 수 있다.

      - Murge Sort의 시간 복잡도를 계산 할 수 있다.

---

1. Merge Sort Summary

   

     '반으로 쪼개고 나중에 합치기'           

시간 복잡도 O(N * logN)을 보장해줌

---

2. Merge Sort Processing

 

1. 작은 순서대로 배열에 삽입

2. 남은 데이터 삽입

3. 정렬된 배열을 삽입

---

3. Merge Sort Coding

#include <stdio.h>
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)
{
	//크기가 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] = {9, 1, 5, 8, 3, 4, 7, 2};
	mergeSort(array, 0, number -1);
	for(int i = 0 ; i < number; i++)
	{
		printf("%d ", array[i]);   //결과값 = 1, 2, 3, 4, 5, 7, 8, 9
	}
	return 0; 
}