퀵정렬 처럼, 합병정렬은 분할 정복 알고리즘입니다.
주어진 배열을 두개로 나누고, 두개의 배열을 인자로 합병정렬 함수 호출을 합니다. 그리고 정렬된 두 배열을 병합합니다.
merge() 함수는 두개의 배열을 합병하는데 사용됩니다.
merge(arr, left, middle, right)은 arr[left ... middle]과 arr[middle+1 ... right]이 정렬되었다는 가정하에 두개의 서브배열을 합병합니다.
|
mergeSort(arr[], left, right) if( right > left) 1. 중간 지점을 찾아서 두개로 나눕니다. middle = (left+right)/2 2. 왼쪽 부분 배열로 mergeSort를 호출합니다. mergeSort(arr, left, middle) 3. 오른쪽 부분 배열로 mergeSort를 호출합니다. mergeSort(arr, middle+1, right) 4. 두개의 부분 배열을 합병합니다. merge(arr, left, middle, right) |
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
void printArray(int A[], int size);
//두개의 배열을 합병합니다.
//left~middle, middle+1~right 까지
void merge(int arr[], int left, int middle, int right)
{
int left_size = middle - left + 1;
int right_size = right - middle;
/* 임시 배열을 만듭니다. */
int Left[left_size], Right[right_size];
/* 왼쪽 오른쪽 배열에 값을 복사합니다. */
memcpy(Left, &arr[left], left_size*sizeof(int));
memcpy(Right, &arr[middle+1], right_size*sizeof(int));
/* Merge the temp arrays back into arr[l..r]*/
int i=0;
int j=0;
int k = left; // Initial index of merged subarray
// 둘다 합병이 끝나지 않은경우
while (i < left_size && j < right_size)
{
//작은 값을 먼저 넣는다.
if (Left[i] <= Right[j])
{
arr[k] = Left[i];
i++;
}
else
{
arr[k] = Right[j];
j++;
}
k++;
}
/* 왼쪽에 값이 남은경우 */
if(i < left_size)
{
memcpy(&arr[k], &Left[i], (left_size - i)*sizeof(Left[0]));
}
/* 오른쪽 배열에 값이 남은경우 */
if (j < right_size)
{ //인덱스 - 인덱스가 아닌 갯수에서 j를 빼는 거라 +1할 필요가 없다
memcpy(&arr[k], &Right[j], (right_size - j)*sizeof(Right[0]));
}
}
//정렬하려는 배열의 왼쪽, 오른쪽 인덱스를 넣어준다.
void mergeSort(int arr[], int left, int right)
{
if (left < right) //오른쪽 인덱스가 더 큰경우만 시행
{
//(left+right)/2랑 같으나 오버플로우를 막기
int middle = left+(right-left)/2;
//배열을 나누어 재귀함수 호출한다.
mergeSort(arr, left, middle);
mergeSort(arr, middle+1, right);
//나눈 배열들을 합병한다.
merge(arr, left, middle, right);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
cout<<A[i]<<" ";
cout<<endl;
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(int);
cout<<"Given array is"<<endl;
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout<<endl<<"Sorted array is"<<endl;
printArray(arr, arr_size);
return 0;
}
시간복잡도
O(n log(n))
제자리 정렬이 아니며, 안정정렬이다
"주어진 배열을 최대한으로 나눈 뒤 합병하면서 정렬시키는 방식이다."
'알고리즘 > 지식' 카테고리의 다른 글
| [정렬 알고리즘] 힙 정렬 (0) | 2020.03.04 |
|---|---|
| [정렬 알고리즘] 퀵 정렬 (0) | 2020.03.04 |
| [정렬 알고리즘] 삽입 정렬 (0) | 2020.03.03 |
| [정렬 알고리즘] 버블 정렬 (0) | 2020.03.03 |
| [정렬 알고리즘] 선택 정렬 (0) | 2020.03.02 |