병합 정렬 구현 및 테스트

  병합 정렬 

입력 배열을 반으로 나누고 나눈 배열을 하나의 배열로 병합하여 정렬을 진행한다.

 

병합 정렬 알고리즘

배열의 크기를 반으로 나누는 과정을 각각의 크기가 1이 될 때까지 반복하고 이후 각각의 배열을 병합할 때 정렬을 진행한다.

 

병합 정렬 알고리즘

MergeSort(A[], p, r)
{
	if (p < r) then
	{
		q ← └(p + r) / 2┘
		MergeSort(A, p, q)
		MergeSort(A, q + 1, r)
		Merge(A, p, q, r)
	}
}

Merge(A[], p, q, r)
{
	정렬되어 있는 두 배열 A[p...q]와 A[q + 1...r]을 합쳐
		정렬 된 하나의 배열 A[p...r]을 만든다.
}

 

※ 병합 정렬 시 배열을 둘로 나누는 것을 반복할 때 logn, 배열을 다시 병합할 때 n 의 비교가 발생하여 시간 복잡도는 Ο(n²)이 된다.

 

병합 정렬 구현

배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다.

 

MergeSort.hpp

#pragma once
#include "../Common.h"

void MergeSort(int arr[], int tempArr[], int p, int r, bool printData = false, int n = 0);
void Merge(int arr[], int tempArr[], int p, int q, int r);

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="printData">중간 결과 출력 여부</param>
void MergeSort(int arr[], int n, bool printData = false)
{
	if (printData)
	{
		Common::PrintArray(arr, n);
	}

	int* tempArr = new int[n];

	MergeSort(arr, tempArr, 0, n, printData, n);

	delete[] tempArr;
}

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="tempArr">정렬 시 사용할 임시 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
/// <param name="printData">중간 결과 출력 여부</param>
/// <param name="n">배열의 길이</param>
void MergeSort(int arr[], int tempArr[], int p, int r, bool printData, int n)
{
	if (r - p <= 1)
	{
		return;
	}

	int q{ (p + r) / 2 };

	MergeSort(arr, tempArr, p, q, printData, n);
	MergeSort(arr, tempArr, q, r, printData, n);
	Merge(arr, tempArr, p, q, r);

	if (printData)
	{
		Common::PrintArray(arr, n);
	}
}

/// <summary>
/// 주어진 배열들을 병합한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="tempArr">정렬 시 사용할 임시 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="q">배열의 중간 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
void Merge(int arr[], int tempArr[], int p, int q, int r)
{
	int pi{ p }, qi{ q }, ti{ p };
	// 두 배열 비교하여 하나에 저장
	while (pi < q && qi < r)
	{
		if (arr[pi] < arr[qi])
		{
			tempArr[ti++] = arr[pi++];
		}
		else
		{
			tempArr[ti++] = arr[qi++];
		}
	}

	// 배열에 남은 값 처리
	while (pi < q)
	{
		tempArr[ti++] = arr[pi++];
	}
	while (qi < r)
	{
		tempArr[ti++] = arr[qi++];
	}

	for (int i = p; i < r; i++)
	{
		arr[i] = tempArr[i];
	}
}

 

arr = [ 10, 8, 6, 4, 2, 9, 7, 5, 3, 1 ], n = 10 을 입력하여 실행한 과정은 다음과 같다.

10 8 6 4 2 9 7 5 3 1
8 10 6 4 2 9 7 5 3 1
8 10 6 2 4 9 7 5 3 1
8 10 2 4 6 9 7 5 3 1
2 4 6 8 10 9 7 5 3 1
2 4 6 8 10 7 9 5 3 1
2 4 6 8 10 7 9 5 1 3
2 4 6 8 10 7 9 1 3 5
2 4 6 8 10 1 3 5 7 9
1 2 3 4 5 6 7 8 9 10

 

난수 1,000,000개에 대한 수행 시간은 다음과 같다.

total time is 0s ( 138ms )

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘