(C/C++) 정렬 - 병합 정렬(Merge Sort) - 안정성 O, O(N log N)

안녕하세요.

오늘은 병합 정렬을 구현해보도록 하겠습니다.

 

1. 병합 정렬(Merge Sort)이란?

병합정렬은 배열을 나누고

나눈 부분들을 다시 하나로 만들때 순서대로 정렬하는 방법을 사용합니다.

아래 구현한 병합 정렬의 순서는 다음과 같습니다.

1) 1개의 크기를 가질때까지 배열을 반으로 나눕니다.

2) 두개의 부분을 정렬하여 새로운 임시배열에 넣습니다.

3) 임시 배열에 저장된 결과를 원래 배열에 복사합니다.

2), 3) 을 반복 하여 정렬을 완료 합니다.

 

2. 병합 정렬의 특징

안정성 O

O(N log N) 의 시간복잡도

 

정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

 

3. 병합 정렬의 구현

 

#include <iostream>
#include <stdio.h>

void MergeSort(int _arrays[], int left, int right)
{
	if (left < right)						//재귀 함수 종료 조건
	{
		int mid = (left + right) / 2;
		MergeSort(_arrays, left, mid);		//왼쪽 정렬
		MergeSort(_arrays, mid + 1, right);	//오른쪽 정렬
		Merge(_arrays, left, mid, right);	//병합
	}
}

void Merge(int _arrays[], int left, int mid, int right)
{
	int leftIndex = left;
	int rightIndex = mid + 1;

	int* sortArray = new int[right + 1];
	int sortIndex = left;

	while (leftIndex <= mid && rightIndex <= right)	//왼쪽 오른쪽 둘중 하나가 바닥 나기 전까지
	{
		if (_arrays[leftIndex] <= _arrays[rightIndex])
			sortArray[sortIndex++] = _arrays[leftIndex++];
		else
			sortArray[sortIndex++] = _arrays[rightIndex++];
	}

	if (leftIndex > mid) 	//왼쪽이 먼저 바닥나면 오른쪽 값을 넣어준다.
	{
		while (rightIndex <= right)
			sortArray[sortIndex++] = _arrays[rightIndex++];
	}
	else		//오른쪽 먼저 바닥나면 왼쪽 값을 넣어준다.
	{
		while (leftIndex <= mid)
			sortArray[sortIndex++] = _arrays[leftIndex++];
	}

	for (int i = left; i <= right; i++)	//배열 복사
		_arrays[i] = sortArray[i];

	delete[] sortArray;		//배열 삭제
}

 

 

왼쪽 혹은 오른쪽이 먼저 바닥날 경우를 위한 예외처리를 해두었습니다.

배열이기 때문에 임시배열을 필요로 하는데 연결리스트로 구현한다면 

추가적인 메모리 할당 없이 구현 할 수 있습니다.

감사합니다. 

 

다른 정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)