[기본문제풀이] merge_sort

 

풀이 일시 : 2020-07-30

​

병합정렬 :

합병정렬 또는 병합정렬로 불린다. O(N*logN) 보장한다. 분할정복 알고리즘의 하나이다.

-> middle을 기준으로 반으로 나눈다. (이를 재귀형식으로 계속 나눈다.)

-> 나눈 것을 병합하며 정렬한다.

-> 병합하는 중 남은 데이터들이 있다면 나머지를 다 넣어주는 과정이 필요하다.

​

문제 :

76584591 을 오름차순으로 정렬하시오

​

 

#define number 8
#include<stdio.h>
int size;
int sorted[8];
int count = 0;

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]; //합쳐질 배열 저장공간 sorted
			i++; //i를 다음칸으로 옮긴다.
		}
		else {
			sorted[k] = a[j]; //sorted에 j값넣는다.
			j++; //j도 다음칸으로 옮긴다.
		}
		k++; //k를 증가하면서 sorted배열을 완성해나가는거
	}
	//남은 데이터들도 삽입 (한쪽만 다 비었다면=범위넘었다면)
	if (i > middle) { //i가 초과라면 j를 넣어줘야겠지
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else { //j가 초과라면 i를 넣어줘야겠지
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	//정렬된 배열을 다시 a[]에 삽입
	for (int t = m; t <= n; t++) {
		a[t] = sorted[t]; //sorted만들고 a배열 도출
	}
}

void mergeSort(int a[],int m,int n) { 
	if (m < n) {
		int middle = (m + n) / 2; //나눠주어 middle을 생성
		mergeSort(a, m, middle); //앞 부분 재귀
		mergeSort(a, middle + 1, n); //뒷 부분 재귀
		merge(a, m, middle, n); //정렬한 후 merge를 수행한다.
		//어떻게 sort를 수행하나면 끝까지 mergeSort로 쪼개면
		//merge 부분에서 1 : 1 를 비교하게 됨
		//a[i] <= a[j] 를 따지기 때문에 sort가 된다.
	}
}

int main() {
	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]);
	}
}