병합정렬을 요약하면?
배열을 원소가 1개가 될 때 까지 계속 쪼갠다음 인접한 두 원소 덩어리씩 합치면서 정렬을 해나거는 정렬 알고리즘이며, 시간 복잡도는 N*log(N)이다.
병합정렬 과정?
1. 원소가 1개가 될 때 까지 계속 2등분 한다.
2. 2덩어리씩 묶어서 정렬한다.
3. 2번 과정을 모든 원소 덩어리들이 모두 합쳐질 때 까지 반복한다.
C언어로 표현해보자
1. 원소가 1개가 될 때 까지 계속 2등분 한다.
나중에 분리한 것 끼리 합친다는 의미에서 계속 2등분을 한다는 말을 사용한 것이지 결국 1개 단위로 쪼개지는거랑 마찬가지이기 때문에 배열을 입력받아서 저장하는것이랑 차이가 없다. 물론 길이는 정해져 있지 않기 때문에 맨 처음에 입력받은 길이를 이용해서 동적할당을 해줘야 한다.
int* nums;
int n;
scanf("%d", &n);
nums = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", nums + i);
}
2 & 3. 2덩어리씩 묶어서 정렬하는 과정을 반복한다.
합치고 정렬하는 과정을 반복하는 과정은 재귀함수를 통해 효과적으로 처리할 수 있을듯 하다. 더 자세한 규칙을 찾기 위해 이 단계를 세부적으로 뜯어보자
1,6,2,4를 병합 후 정렬하는 예시이다. 비록 숫자들은 모두 한 배열 안에 있지만, 시작 인덱스와 끝 인덱스를 정해준다면 한 덩어리처럼 사용할 수 있을 것이다.
최종 정렬된 원소들이 다른 공간으로 옮겨진다는 것을 이용해서 최종 정렬된 덩어리를 저장하는 배열을 하나 더 만들 것이고, 그리고 각 덩어리들은 이미 오름차순 정리가 완료되어있기 때문에 두 배열의 맨 앞 원소를 비교한 뒤 더 작은 숫자 원소를 병합될 배열의 뒤로 붙이는 과정을 반복하면 정렬이 가능할 것이다.
재귀함수를 이용하여 코드를 작성해보면
void sort(int* arr, int start, int end) {
if (start == end)
return; //만약 원소 개수가 1개면 return
sort(arr, start, start + (end - start) / 2);
sort(arr, start + 1 + (end - start) / 2, end);
int* arr2 = (int*)malloc(sizeof(int) * (end - start + 1)); //병합될 부분 동적할당
int index_a = start; //앞쪽 덩어리 index
int index_b = start + 1 + (end - start) / 2; //뒤쪽 덩어리 index
int chunk_size_a = (end - start) / 2 + 1; // 앞에부터 2개씩 그룹짓기 때문에 그룹에 들어가지 못하는 원소는 무조건 뒤에 있을 수 밖에 없음, 따라서 병합 시 원소의 개수가 홀수가 될 경우 앞쪽 그룹의 원소의 개수가 1개 더 많게 됨
int chunk_size_b = end - start + 1 - chunk_size_a;
for (int i = 0; i < chunk_size_a + chunk_size_b; i++) {
if (arr[index_a] < arr[index_b] && index_a < start + chunk_size_a || index_b >= start + 1 + (end - start) / 2 + chunk_size_b) {
//뒤쪽 덩어리가 모두 옮겨졌거나 앞쪽 덩어리의 맨 앞쪽 값이 더 작을 때
//앞쪽 덩어리 맨 앞쪽 원소를 옮김
//옮긴 이후 가리키는 인덱스 1 증가
arr2[i] = arr[index_a++];
}
else {
//그 외의 경우
//뒤쪽 덩어리 맨 앞쪽 원소를 옮김
//옮긴 이후 가리키는 인덱스 1 증가
arr2[i] = arr[index_b++];
}
}
patch(arr, arr2, start, end - start + 1); //병합된 원소를 원래 배열에 덮어쓰는 부분
}
여기에서 patch 함수는 직접 작성한 함수로 최종 배열된 원소를 원래 배열에 start 위치부터 (end - start + 1) 길이 만큼 덮어씌우는 함수이다.
void patch(int* orig, int* source, int start, int len) {
for (int i = start; i < start + len; i++) {
orig[i] = source[i - start];
}
}
main함수까지 이렇게 작성을 하면 병합 정렬을 통해 오름차순으로 정렬할 수 있다.
int main() {
int* nums;
int n;
scanf("%d", &n);
nums = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", nums + i);
}
sort(nums, 0, n-1); //인덱스 번호 0~n-1까지 정렬
for (int i = 0; i < n; i++) {
printf("%d\n", nums[i]);
}
}
최종 코드는 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
void patch(int* orig, int* source, int start, int len) {
for (int i = start; i < start + len; i++) {
orig[i] = source[i - start];
}
}
void sort(int* arr, int start, int end) {
if (start == end)
return; //만약 원소 개수가 1개면 return
sort(arr, start, start + (end - start) / 2);
sort(arr, start + 1 + (end - start) / 2, end);
int* arr2 = (int*)malloc(sizeof(int) * (end - start + 1)); //병합될 부분 동적할당
int index_a = start; //앞쪽 덩어리 index
int index_b = start + 1 + (end - start) / 2; //뒤쪽 덩어리 index
int chunk_size_a = (end - start) / 2 + 1; // 앞에부터 2개씩 그룹짓기 때문에 그룹에 들어가지 못하는 원소는 무조건 뒤에 있을 수 밖에 없음, 따라서 병합 시 원소의 개수가 홀수가 될 경우 앞쪽 그룹의 원소의 개수가 1개 더 많게 됨
int chunk_size_b = end - start + 1 - chunk_size_a;
for (int i = 0; i < chunk_size_a + chunk_size_b; i++) {
if (arr[index_a] < arr[index_b] && index_a < start + chunk_size_a || index_b >= start + 1 + (end - start) / 2 + chunk_size_b) {
//뒤쪽 덩어리가 모두 옮겨졌거나 앞쪽 덩어리의 맨 앞쪽 값이 더 작을 때
//앞쪽 덩어리 맨 앞쪽 원소를 옮김
//옮긴 이후 가리키는 인덱스 1 증가
arr2[i] = arr[index_a++];
}
else {
//그 외의 경우
//뒤쪽 덩어리 맨 앞쪽 원소를 옮김
//옮긴 이후 가리키는 인덱스 1 증가
arr2[i] = arr[index_b++];
}
}
patch(arr, arr2, start, end - start + 1); //병합된 원소를 원래 배열에 덮어쓰는 부분
}
int main() {
int* nums;
int n;
scanf("%d", &n);
nums = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", nums + i);
}
sort(nums, 0, n-1); //인덱스 번호 0~n-1까지 정렬
for (int i = 0; i < n; i++) {
printf("%d\n", nums[i]);
}
}
[예시 입력]
8
1
9
8
7
5
20
4
11
[출력 결과]
1
4
5
7
8
9
11
20
문제해결에 적용해보기
위의 코드를 그대로 작성하면 문제를 해결할 수 있다. 문제에서는 언어에 내장된 함수를 쓰라고 안내를 했지만 필자가 들어만 봤던 병합 정렬을 한번 직접 구현해 보고 싶어서 병합정렬로 해결하였다.
'알고리즘' 카테고리의 다른 글
| 모든 순열 구하기 (0) | 2022.03.06 |
|---|---|
| [C언어] 카운팅정렬 구현하기 (feat. 백준 10989번) (0) | 2022.02.28 |
