합병(병합) 정렬(Merge Sort)
: 분할 정복 방법(큰 문제를 작은 문제 단위로 쪼개서 해결하고 병합하는 방식)을 통해 구현
: 원소를 쪼개고 나서(분할) 다시 합병시키면서(정복) 정렬해 나가는 방식
: 빠른 정렬
: Divid, Conquer and Combine
✓ 배열 A 가 있다고 가정 , 나누기를 시작할 인덱스 p, 마지막 인덱스 r (A[p..r])
✓ Divide (나누기, 큰 문제 → 작은 문제)
① q(p 와 r 사이의 수) 인덱스를 기준으로 배열을 2개로 나눈다. (A[p..q], A[q+1, r])
② 계속해서 나눠주다가(재귀) p == r 이 될 경우(base case) 배열의 크기가 1이 되므로 종료한다.
✓ Conquer (병합하기, 작은 문제 → 큰 문제)
① 크기가 1인 배열의 원소를 비교해 정렬해준다.
② 크기가 1 이상인 배열들의 원소를 서로 비교해 작은 값을 배열에 넣어준다. (길이가 긴 배열의 인덱스에 도달할 때까지)
③ 만약 정렬이 끝났다면(배열의 마지막까지 병합했다면) 빈 배열에 해당 배열을 복사해준다.
구현 코드
병합정렬은 2가지 메서드에 대해 알아야 한다.
✓ MergeSort : 주어진 배열을 작은 배열로 쪼개는 재귀메서드
✓ Merge : 쪼개진 배열을 다시 합하는 메서드 (⭐️⭐️⭐️)
→ MergeSort
// 매개변수 : arr(정렬할 배열), l(시작인덱스), r(마지막인덱스)
void mergeSort(int arr[], int l, int r) {
if (l < r) { // l이 r보다 크면 base case에 해당되므로 그렇지 않을 경우에만 케이스 진행
int m = (l + r) / 2; // 중간값
mergeSort(arr, l, m); // 중간값을 기준으로 왼쪽 배열
mergeSort(arr, m + 1, r); // 오른쪽 배열
merge(arr, l, m, r); // mergeSort 재귀문의 마지막에 merge가 호출
}
}
→ Merge
// 매개변수: arr(정렬할 배열), p(시작인덱스), q(중간 인덱스), r(마지막 인덱스)
void merge(int arr[], int p, int q, int r) {
// 분할된 두 배열을 담을 배열이 필요함
// L ← A[p..q] && M ← A[q+1..r]
int n1 = q - p + 1; // A[p..q] 배열 사이즈
int n2 = r - q; // A[q+1..r] 배열 사이즈
int L[n1], M[n2]; // 배열을 사이즈에 맞게 선언해주고 값을 삽입
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k; // 각각의 인덱스 선언
i = 0; // L을 순회할 인덱스
j = 0; // M을 순회할 인덱스
k = p; // L 의 시작 인덱스(L의 시작인덱스가 M의 시작인덱스보다 작으므로)
// arr에 삽입할 값의 인덱스
while (i < n1 && j < n2) { // L이나 M의 순회 인덱스가 배열 사이즈보다 작을 때만 반복문
if (L[i] <= M[j]) { // 만약 L의 원소가 더 작다면 arr의 k 번째 값에 삽입하고 i 증가
arr[k] = L[i];
i++;
} else { // 그렇지 않으면 M의 원소를 k번째 삽입하고 j 증가
arr[k] = M[j];
j++;
}
k++; // k는 무조건 값이 들어오므로 증가시켜줌
}
// L 배열의 원소가 남았을 경우
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// M 배열의 원소가 남았을 경우
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
복잡도
✅ 시간복잡도
병합 정렬의 시간 복잡도는 최악, 최선, 평균 모두 O(n*logn)이다.
n개의 데이터를 가지고 logn의 단계(절반씩 분할이 되기 때문에)를 거치기 때문이다.
단, 자바에서는 배열을 복사하는데 많은 시간이 걸려 생각보다 빠르지 않을 수 있다.
✅ 공간복잡도
O(n) → L, M 배열이 필요함