병합 정렬(Merge Sort)은 효율적인 정렬 알고리즘 중 하나로, "분할 정복" 기법을 사용하여 데이터를 정렬합니다. 이 알고리즘은 안정적이며 평균 및 최악의 경우 시간 복잡도가 O(n log n)입니다. 아래는 병합 정렬의 원리와 구현 방법을 설명하겠습니다.
아래는 정복 알고리즘
정복 알고리즘(Divide and Conquer Algorithm)은 문제를 해결하는 방법 중 하나로, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 접근 방식입니다. 이 방식은 다음의 세 가지 주요 단계로 구성됩니다:
분할 (Divide): 주어진 문제를 여러 개의 하위 문제로 나눕니다. 이 하위 문제들은 원래 문제와 비슷하지만 크기가 더 작습니다.
정복 (Conquer): 나누어진 하위 문제를 재귀적으로 해결합니다. 만약 하위 문제가 작고 간단하면, 직접 해결합니다.
결합 (Combine): 해결된 하위 문제의 결과를 결합하여 원래 문제의 해결책을 만듭니다.
병합 정렬의 원리
- 분할: 주어진 배열을 두 개의 하위 배열로 나눕니다.
- 정렬: 각 하위 배열을 재귀적으로 병합 정렬을 사용하여 정렬합니다.
- 병합: 정렬된 두 하위 배열을 하나의 정렬된 배열로 병합합니다.
#include <iostream>
#include <vector>
using namespace std;
// 배열을 병합하는 함수
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 왼쪽 배열의 크기
int n2 = right - mid; // 오른쪽 배열의 크기
vector<int> L(n1);
vector<int> R(n2);
// 왼쪽 배열과 오른쪽 배열에 값 복사
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 병합
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 남은 요소들 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 병합 정렬 함수
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 중간 인덱스 계산
// 분할
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 병합
merge(arr, left, mid, right);
}
}
// 메인 함수
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
int n = arr.size();
mergeSort(arr, 0, n - 1);
cout << "정렬된 배열: ";
for (int i : arr) {
cout << i << " ";
}
cout << endl;
return 0;
}
단계별 설명
배열의 크기가 1이 될 때까지 계속해서 배열을 반으로 나눕니다.
배열이 더 이상 나눌 수 없을 때, 정렬된 상태로 병합합니다.
병합할 때는 두 개의 배열을 비교하여 더 작은 값을 먼저 결과 배열에 추가합니다.
merge 함수: 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열로 만듭니다.
mergeSort 함수: 배열을 재귀적으로 분할하고, 각 하위 배열을 정렬한 후 병합합니다.
main 함수: 정렬할 배열을 정의하고 병합 정렬을 호출하여 결과를 출력합니다.
글쓴이 분석
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
int n = arr.size();
배열을 먼저 만들어주고 사이즈 체크
mergeSort(arr, 0, n - 1); 해당 함수로
mergeSort(vector<int>& arr, int left, int right)
매개변수로 정렬할 배열과 작은수 와 큰수
if (left < right) {
int mid = left + (right - left) / 2; // 중간 인덱스 계산
이부분에서 좌측 보다 우측이 클경우
중간 지정
(왼쪽 + (오른쪽 - 왼쪽) / 2 // 0 + (6 - 0) / 2 = 3
예시 ) left : 2 / right 8
mid = 2 + (8 - 2 ) / 2 // 5
// 분할
1. mergeSort(arr, left, mid);
2. mergeSort(arr, mid + 1, right);
여기서 재귀로 분할 실시
1번 재귀 0 , 3
0 + ( 3 + 0) /2; // int 이므로 1
1-1 번 재귀 0, 1
0 + ( 1 + 0) /2; // int 이므로 0 조건 성립 안함 재귀 종료
//수학 계산오류 발생해서 수정 !!
1-2 번 재귀 0+ 1, 3
1 + (3 - 1) / 2 == 2
1- 2 - 1번 재귀 1 , 2
1< 2
1 + (2 - 1 ) / 2 == 1
1- 2- 1 -1 번 재귀 1, 1 // 1 < 1 성립 안됨 끝
1 -2 - 1- 2 번 재귀 2 , 2 // 또 성립 안됨
1-2-2 번 재귀 2+ 1 , 3 // 또 성립안됨
1-2-1 , 1- 2 , 1 번 순서로 정렬
병합 함수로 이동
merge(vector<int>& arr, int left, int mid, int right) {
매개변수로 함수와 왼쪽 중간 오른쪽값과 배열 전달
int n1 = mid - left + 1; // 왼쪽 배열의 크기
int n2 = right - mid; // 오른쪽 배열의 크기
배열의 크기 계산
n1 은 mid - left + 1;
1- 2 -1 를 예시로 하면 // 1 1 2
left : 1, mid :1 , rihgt : 2
n1 = 1;
n2 = 1
vector<int> L(n1);
vector<int> R(n2);
벡터를 왼쪽과 오른쪽으로 나누고 크기 맞춰줍니다.
// 왼쪽 배열과 오른쪽 배열에 값 복사
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
왼쪽 배열안에 값을 전달
L = { 27}
R = {43}
// 병합
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
i가 왼쪽 배열 보다 작고 j가 오른쪽 배열 크기보다 작을 때까지 반복문 실행
반복문에서 왼쪽 배열값과 오른쪽 배열 값 비교 시작
왼쪽이 더작거나 같으면 매개변수 배열 k값 (left == 1이였습니다.)
// 27 <= 43 인상황
arr[1] = L[0] ; // 27
i++ ; //i== 1;
k++;
조건 해당안됨
// 수정 반복문 조건 && 에서 둘다 해당해야 되는걸 잘못 분석했음
// i나 혹은 j가 범위 넘어가면 조건 해당안됨!! 종료임!!
// 남은 요소들 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
i나 j가 아직 n1 , n2보다 작을 경우 따로 정렬
이번에는 j가 0이니 시작 n2 ==1 , k == 2인상황
arr[2] = 43;
1-2 -1 끝
1 - 2번 이동
매개변수 받은 인덱스 1 2 3
n1 = 2
n2 = 1
L = { 38 , 27 }
R = {3 } // mid + 1 + j ; 2 + 1 + 0; == 3 ; arr[3] == 3;
38 <= 3
arr[0] = 3; // j == 1 ; j < n2 조건 성립하지않으므로 끝
K++;
k == 1
// 남은 요소들 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
arr[1] = 38;
arr[2] = 27;
여기까지보면 병합 정렬은
배열의 중간 인덱스를 지정하고 가장 작은 인덱스부터 가장 큰 인덱스까지의 값을 비교후 정렬 하는것을 알 수 있습니다.
더할 경우 너무 지저분해지니 변경이 어느방식으로 되는지만 이해했습니다.
나중에는 더 효과적으로 분석하는 법을 알아봐야겠습니다.
병합 정렬의 장점
효율성:
대량의 데이터에 대한 정렬에서 안정적인 성능을 보입니다. 특히, 데이터가 대용량일 때 효율적입니다.
안정성:
안정적인 정렬 알고리즘이므로, 데이터의 원래 순서를 유지해야 하는 경우 유용합니다.
재귀적 구현:
병합 정렬은 재귀적으로 구현할 수 있으며, 이로 인해 코드가 간결해질 수 있습니다.
외부 정렬:
데이터가 메모리에 모두 들어갈 수 없을 때(예: 대용량 파일), 외부 정렬에 적합한 알고리즘입니다. 예를 들어, 병합 정렬은 디스크 기반 데이터 정렬에 자주 사용됩니다.
병합 정렬의 단점
공간 복잡도:
추가적인 메모리 공간이 필요하므로, 메모리 사용량이 많습니다. 메모리가 제한된 환경에서는 부적합할 수 있습니다.
비교 기반:
병합 정렬은 비교 기반 정렬 알고리즘이므로, 최악의 경우 시간 복잡도가 O(n log n) 을 넘지 않습니다.
다른 비교 기반 정렬 알고리즘에 비해 성능이 떨어질 수 있습니다.
복잡한 구현:
다른 정렬 알고리즘에 비해 구현이 복잡할 수 있으며, 특히 재귀적 구조를 이해해야 합니다.
사용 예시
- 대량의 데이터 정렬: 대규모 데이터베이스에서 데이터를 정렬할 때.
- 정렬된 데이터를 유지해야 하는 경우: 예를 들어, 사용자 목록에서 동일한 사용자 정보를 가진 여러 항목을 정렬할 때.
- 외부 정렬: 디스크에 저장된 대용량 파일을 정렬할 때, 파일을 여러 조각으로 나누어 정렬한 후 병합하는 방식으로 사용됩니다.
효율성과 안정성 덕분에 다양한 상황에서 유용하게 사용된다고합니다.
글쓴이의 생각
직접 분석하면서 퀵 정렬이 좀 떠올랐습니다
퀵정렬은 값의 기준을 정하고 정렬이였고
병합 정렬은 요소들의 중간 위치를 찾고 거기서 정렬한다는 점이 있더군요
여기서 궁금한건 이렇게 여러번 정렬해서 오래 걸릴 것이라 예상했지만
시간 복잡도가 평균 최악 최선 모두 같다는 것은 상당히 매력적이라 느껴졌습니다만
아직 실력이 부족해서 왜 복잡도가 똑같은지 이해중입니다.
따로 조사한 것
이렇게 복잡하고 재귀를하는데 어떻게 시간복잡도가좋은건지
배열을 반으로 나눌 때마다, 문제의 크기가 절반으로 줄어듭니다. 이 과정은 배열의 크기가 1이 될 때까지 계속됩니다. 따라서 분할 단계에서의 연산 횟수는 O(logn)입니다.
시간복잡도 O(n log n)이게 무슨뜻인지
O(nlogn)=O(n)×O(logn)
이는 병합 정렬이 각 단계에서 O(n)의 작업을 수행하고,
이러한 단계가 O(logn) 번 반복된다는 것을 의미합니다.