[알골90제] 62번 - 병합정렬 : 분할정복 (복습필수ㅠㅠ)

- 32번 복습하기

- 분할정복?

https://kugistory.net/76

분할정복법 (Divide and Conquer)

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

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

*문제

병합정렬로 주어진 숫자들을 오름차순 하는 프로그램을 작성하세요.

 

*풀이

	//분할
	if (lt < rt) { //엇갈리면 멈춤
		mid = (lt + rt) / 2;
		divide(lt, mid);
		divide(mid+1, rt);
	}

 

 

- DFS: 후위순회이다! - 왼쪽 자식과 오른쪽 자식의 할일이 끝나면 루트를 한다.

 

// 62번 - 병합정렬 - 분할정복

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>

int data[10], tmp[10];

void divide(int lt, int rt) { //lt, rt는 우리가 정렬하고자 하는 범위

	int mid;
	int p1, p2, p3;

	//분할
	if (lt < rt) { //엇갈리면 멈춤

		mid = (lt + rt) / 2;
		divide(lt, mid);
		divide(mid + 1, rt);

		p1 = lt;
		p2 = mid + 1;
		p3 = lt;

		while (p1 <= mid && p2 <= rt) {
			if (data[p1] < data[p2]) tmp[p3++] = data[p1++];
			else tmp[p3++] = data[p2++];
		}
		while (p1 <= mid) tmp[p3++] = data[p1++];
		while (p2 <= rt) tmp[p3++] = data[p2++];

		for (int i = lt; i <= rt; i++) {
			data[i] = tmp[i];
		}
	}
}

int main() {

	int n, i;

	scanf("%d", &n);
	for (int i = 1; i <= n;i++)
		scanf("%d", &data[i]);

	divide(1, n);

	for (int i = 1; i <= n; i++)
		printf("%d ", data[i]);



}