📁병합 정렬
배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 합병하는 작업을 반복하는 정렬로 효율적이고 안정적인 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 알고리즘을 따른다.
1️⃣ 병합 정렬의 과정
이미지 출처: algorithm.wiki
- 배열 요소 개수가 2개 이상인 경우(길이가 1 이하이면 이미 정렬된 내용)
- 분할(Divide) : 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 배열로 나눈다.
- 정복(Conquer) : 각 부분 배열을 재귀적으로 합병 정렬을 이용해 정렬한다.
- 결합(Combine) : 두 부분 배열을 다시 하나의 정렬된 배열로 합병한다. 이 때, 정렬 결과는 임시 배열에 저장된다.
- 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = new int[] {38, 27, 43, 3, 9, 82, 10, 22};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
static void sort(int[] arr, int left, int right) {
if(left == right) return;
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
static void merge(int[] arr, int left, int mid, int right) {
int n = mid - left + 1;
int m = right - mid;
int[] leftArr = new int[n];
int[] rightArr = new int[m];
for(int i = 0; i < n; i++) {
leftArr[i] = arr[left+i];
}
for(int i = 0; i < m; i++) {
rightArr[i] = arr[mid + 1 + i];
}
int i = 0;
int j = 0;
int k = left;
while(i < n && j < m) {
if(leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// 왼쪽 배열의 남아있는 내용들 채워주기
while(i < n) {
arr[k] = leftArr[i];
i++;
k++;
}
// 오른쪽 배열의 남아있는 내용들 채워주기
while(j < m) {
arr[k] = rightArr[j];
j++;
k++;
}
}
}2️⃣ 병합 정렬 정리
-
병합 정렬은 O(NlogN)의 시간 복잡도를 가지고 있어 다른 정렬 알고리즘에 비해 효율적이다.
-
동일하 값의 원소가 입력에 따라 순서를 보장하는 안정 정렬(Stable Sort) 알고리즘이다.
-
최선과 최악의 경우에도 항상 동일한 시간 복잡도를 가진다.
-
원본 배열을 분할하여 새로운 배열을 추가적으로 만들기 때문에 추가적인 메모리가 필요하다.
-
다른 정렬 알고리즘에 비해 구현하기가 복잡하다.
-
배열의 크기가 작은 경우 퀵 정렬 알고리즘이 더 빠르다.
3️⃣ 정렬 알고리즘 시간복잡도 비교
4️⃣ 병합 정렬 코딩테스트 예제
📌 문제 탐색하기
🌝 입력
- 첫째 줄에 수의 개수 N이 주어진다. (1 <= N <= 1,000,000)
- 둘째 줄부터 N개의 줄에 수가 주어진다. 이 값은 절댓값이 1,000,000보다 작거나 같은 정수이고 수는 중복되지 않는다.
🌑 출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
🕔 시간제한
2초
🚨 접근
병합 정렬을 활용해 정렬해보자.
- 이 문제는 Arrays.sort()로 풀면 시간초과가 발생한다. Arrays.sort()의 경우 dual-pivot Quicksort 알고리즘을 사용한다. 물론 평균 시간 복잡도가 O(nlogn)이고 매우 빠른 알고리즘이지만 최악의 경우 O(n²)의 시간 복잡도를 가지게 된다.
- 자바에서 제공하는 Collections.sort()를 사용하면 Timsort 알고리즘을 사용하는데 이는 합병 및 삽입 정렬을 사용한다. 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm이라고 하는데 합병 정렬의 경우 최선, 최악 모두 O(nlogn)을 보장하고, 삽입 정렬의 경우 최선의 경우는 O(n), 최악의 경우는 O(n²)이다. 두 정렬 모두 안정 정렬(stable sort)이기 때문에 hybrid stable sorting이라고도 한다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘으로 시간 복잡도가 O(n) ~ O(nlogn)을 보장한다는 장점이 있다.
- 우리는 Java에서 제공하는 Collections.sort()를 사용하지 않고 병합 정렬 공부를 위해 병합 정렬을 이용해 문제를 풀어보도록 하겠다.
🙆♂️ 가능한 시간복잡도
이중 반복 수행 불가능
- N이 1,000,000개이기 때문에 이중으로 반복 수행하는 경우 시간 초과가 발생한다.
📌 정답 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 배열 크기 입력 받기
int n = Integer.parseInt(br.readLine());
// 배열 선언 및 배열의 요소 입력 받기
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
mergeSort(arr, 0, arr.length - 1);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
sb.append(arr[i]).append("\n");
}
System.out.println(sb);
}
/**
* 병합 정렬 함수: 배열을 분할하고 정렬된 상태로 병합
* @param arr 정렬할 배열
* @param left 현재 부분 배열의 시작 인덱스
* @param right 현재 부분 배열의 끝 인덱스
*/
static void mergeSort(int[] arr, int left, int right) {
// 배열이 더 이상 분할할 수 없는 크기라면 반환
if(left == right) return;
// 중간점 계산 (overflow 방지를 위해 left + right / 2가 아닌 left + (right - left) / 2 사용
int mid = left + (right - left) / 2;
// 왼쪽 부분 배열 재귀적으로 병합 정렬
mergeSort(arr, left, mid);
// 오른쪽 부분 배열 재귀적으로 병합 정렬
mergeSort(arr, mid + 1, right);
// 정렬된 두 부분 배열 병합
merge(arr, left, mid, right);
}
/**
* 두 개의 정렬된 부분 배열을 병합
* @param arr 원본 배열
* @param left 왼쪽 부분 배열의 시작 인덱스
* @param mid 중간 인덱스 (왼쪽 부분 배열의 끝)
* @param right 오른쪽 부분 배열의 끝 인덱스
*/
static void merge(int[] arr, int left, int mid, int right) {
int n = mid - left + 1;
int m = right - mid;
int[] leftArr = new int[n];
int[] rightArr = new int[m];
for(int i = 0; i < n; i++) {
leftArr[i] = arr[left + i];
}
for(int i = 0; i < m; i++) {
rightArr[i] = arr[mid + i + 1];
}
int i = 0;
int j = 0;
int k = left;
while(i < n && j < m) {
if(leftArr[i] > rightArr[j]) { // 오른쪽 배열이 더 작을 경우
arr[k] = rightArr[j];
j++;
} else { // 왼쪽 배열이 더 작을 경우
arr[k] = leftArr[i];
i++;
}
k++;
}
// 위 반복에서 둘 중 하나(왼쪽 혹은 오른쪽)는 모두 꺼내서 원본 배열에 담았으므로
// 왼쪽 배열의 남은 값을 먼저 수행하던 오른쪽 배열의 남은 값을 먼저 수행하던 상관 없다.
while(i < n) {
arr[k] = leftArr[i];
i++;
k++;
}
while(j < m) {
arr[k] = rightArr[j];
j++;
k++;
}
}
}