합병 정렬 / 병합 정렬(Merge Sort)

합병 정렬 / 병합 정렬

합병 정렬 / 병합 정렬(Merge Sort)은 정렬되지 않은 원소들을 하나의 원소로 분할한 다음 원소들을 정렬하면서 합병하는 알고리즘입니다.

먼저 원소들을 반복해서 분할해주면서 하나의 원소만 남을 때 까지 분할합니다.

그 다음에는 분할했던 두 원소들을 서로 합쳐주면서 정렬해줍니다.

이 과정을 반복해주면 정렬이 완료됩니다.

 

합병 정렬 / 병합 정렬 예시

 

 

합병 정렬 / 병합 정렬 C++ 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void Partition(int left, int right, int numbers[]);
void Merge(int left, int mid, int right, int numbers[]);
void MergeSort(int number, int numbers[]);
void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

	for (int i = 0; i < number; i++)
	{
		scanf("%d", &numbers[i]);
	}

	MergeSort(number, numbers);

	for (int i = 0; i < number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void MergeSort(int number, int numbers[])
{
	Partition(0, number - 1, numbers);
}

void Partition(int left, int right, int numbers[])
{
	int mid;

	if (left < right)
	{
		mid = (left + right) / 2;
		Partition(left, mid, numbers);
		Partition(mid + 1, right, numbers);
		Merge(left, mid, right, numbers);
	}
}

void Merge(int left, int mid, int right, int numbers[])
{
	int left_index = left;
	int right_index = mid + 1;
	int temp_index = 0;
	int temp[1000];

	memset(temp, 0, sizeof(temp));

	while (left_index <= mid && right_index <= right)
	{
		if (numbers[left_index] < numbers[right_index])
		{
			temp[temp_index] = numbers[left_index];
			left_index++;
		}
		else
		{
			temp[temp_index] = numbers[right_index];
			right_index++;
		}

		temp_index++;
	}

	if (left_index <= mid)
	{
		for (int i = left_index; i <= mid; i++)
		{
			temp[temp_index] = numbers[i];
			temp_index++;
		}
	}
	else
	{
		for (int i = right_index; i <= right; i++)
		{
			temp[temp_index] = numbers[i];
			temp_index++;
		}
	}

	temp_index = 0;

	for (int i = left; i <= right; i++)
	{
		numbers[i] = temp[temp_index];
		temp_index++;
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

합병 정렬 / 병합 정렬 시간복잡도

최선	평균	최악
nlog2n	nlog2n	nlog2n