[개념] 병합정렬 / c / 제한시간 없음

▣ 문제

- N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 병합정렬입니다.

 

▣ 입력설명

- 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

▣ 출력설명

- 오름차순으로 정렬된 수열을 출력합니다.

 

▣ 입력 예시

8 7 6 3 1 5 2 4 8

 

▣ 출력 예시

1 2 3 4 5 6 7 8

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
int data[10], temp[10];

void divide(int lt, int 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]) temp[p3++] = data[p1++];
			else temp[p3++] = data[p2++];
		}
		while (p1 <= mid) temp[p3++] = data[p1++];
		while (p2 <= rt)temp[p3++] = data[p2++];
		for (int i = lt; i <= rt; i++) {
			data[i] = temp[i];
		}
	}
}

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

	return 0;
}

병합정렬이란 배열을 계속 2개씩 나눈후 최소단위에서 계산의 결과값을 합쳐서 원래 문제의 결과를 푸는 방법이다.

 

이 문제에서는 오름차순으로 정렬하는것을 예로 들었다.

 

이전에 푼 '두 배열 합치기'의 개념을 빌려다 푸는 방법이다.

 

https://chonstudyroom.tistory.com/19?category=972726     <참고>

 

우선 배열을 입력을 받는다.

 

이제 divide 함수에서 왼쪽(lt)과 오른쪽(rt)를 기준으로 절반씩 나누게 된다. 이를 계속 반복하면 다음과 같은 그림으로 나타난다. 

 

Divide(left,right)

그리고 p1,p2는 각각 data[ ] 의 lt, rt를 나타내는 포인터이고 p3는 temp[ ]의 포인터를 뜻한다.

 

정렬은 D(1,2) - D(3,4) - D(1,4) - D(5,6) - D(7,8) - D(5,8) - D(1,8)의 순서로 실행이 된다. (후위 순회)

 

병합정렬의 장점으로는 시간복잡도가 O(nlogn)으로 굉장히 효율적인 코드이다. 단점으로는 temp[ ]라는 공간을 차지하는 배열을 만들어야한다는 점이다.

 

이는 나중에 '연결리스트'로 구성하면 링크의 인덱스만 변경되어서 데이터의 이동이 무시된다는 점이다. (나중에 추가적인 설명필요할듯)

 

처음 코드를 짜는데 힘들긴하지만 퀵정렬보다 더 효율적인 코드이긴하다.

 

대표적인 정렬들의 시간복잡도표