병합 정렬 (Merge sort)
병합 정렬 (Merge Sort)
병합 정렬은 분할 정복 (divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도 평균값은 O(nlogn)이다.
그룹을 병합하는 방법은 투 포인터 개념을 사용하여 왼쪽 포인터와 오른쪽 포인터의 값을 비교하고 작은 값을 결과 배열에 추가한 후 포인터를 오른쪽으로 1칸 이동시키면 된다.
위의 예로 보면, [27, 38] 과 [10, 43] 을 병합해야 할 때 data 1 index와 data 2 index를 둔 후 index1은 첫 배열의 첫 번째 요소를, index2는 두 번째 배열의 첫 번째 요소를 가리킨 후 값을 비교한다. 27과 10중에 10이 더 작으므로 이를 새로운 배열의 첫 번째 값으로 저장하고 해당 인덱스 즉 index2를 하나 증가시킨다. 이는 43을 가리키게 되고, index1이 가리키는 27이 더 작으므로 다음 값으로 27이 넘어가며 index1++이 된다. 38이 43보다 작아 다음 값으로 배열에 들어가고 마지막으로 남은 하나의 값인 43이 자동으로 마지막에 저장된다. 그럼 결과는 10, 27, 38, 43 순서로 오름차순 정렬이 완료된다.
단점
- 병합 과정에서 새로운 배열이 필요하므로 추가적인 공간이 요구된다. O(n)
- 제자리 정렬 (in-place sorting, 추가적인 메모리 공간 없이 정렬 가능한 알고리즘)이 아니다.
장점
- 안정적인 정렬 방법. 데이터의 분포에 영향을 덜 받아 입력 데이터가 무엇이든 정렬 시간은 동일하다.
시간 복잡도 계산
각 합병 단계의 비교 연산이 n번, (가로) 순환 호출의 깊이가 logn이므로 이 둘을 곱한 nlogn이 시간 복잡도가 된다.
병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장한다. 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 한다.
[백준 2751번] 수 정렬하기 2
https://www.acmicpc.net/problem/2751
import java.io.*;
import java.util.*;
public class Main {
public static int[] arr, tmp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
tmp = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
mergeSort(1, N); // 합병 정렬
for (int i = 1; i <= N; i++) {
bw.write(arr[i] + "\n");
}
bw.flush();
bw.close();
}
private static void mergeSort(int s, int e) {
if(e-s < 1)
return;
int m = s + (e-s) / 2;
mergeSort(s, m);
mergeSort(m+1, e);
for (int i = s; i <= e; i++) {
tmp[i] = arr[i];
}
int k = s;
int index1 = s;
int index2 = m+1;
while(index1 <= m && index2 <= e) { // 두 그룹 병합
// 양쪽 그룹의 index가 가리키는 값을 비교해 더 작은 수를 선택해 배열에 저장하고, 선택된 데이터의 index 값 오른쪽으로 한 칸 이동하기
if(tmp[index1] > tmp[index2]) {
arr[k] = tmp[index2];
k++;
index2++;
} else {
arr[k] = tmp[index1];
k++;
index1++;
}
}
while(index1 <= m){ // 한쪽 그룹이 모두 선택된 후 남아 있는 값 정리
arr[k] = tmp[index1];
k++;
index1++;
}
while(index2 <= e) {
arr[k] = tmp[index2];
k++;
index2++;
}
}
}
위의 코드는 Top-Down 방식으로 재귀 함수를 이용한 풀이이다. 두 부분으로 짤라 들어가며 서브 문제를 해결하는 방식이 가장 일반적이다. 그러나 대부분의 경우 정렬 과정은 최대한 재귀는 피하여 구현해주는 것이 일반적이기 때문에 아래의 Bottom-Up 으로 구현하는 게 좋다.
public class Merge_Sort {
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;
}
// Bottom-Up 방식 구현
private static void merge_sort(int[] a, int left, int right) {
/*
* 1 - 2 - 4 - 8 - ... 식으로 1부터 서브리스트를 나누는 기준을 두 배씩 늘린다.
*/
for(int size = 1; size <= right; size += size) {
/*
* 두 부분리스트을 순서대로 병합해준다.
* 예로들어 현재 부분리스트의 크기가 1(size=1)일 때
* 왼쪽 부분리스트(low ~ mid)와 오른쪽 부분리스트(mid + 1 ~ high)를 생각하면
* 왼쪽 부분리스트는 low = mid = 0 이고,
* 오른쪽 부분리스트는 mid + 1부터 low + (2 * size) - 1 = 1 이 된다.
*
* 이 때 high가 배열의 인덱스를 넘어갈 수 있으므로 right와 둘 중 작은 값이
* 병합되도록 해야한다.
*/
for(int l = 0; l <= right - size; l += (2 * size)) {
int low = l;
int mid = l + size - 1;
int high = Math.min(l + (2 * size) - 1, right);
merge(a, low, mid, high); // 병합작업
}
}
}
/**
* 합칠 부분리스트는 a배열의 left ~ right 까지이다.
*
* @param a 정렬할 배열
* @param left 배열의 시작점
* @param mid 배열의 중간점
* @param 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) {
if(a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
else {
sorted[idx] = a[r];
idx++;
r++;
}
}
while(r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
while(l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
/*
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
*/
for(int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
}
병합하는 부분(merge())의 내용은 같다.
[백준 1517번] 버블 소트
https://www.acmicpc.net/problem/1517
N의 최대 범위가 500,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다. 이 문제는 버블 소트를 사용하면 제한 시간을 초과하므로 병합 정렬을 사용해야 한다. 병합 정렬에서 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있기 때문이다.
[24, 32, 42, 60]과 [5, 15, 45, 90]을 병합 정렬할 때, 뒤쪽 그룹의 5가 앞쪽 그룹의 24, 32, 42, 60 앞에 놓이는데 이는 버블 정렬에서 swap을 4번해야 볼 수 있는 효과이다. 마찬가지로 45는 60보다 앞에 놓이므로 버블 정렬에서 swap을 1번한 것과 동일하다. 이런 식으로 뒤의 원소가 앞의 원소보다 먼저 놓이게 될 때 이동하는 횟수만큼을 정답 변수에 더해주면 총 swap의 수를 구할 수 있다.
코드는 swap 횟수를 세기 위한 로직을 추가한 것만 제외하면 동일하다.
[정답]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1517_버블소트2 {
public static int[] A, tmp;
public static long result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
A = new int[N + 1];
tmp = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
result = 0;
merget_sort(1, N); //병합정렬 수행하기
System.out.println(result);
}
private static void merget_sort(int s, int e) {
if (e - s < 1)
return;
int m = s + (e - s) / 2;
//재귀함수 형태로 구현
merget_sort(s, m);
merget_sort(m + 1, e);
for (int i = s; i <= e; i++) {
tmp[i] = A[i];
}
int k = s;
int index1 = s;
int index2 = m + 1;
while (index1 <= m && index2 <= e) { //두 그룹을 Merge 해주는 로직
if (tmp[index1] > tmp[index2]) {
A[k] = tmp[index2];
result = result + index2 - k; // 뒤쪽 데이터 값이 작아 선택되는 경우 결과 값 업데이트
k++;
index2++;
} else {
A[k] = tmp[index1];
k++;
index1++;
}
}
while (index1 <= m) {
A[k] = tmp[index1];
k++;
index1++;
}
while (index2 <= e) {
A[k] = tmp[index2];
k++;
index2++;
}
}
}
[참고 자료]
- 알고리즘 코딩 테스트 자바편
- https://www.geeksforgeeks.org/merge-sort/
Merge Sort - Data Structure and Algorithms Tutorials - GeeksforGeeks
Like QuickSort , Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two
www.geeksforgeeks.org
- https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
- https://st-lab.tistory.com/233
자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)
[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge
st-lab.tistory.com