합병정렬 알고리즘

합병정렬 알고리즘은 퀵정렬과 마찬가지로 O(nlogn)의 시간복잡도를 가지며, 

방법은 퀵정렬과 반대되는 느낌으로 풀면 됩니다.

퀵정렬은 본래의 배열을 피벗에 의해서 나눈 뒤, 왼쪽 배열과 오른쪽 배열로 나눠서 

인덱스를 각각 구한 다음에, 피벗을 다시 설정하고 인덱스를 기준으로 초기의 배열을 재정의합니다.

재정의한 배열은 인덱스로, 왼쪽 배열과 오른쪽 배열로 각각 나누어 다시 QuickSorting을 진행합니다.(재귀적)

다음은 합병정렬입니다.

합병정렬은 하나의 배열을 중앙값(인덱스)으로 나눈 뒤에, 각각 재귀적으로 합병정렬을 진행합니다. 

아래 예시를 들어보겠습니다.

---

<원래의 배열>

1 5 3 4  2 7 8 9 

이 배열의 중앙을 반으로 나눕니다.

[1 5 3 4]   [2 7 8 9]

나눈 다음에 각각의 요소를 먼저 오름차순으로 나열합니다.

[1 3 4 5]   [2 7 8 9]

---

각 배열의 요소들을 하나씩 비교하면서 새로운 배열에 추가합니다.

추가된 배열은 다시 원래의 배열에 넣어 최종적으로 병합시킵니다.

이처럼, 각 배열을 왼쪽 배열과 오른쪽 배열로 나누어 합병정렬을 진행한 뒤, 하나의 배열로 합병시키고 

기존 배열을 재정의하면 됩니다.

MergeSort 함수 코드는 의외로 간단합니다. 

왼쪽 배열과 오른쪽 배열을 나누는 기준이 단순히 중앙에 위치한 값이며, 

이를 재귀적으로 호출만 하면 되기 때문입니다.

또한 시작요소와 마지막요소가 교차되기 시작할 지점이 기저조건 입니다.

간단히 생각해보면, 중앙값을 더이상 뽑아내지 못할 경우가 기저조건이라고 정의할 수 있기 때문입니다.

코드는 아래와 같습니다.

---

// arr 배열을 s1~e1 까지의 요소를 정렬하고 s2~e2 까지의 요소를 정렬한 뒤 

// 합병하는 함수입니다. 

// 퀵정렬도 마찬가지고, 구조가 배열을 나눠서 표현한다고해서 거창한 것이 아니라,

// 인덱스를 가지고 표현하는 것을 유념하시길 바랍니다.

void merging(int arr[],int s1,int e1,int s2,int e2){

int size = N; // 전역으로 선언된 변수

int temp[size];

int temp_inx = 0; // temp 배열의 인덱스

int p,q; 

// 이게 중요하다. 

// p는 명목상 왼쪽 배열의 요소들을 가리키는 인덱싱 포인터

// q는 명목상 오른쪽 배열의 요소들을 가리키는 인덱싱 포인터 

p = s1; // 각 배열의 첫 번째 요소를 잡는다.

q= s2;  // 각 배열의 첫 번째 요소를 잡는다.

// p는 인덱스를 가리키는 포인터이므로, 범위상 e1이 최대가 됩니다. 

// q 또한 e2가 최대이므로 범위 내에서만 비교 후 합병이 이루어지도록 구현합니다.

while(p <= e1 && q <= e2){

if(arr[p] >= arr[q]){

temp[temp_inx++] = arr[q];

q+=1;

} else {

temp[temp_inx++] = arr[p];

p+=1;

}

}

// 작은 요소들을 temp배열에 먼저 넣어주면서 각각의 인덱스를 옮겨준다.

// 위의 반복문이 깨지게 되는 것은 p또는q가 범위를 벗어난 것입니다.

if(p > e1){

//p 가 범위를 벗어난 경우

for(int i=q;i<=e2;i++){

temp[temp_inx++] = arr[i];

}

} else {

// q가 범위를 벗어나지 않았다면 p가 범위를 벗어난 것이다.

for(int i=p;i<=e1;i++){

temp[temp_inx++] = arr[i];

}

}

// 범위를 벗어난 남은 요소들은 그대로 temp 배열에 추가해야하기 때문입니다.

// 이제 temp 배열의 요소들을 arr 배열에 복사하여 재정의하면 됩니다.

// s1~e2까지의 배열 요소를 arr배열에 재정의하고, temp배열은 0부터 들어갔기 때문에

// i-s1으로 구현한 것입니다. 

for(int i=s1;i<=e2;i++){

arr[i] = temp[i-s1];

}

}

void mergeSort(int arr[] ,int s,int e){

// arr 배열을 s 인덱스 부터 e 인덱스까지 병합정렬하겠다.

if(s>=e)

return;

else{

int mid = (s+e)/2;

mergeSort(arr,s,mid);

mergeSort(arr,mid+1,e);

merging(arr,s,mid,mid+1,e);

}

}

---

합병정렬의 기본 개념은 인덱스를 가리키는 포인터들을 옮겨가면서 대소관계를 비교하고, 작은 값들을 먼저 

임시 배열에 추가한 뒤, 기존 배열을 재정의하는 것입니다.

이를 재귀적으로 구현하는 것이 핵심이며, 이 과정이 기저조건까지 진행된다면, 

결국 오름차순으로 정의된 하나의 온전한 배열이 반환될 것입니다.

전체 코드는 아래와 같습니다.

---

 

#include <stdio.h>

#include <cstdio>

// 배열 요소 정리 

// 합병정렬

/*

합병정렬

1. 왼쪽 배열을 구한다.  

2. 오른쪽 배열을 구한다.

3. 1과 2를 통해 왼쪽, 오른쪽 배열을 합친다. 

합칠 때에는 각 집합의 요소들을 하나씩 서로 비교하면서

최솟값을 먼저 출력할 수 있도록 한다.

기저 조건

: 합병할 배열을 만들기 위해 시작점과 끝점에 대해서 

반을 계속 나누면서 진행할 예정인데,

더이상 나눌 공간이 없을 경우

즉, 시작점이 끝점과 같을때 또는 클 때를 의미한다. 

*/ 

void merging(int arr[],int start1,int end1,int start2,int end2){

// arr 배열을 start1 ~ end1 (왼쪽 배열) 따로 정리 

// arr 배열을 start2 ~ end2 (오른쪽 배열) 따로 정리 

// 각각의 값들을 비교하면서 최소값을 먼저 변수에 넣어서 반환한다.

// 예시 

// 1 3 5 2   2 8 9 7 

// p         q

// (p는 start1 ~ end1으로 이루어진 배열의 인덱스)

// (q는 start2 ~ end2으로 이루어진 배열의 인덱스)

// p가 가리키는 값과 q가 가리키는 값을 비교해서 작은 것은 

// 다른 배열에 복사하여 넣고, 이동한 포인터 (p or q)는 다음 인덱스로 넘어간다.

// 다음 과정을 계속해서 반복하다가 범위를 벗어나는 경우가 생기면,

// 남은 포인터(p or q)의 값들을 순차적으로 넣어준다.

int p,q;

int temp[100]; // 배열 요소 복사

p = start1;

q = start2;

int temp_inx = 0;

while(p <= end1 && q <= end2){

if(arr[p] > arr[q]){

temp[temp_inx++] = arr[q];

q+=1;

} else {

temp[temp_inx++] = arr[p];

p+=1;

}

} 

if(p > end1){

// 왼쪽 배열이 범위를 벗어난 경우

for(int i=q;i<=end2;i++){

temp[temp_inx++] = arr[i];

} 

} else {

for(int i=p;i<=end1;i++){

temp[temp_inx++] = arr[i];

}

}

// temp안에 있는 내용을 arr에 복사해넣기

// arr은 start1~end2이지만 temp는 0부터 들어갔기 때문에  

for(int i=start1;i<=end2;i++){

arr[i] = temp[i-start1];

} 

}

void merge_sort(int arr[],int start,int end){

// 기저 조건은 앞서 말한대로 시작점이 끝점보다 크거나 같을 경우 

// 즉, 더이상 나눌 공간이 없을 경우 merge_sort는 반환한다.

if(start >= end)

return;

else{

// 왼쪽 배열 (처음부터 중간지점)

// 오른쪽 배열(중간지점+1 ~ 끝지점)

int mid = (start+end) / 2;

merge_sort(arr,start,mid);

merge_sort(arr,mid+1,end);

merging(arr,start,mid,mid+1,end); 

} 

}

int main(){

int n;

scanf("%d", &n);

int arr[100];

for(int i=0;i<n;i++)

scanf("%d",&arr[i]);

merge_sort(arr,0,n-1);

for(int i=0;i<n;i++)

printf("%d ",arr[i]);

}

---

감사합니다.