[정렬 알고리즘] 합병 정렬

퀵정렬 처럼, 합병정렬은 분할 정복 알고리즘입니다.

주어진 배열을 두개로 나누고, 두개의 배열을 인자로 합병정렬 함수 호출을 합니다. 그리고 정렬된 두 배열을 병합합니다.

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))

 

제자리 정렬이 아니며, 안정정렬이다

 

"주어진 배열을 최대한으로 나눈 뒤 합병하면서 정렬시키는 방식이다."