백준 알고리즘 2751번: 수 정렬하기 2 C언어 합병 정렬(merge sort)

문제 출처: https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

1. 코드

#include <stdio.h>

void merge(int a[], int low, int mid, int hight)    //분리된 배열 정렬 및 병합 함수
{
	int b[1000000];
	int i = low;        //왼쪽 시작
	int j = mid + 1;    //오른쪽 시작
	int k = 0;          //배열 b의 인덱스 값
	
	while(i <= mid && j <= hight)
	{
		if(a[i] <= a[j])        //분리된 왼쪽 배열과 오른쪽 배열 비교
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}
	while(i <= mid)             //비교하지 않은 왼쪽 배열이 있다면 배열 b에 전부 채우기
		b[k++] = a[i++];
	while(j <= hight)           //비교하지 않은 오른쪽 배열이 있다면 배열 b에 전부 채우기
		b[k++] = a[j++];
	k--;
    
	while(k >= 0)               //배열 b 내용을 배열 a 내용에 덮어쓰기
	{
		a[low + k] = b[k];
		k--;
	}
}
void mergeSort(int a[], int low, int hight)    //배열의 요소를 분할하는 함수
{
	
	int mid;
	if(low < hight)
	{
		mid = (low + hight) / 2;
		mergeSort(a, low, mid);            //왼쪽 배열의 요소 분리
		mergeSort(a, mid + 1, hight);      //오른쪽 배열의 요소 분리
		merge(a, low, mid, hight);         //분리된 배열 정렬 및 병합 함수
	}
}
int main(void)
{
	int arr[1000000];
	int i, cnt;        //cnt : 입력 횟수
	
	scanf("%d", &cnt);
	
	for(i = 0 ; i < cnt; i++)
		scanf("%d", &arr[i]);
    
	mergeSort(arr, 0, cnt - 1);    //배열의 요소를 분할하는 함수
	
    for(i = 0; i < cnt; i++)
		printf("%d ", arr[i]);
}

(실행)

2. 문제 해결 방식

이 문제는 합병 정렬(merge sort)를 이용하여 문제를 해결했다. 합병 정렬을 이용한 이유는 최고의 속도와 최악의 속도가 O(n log n)이기에 이용하였고, 백준에서도 합병 정렬과 힙 정렬을 이용하여 해결할 수 있다고 설명이 되어있기 때문이다.

합병 정렬의 간단하게 소개하면 배열의 요소를 최소한의 개수로 쪼개어 나눈 뒤 다시 원래대로 합칠 때 크기 비교를 한뒤 합치는 방식이다. 

출처: 위키 백과

반복적인 행위를 하기에 반복문보다는 재귀 함수로 돌리는 것이 보편적인 것 같다. 아마 이렇게만 쓰면 합병 정렬에 대해 이해가 잘 안되고 너무 길어지기 때문에 합병 정렬에 대한 자세한 설명은 따로 정리해서 올리도록 하겠다.

추가: travelerfootprint.tistory.com/83

합병 정렬(merge sort) C언어