병합정렬은 분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘입니다
병합 정렬의 시간복잡도는 O(NlogN) 입니다
시간복잡도
위 그림의 숫자 개수는 8개 입니다
병합정렬이 시간복잡도가 O(NlogN)인 이유는
3번의 병합만에 결과가 나왔는데 여기서 3번은 총 병합횟수이며 logN에서 log8 = 3이기 때문입니다 (시간복잡도의 log의 밑은 2로 가정합니다)
1회 병합시 N번만큼 데이터에 대해 접근 및 연산을 해야하기 때문에 8번만큼 데이터에 접근을 해야 합니다
즉, O(NlogN) 의 시간복잡도가 발생합니다
여기서 저 숫자들이 어떻게 저렇게 정렬이 될 수 있을까요 ?
가장 작은 데이터의 집합(1개 숫자는 1개의 집합)으로 분할을 진행합니다
그리고 다시 인접한 양측의 숫자들을 1개의 집합으로 묶습니다
이때 묶는 행위를 병합 이라고 합니다
또한 값을 서로 비교하여 작은 값이 왼쪽으로 오도록 합니다
집합의 원소가 1개일때는 비교대상이 1개밖에 없으므로 포인터의 의미가 없지만, 2개 이상일 경우 어떤것을 비교해야할지 정해야 하므로 포인터의 개념이 활용됩니다
각 집합에 포인터(인덱스)를 두어 포인터가 가르키는 위치의 값들을 서로 비교하여 작은 값을 다음 집합의 원소 가장 왼쪽부터 차례대로 넣습니다
아래 2개의 그룹을 병합하는 과정에서 더 자세하게 설명하도록 하겠습니다
핵심원리
병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장합니다
특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야합니다
2개의 그룹을 병합하는 과정
투 포인터 사용
두 집합의 특정 인덱스 값을 비교하여 작은 값을 결과 배열에 추가하고 해당하는 집합의 포인터를 오른쪽으로 1칸 이동시킵니다. 이 방식은 여러 문제에서 응용하므로 반드시 숙지하는 것이 좋습니다
병합을 할때에는 이전의 연산과정을 통해 이미 정렬된 집합들 이므로 각 집합의 첫 인덱스부터 시작하여 양측의 값들을 서로 비교하며 작은 값을 최종 집합에 순차적으로 넣을 수 있습니다
아래 사진은 가장 마지막의 병합과정을 자세하게 나타낸 그림입니다
- 첫번째 loop에서 24와 5를 비교합니다
- 5가 작으니 5를 최종 집합에 넣어줍니다
- 선택된 집합의 인덱스를 1칸 늘려줍니다
- 24는 선택되지 않았으므로 재비교합니다
- 두번째 loop에서 24와 15를 비교합니다
- 15가 작으니 15를 최종집합에 넣어줍니다
- 선택된 집합의 인덱스를 1칸 늘려줍니다
- 이번에도 24는 선택되지 않았으므로 인덱스를 늘리지 않습니다
- 세번째 loop에서 24와 45를 비교합니다
- 24가 작으니 24를 최종 집합에 넣어줍니다
- 선택된 집합의 인덱스를 1칸 늘려줍니다
- 이번에는 24가 선택되었으므로 인덱스를 늘려주어 다음번에는 32가 비교대상이 됩니다
- 위를 각 각 집합의 원소가 모두 선택될때까지 반복합니다
- 만약 한쪽의 집합의 원소가 모두 선택될 경우 나머지 집합의 원소들은 순차적으로 들어가게 된다
다시 한 번 시간복잡도를 생각해보면
위와 같이 병합하는 과정에서 각 집합에서 데이터를 N/2 번만큼 접근하고 이를 2개의 집합에 대해 접근하므로 총 N번 데이터접근이 발생하고 이 병합과정을 logN번 만큼 수행하므로
총 시간복잡도는 NlogN이 발생합니다
병합정렬 응용
투포인터를 사용
위 상황을 자동차 경주라고 가정해보자
- 숫자가 낮을 수록 속도가 빠르며, 무한대의 가까운 시간이 주어졌을때 최종 순위를 나타낸다고 하면 몇번의 순위에 역전이 일어났는가 ?
첫번째 loop 와 두번째 loop에서 총 4번의 역전이 일어나고
마지막 45가 최종 집합에 들어갈때 1번의 역전이 발생하여
총 9번의 역전이 일어난다
여기서 포인트는 “역전” 의 의미이다
역전이 의미하는 것은 정렬을 위한 1번의 swap()이 발생한 것과 같다
merge sort() 에서 첫번째 loop에서 5라는 숫자가 맨 처음 오는것이 매우 단순 비교 연산처럼 보이지만 숨은 의미로는 4번의 swap() 이 발생한 것과 동일한 의미로 해석할 수 있다
병합정렬 구현
package org.example;
public class MergeSort {
private static int[] sorted;
public static void merge_sort(int[] a) {
sorted = new int[a.length];
merge_sort(a, 0, a.length - 1);
sorted = null;
}
private static void merge_sort(int[] a, int left, int right) {
/*
* left == right 즉, 부분리스트가 1개의 원소만 갖고 있는 경우
* 더이상 나눌 수 없으므로 return 한다
*/
if (left == right) {
return;
}
int mid = (left + right) / 2; // 절반 위치
merge_sort(a, left, mid); // 절반 중 왼쪽 부분 리스트 (left ~ mid)
merge_sort(a, mid + 1, right); // 절반 중 오른쪽 부분 리스트 (mid + 1 ~ right)
merge(a, left, mid, right); // 병합 작업
}
private static void merge(int[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분 리스트 시작점
int r = mid + 1; // 오른쪽 부분 리스트 시작점
int idx = left; // 채워넣을 배열의 인덱스
while (l <= mid && r <= right) {
/**
* 왼쪽 부분 리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
* 왼쪽의 1번째 원소를 새 배열에 넣고 1과 idx를 1 증가시킨다
*/
if (a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
/**
* 오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
* 오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1증가 시킨다
*/
else {
sorted[idx] = a[r];
idx++;
r++;
}
}
/**
* 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
* 오른쪽 부분리스트 원소가 아직 남아있을때
* 오른쪽 부분리스트의 나머지 원소들을 새 배열에 비교하지 않고 바로 채워준다
* 이미 정렬이 되어있으므로
*/
if ((l > mid)) {
while (r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
}
/**
* 위와 마찬가지로 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
* 왼쪽 부분리스트 원소가 아직 남아있을때
* 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다
*/
else {
while (l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
/**
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다
*/
for (int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
}
참고
