합병 정렬(merge sort) C언어

1. 합병 정렬이란?

합병 정렬은 폰 노이만이 제안한 비교기반의 분할 정복 정렬 알고리즘이다. 또한 안정 정렬 중 하나로 속한다. 그리고 최악의 시간 복잡도와 최고의 시간 복잡도는 O(n log n)이다.

2. 실행 순서(오름 차순일때)

1. 배열의 길이가 1이 될 때까지 반으로 나눈다.

2. 그리고 분리된 배열의 좌우를 기준으로 각각의 값을 비교한다.

ex) 3과 4의 크기 비교를 한다. 결과 3 < 4

3. 오름 차순에 맞게 비교한 값을 작은 값부터 왼쪽으로 임시 배열에 저장한다.

4. 임시 배열에 저장한 값을 원래 배열에 저장한다.

이 4가지가 정렬이 다 될 때까지 실행이 되면 이렇게 된다.

 

3. 코드

#include <stdio.h>
 
void merge(int a[], int low, int mid, int hight)    //분리된 배열 정렬 및 병합 함수
{
	int b[6];
	int i = low;        //왼쪽 시작
	int j = mid + 1;    //오른쪽 시작
	int k = 0;          //배열 b의 인덱스 값
 
	while(i <= mid && j <= hight)
	{
		if(a[i] <= a[j])        //분리된 왼쪽 배열과 오른쪽 배열 비교
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}
	while(i <= mid)             //비교하지 않은 왼쪽 배열이 있다면 배열 b에 전부 채우기
		b[k++] = a[i++];
	while(j <= hight)           //비교하지 않은 오른쪽 배열이 있다면 배열 b에 전부 채우기
		b[k++] = a[j++];
	k--;
 
	while(k >= 0)               //배열 b 내용을 배열 a 내용에 덮어쓰기
	{
		a[low + k] = b[k];
		k--;
	}
}
void mergeSort(int a[], int low, int hight)    //배열의 요소를 분할하는 함수
{
 
	int mid;
	if(low < hight)
	{
		mid = (low + hight) / 2;
		mergeSort(a, low, mid);            //왼쪽 배열의 요소 분리
		mergeSort(a, mid + 1, hight);      //오른쪽 배열의 요소 분리
		merge(a, low, mid, hight);         //분리된 배열 정렬 및 병합 함수
	}
}
int main(void)
{
	int arr[6] = { 3, 4, 5, 2, 1, 6 };
	int i;
 
	mergeSort(arr, 0, 6 - 1);    //배열의 요소를 분할하는 함수
 
    for(i = 0; i < 6; i++)
		printf("%d ", arr[i]);
}

(실행)