<병합 정렬 구현>
[MergeSort.c]
/*
* 알고리즘 - 병합 정렬(Merge Sort)
* 파일명: MergeSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 병합 정렬 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
// 병합 과정
void MergeTwoArea(int arr[], int left, int mid, int right)
{
int front_Idx = left; // 첫 번째 인덱스(가장 왼쪽)
int rear_Idx = mid + 1; // mid(중간)의 바로 다음 -> 오른쪽의 맨 첫 번째 인덱스
int i;
int* sortArr = (int*)malloc(sizeof(int) * (right + 1)); // 정렬한 데이터를 담을 배열 동적 할당
int sort_Idx = left; // 동적 할당에 쓰일 첫 인덱스
// 첫 번째 인덱스가 mid와 같아지거나 (왼쪽에 나눈 배열의 끝까지 가는 경우)
// 오른쪽의 인덱스가 right와 같아지거나 (오른쪽에 나눈 배열의 끝까지 가는 경우)
while (front_Idx <= mid && rear_Idx <= right)
{
if (arr[front_Idx] <= arr[rear_Idx]) // 합쳐지기 전에 좌우에 나뉜 값에 대한 비교
sortArr[sort_Idx] = arr[front_Idx++];
else
sortArr[sort_Idx] = arr[rear_Idx++];
sort_Idx++;
}
// 병합 후 정렬이 끝나면
if (front_Idx > mid)
{
for (i = rear_Idx; i <= right; i++, sort_Idx++) // 오른쪽 부분을 채움
sortArr[sort_Idx] = arr[i];
}
else
{
for (i = front_Idx; i <= mid; i++, sort_Idx++) // 왼쪽 부분을 채움
sortArr[sort_Idx] = arr[i];
}
for (i = left; i <= right; i++)
arr[i] = sortArr[i]; // 원래 배열에 정렬된 값을 대입
free(sortArr); // 할당 해제
}
void MergeSort(int arr[], int left, int right)
{
int mid;
if (left < right)
{
// 중간 지점을 계산
mid = (left + right) / 2;
// 둘로 나눠서 정렬 (재귀)
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
// 정렬이 된 배열을 병합
MergeTwoArea(arr, left, mid, right);
}
}
int main()
{
int arr[7] = { 3, 2, 4, 1, 7, 6, 5 };
int i;
// 배열의 전체 영역을 정렬
MergeSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
for (i = 0; i < 7; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[병합 정렬의 이해]
병합 정렬은 분할 정복(Divide and Conquer)라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 기법이다.
분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할(divide)하여 정복(conquer)하는 방법이다.
단, 분할하여 정복한 후에는 결합(combine)하는 과정을 거쳐야 한다.
다음의 3단계를 거쳐 알고리즘을 디자인 하는 것이 분할 정복법이다.
1) 분할 (Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다.
2) 정복 (Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다.
3) 결합 (Combine) - 분할해서 해결한 결과를 결합하여 마무리한다.
병합 정렬은 위와 같은 방법을 근거로 다음과 같이 디자인되었다.
“8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고,
이걸 또 다시 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.”
그래서 병합 정렬은 데이터가 1개만 남을 때까지 분할을 해나간다.
데이터가 2개만 남아도 정렬을 해도 되지만, 데이터가 1개만 남으면 정렬을 할 필요가 없어지기 때문이다.
그래서 병합 정렬은 나누는 것이 핵심이 아니라, 병합되는 과정에서 정렬이 이뤄진다.
그렇기 때문에 ‘병합 정렬’이라는 이름이 붙은 것이다.
[성능 평가]
병합 정렬의 성능 평가는 비교연산의 횟수에 대해서는 MergeTwoArea 함수를 기준으로 한다.
병합 과정에서 정렬을 하게 되므로 여기서 비교 연산이 이뤄지기 때문이다.
그리고 데이터의 수에 따라서 진행하는 비교 연산의 횟수는 $log_2n$이다.
데이터의 수가 $n$개라고 하면 비교연산에 대한 빅-오는 $O(nlog_2n)$ 이 된다.
이동 연산의 경우, 위 코드를 기준으로 하면 크게 임시 배열에 데이터를 병합하는 과정에서 한 번.
그리고 마지막에 임시 배열에 저장된 데이터 전체를 원래 배열에 옮기는 데 한 번 발생한다.
그래서 이동 횟수는 최악, 평균, 최선의 경우와 상관 없이 $2nlog_2n$만큼 수행하게 된다.
그러므로 이동연산에 대한 빅-오는 $O(log_2n)$이 된다.
<병합 정렬 구현>
[MergeSort.c]
/*
* 알고리즘 - 병합 정렬(Merge Sort)
* 파일명: MergeSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 병합 정렬 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
// 병합 과정
void MergeTwoArea(int arr[], int left, int mid, int right)
{
int front_Idx = left; // 첫 번째 인덱스(가장 왼쪽)
int rear_Idx = mid + 1; // mid(중간)의 바로 다음 -> 오른쪽의 맨 첫 번째 인덱스
int i;
int* sortArr = (int*)malloc(sizeof(int) * (right + 1)); // 정렬한 데이터를 담을 배열 동적 할당
int sort_Idx = left; // 동적 할당에 쓰일 첫 인덱스
// 첫 번째 인덱스가 mid와 같아지거나 (왼쪽에 나눈 배열의 끝까지 가는 경우)
// 오른쪽의 인덱스가 right와 같아지거나 (오른쪽에 나눈 배열의 끝까지 가는 경우)
while (front_Idx <= mid && rear_Idx <= right)
{
if (arr[front_Idx] <= arr[rear_Idx]) // 합쳐지기 전에 좌우에 나뉜 값에 대한 비교
sortArr[sort_Idx] = arr[front_Idx++];
else
sortArr[sort_Idx] = arr[rear_Idx++];
sort_Idx++;
}
// 병합 후 정렬이 끝나면
if (front_Idx > mid)
{
for (i = rear_Idx; i <= right; i++, sort_Idx++) // 오른쪽 부분을 채움
sortArr[sort_Idx] = arr[i];
}
else
{
for (i = front_Idx; i <= mid; i++, sort_Idx++) // 왼쪽 부분을 채움
sortArr[sort_Idx] = arr[i];
}
for (i = left; i <= right; i++)
arr[i] = sortArr[i]; // 원래 배열에 정렬된 값을 대입
free(sortArr); // 할당 해제
}
void MergeSort(int arr[], int left, int right)
{
int mid;
if (left < right)
{
// 중간 지점을 계산
mid = (left + right) / 2;
// 둘로 나눠서 정렬 (재귀)
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
// 정렬이 된 배열을 병합
MergeTwoArea(arr, left, mid, right);
}
}
int main()
{
int arr[7] = { 3, 2, 4, 1, 7, 6, 5 };
int i;
// 배열의 전체 영역을 정렬
MergeSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);
for (i = 0; i < 7; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[병합 정렬의 이해]
병합 정렬은 분할 정복(Divide and Conquer)라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 기법이다.
분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할(divide)하여 정복(conquer)하는 방법이다.
단, 분할하여 정복한 후에는 결합(combine)하는 과정을 거쳐야 한다.
다음의 3단계를 거쳐 알고리즘을 디자인 하는 것이 분할 정복법이다.
1) 분할 (Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다.
2) 정복 (Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다.
3) 결합 (Combine) - 분할해서 해결한 결과를 결합하여 마무리한다.
병합 정렬은 위와 같은 방법을 근거로 다음과 같이 디자인되었다.
“8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고,
이걸 또 다시 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.”
그래서 병합 정렬은 데이터가 1개만 남을 때까지 분할을 해나간다.
데이터가 2개만 남아도 정렬을 해도 되지만, 데이터가 1개만 남으면 정렬을 할 필요가 없어지기 때문이다.
그래서 병합 정렬은 나누는 것이 핵심이 아니라, 병합되는 과정에서 정렬이 이뤄진다.
그렇기 때문에 ‘병합 정렬’이라는 이름이 붙은 것이다.
[성능 평가]
병합 정렬의 성능 평가는 비교연산의 횟수에 대해서는 MergeTwoArea 함수를 기준으로 한다.
병합 과정에서 정렬을 하게 되므로 여기서 비교 연산이 이뤄지기 때문이다.
그리고 데이터의 수에 따라서 진행하는 비교 연산의 횟수는 $log_2n$이다.
데이터의 수가 $n$개라고 하면 비교연산에 대한 빅-오는 $O(nlog_2n)$ 이 된다.
이동 연산의 경우, 위 코드를 기준으로 하면 크게 임시 배열에 데이터를 병합하는 과정에서 한 번.
그리고 마지막에 임시 배열에 저장된 데이터 전체를 원래 배열에 옮기는 데 한 번 발생한다.
그래서 이동 횟수는 최악, 평균, 최선의 경우와 상관 없이 $2nlog_2n$만큼 수행하게 된다.
그러므로 이동연산에 대한 빅-오는 $O(log_2n)$이 된다.
