병합 정렬(C언어)

병합 정렬이란?

병합 정렬은 간단히 말해서 배열을 더 이상 나눠지지 않을 때까지 배열의 인덱스를 나눈 다음에 인접한 두 개의

배열을 크기 순으로 정렬하며 다시 합치는 방법이다.

순서대로 나열하면

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

※ 병합 정렬 코드

#include<stdio.h>

int sorted[8]; // 결합에 사용할 배열

// 결합
void merge(int a[], int m, int mid, int n) { 
	int i = m; // 정렬할 배열 맨 앞 배열 인덱스 번호
	int j = mid + 1; // 정렬할 배열 중간 인덱스 번호
	int k = m; // sorted의 인덱스 번호

	while (i <= mid && j <= n) { // 크기가 작은 순으로 정렬
		if (a[i] < a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if (i > mid) { // while 문의 정렬이 끝나고 정렬해야 할 것이 남았을 때
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= mid; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	for (int t = m; t <= n; t++) { // 원래의 배열에 정렬한 배열을 옮겨 담기
		a[t] = sorted[t];
	}
}

// 분할
void merge_sort(int a[], int m, int n) {
	if (m < n) {
		int mid = (m + n) / 2; // 중간 기준으로 나누기 위함
		merge_sort(a, m, mid);
		merge_sort(a, mid + 1, n);
		merge(a, m, mid, n);
	}
	return;
}

int main() {
	int arr[8] = { 8, 2, 5, 1, 3, 7, 4, 6 };
	merge_sort(arr, 0, 8 - 1); // (정렬할 배열, 처음 인덱스, 마지막 인덱스)
	for (int i = 0; i < 8; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}