알고리즘을 시작할 때 가장 먼저 접하게 되는 주제는 정렬(Sorting)이다.
여러가지 정렬 알고리즘이 있지만 병합정렬은 시간 복잡도가 항상 O(nlogn)으로 안정적이고 효율적이며 성능도 좋다.
병합정렬은 재귀적으로 배열을 계속 반으로 나누기 때문에 분할하는 단계는 배열의 크기 n에 대해 log₂n번 실행된다.
참고: 백준 문제를 사용해서 글을 작성했으나 병합정렬로 수 정렬하기2를 풀면 시간초과가 나오므로 해당 문제는 언어에 내장된 함수를 써야함. 수 정렬하기 2 답은 더보기 클릭.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.valueOf(br.readLine());
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
list.add(Integer.valueOf(st.nextToken()));
}
Collections.sort(list);
for (int j = 0; j < list.size(); j++) {
bw.write(list.get(j) + " ");
}
bw.flush();
bw.close();
br.close();
}
}
병합정렬(=합병정렬)
병합정렬은 분할정복(Divide and Conquer) 알고리즘의 대표적인 정렬방법이며, 데이터를 작은 단위로 쪼개서 정렬한 뒤 다시 병합하는 방식으로 동작한다. 병합정렬의 핵심 단계는 다음과 같다.
- 분할(Divide) : 배열을 반으로 나누어 각각의 부분 배열을 만든다.
- 정복(Conquer) : 부분 배열이 길이가 1이 될 때까지 재귀적으로 나눈다.
- 병합(Merge) : 두 부분 배열을 정렬하여 하나로 합친다.
Java로 병합정렬 구현하기
import java.util.Scanner;
public class Main {
public static int[] arr;
public static int[] tmpArr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new int[n];
tmpArr = new int[arr.length];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int[] mergeArr = mergeSort(0, arr.length - 1);
for (int i = 0; i < mergeArr.length; i++) {
System.out.println(mergeArr[i] + " ");
}
}
public static int[] mergeSort(int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // arr의 중간지점 저장
mergeSort(left, mid); // 1번 분할
mergeSort(mid + 1, right); // 2번 분할
int l = left; // 1번 분할의 시작점 저장
int r = mid + 1; // 2번 분할의 시작점 저장
int idx = l;
/*
1번 분할의 첫번째 원소가 mid보다 작거나 같고,
2번 분할의 첫 원소가 맨 끝 원소보다 작거나 같으면 분할 종료.
원소가 하나만 남았을 경우엔 더이상 분할할 수 없음을 의미함.
*/
while (l <= mid || r <= right) {
if (r > right || l <= mid && arr[l] < arr[r]) {
/*
2번 배열에서 원소를 다 가지고 온 상태거나,
1번 배열에서 아직 원소를 가지고 오지 않았고,
1번 분할의 첫번째 원소 값이 2번 분할의 첫번째 원소 값보다 작은 경우에 1번 분할 원소 저장,
위의 조건이 아니라면 2번 분할 원소 저장
*/
tmpArr[idx++] = arr[l++]; // 1번 분할 원소를 tmpArr에 저장
} else {
tmpArr[idx++] = arr[r++]; // 2번 분할 원소를 tmpArr에 저장
}
}
for (int i = left; i <= right; i++) {
arr[i] = tmpArr[i];
}
}
return arr;
}
}
코드 설명
if (left < right) {
int mid = (left + right) / 2;
mergeSort(left, mid);
mergeSort(mid + 1, right);
}
lfet는 현재 처리 중인 배열의 시작 인덱스, right는 끝 인덱스, mid는 배열을 반으로 나누기 위한 중간 지점이다.
mergeSort(left, mid)는 왼쪽 부분 배열을 처리하고, mergeSort(mid+1, right)는 오른쪽 부분 배열을 처리하며 배열의 길이가 1이 될 때까지 재귀적으로 호출된다.
int l = left; // 첫 번째 배열의 시작점
int r = mid + 1; // 두 번째 배열의 시작점
int idx = l; // 정렬된 값을 저장할 임시 배열의 인덱스분할된 두 부분 배열의 시작점을 l과 r에 저장한다.
idx는 정렬된 결과를 임시 배열 tmpArr에 저장할 때 사용할 위치이다.
while (l <= mid || r <= right) {
if (r > right || (l <= mid && arr[l] < arr[r])) {
tmpArr[idx++] = arr[l++];
} else {
tmpArr[idx++] = arr[r++];
}
}두 부분 배열의 현재 위치(l, r)을 비교하면서 작은 값을 tmpArr에 저장한다.
- r > right : 오른쪽 배열이 끝까지 처리된 경우
- l <= mid && arr[l] < arr[r] : 왼쪽 배열의 값이 오른쪽 배열의 값보다 작거나 같은 경우
- 그렇지 않으면 오른쪽 배열의 값을 선택함.
for (int i = left; i <= right; i++) {
arr[i] = tmpArr[i];
}임시 배열에 저장된 정렬 결과를 원래 배열 arr에 복사한 후 정렬된 배열을 반환한다.
실행 과정 예시
- 초기 배열 : [5, 3, 8, 6, 2]
- 분할 : [5, 3, 8] , [6, 2] -> [5, 3], [8], [6], [2] -> [5], [3], [8], [6], [2]
- 병합:
- [5], [3] -> [3, 5]
- [6], [2] -> [2, 6]
- [3, 5], [8] -> [3, 5, 8]
- [3, 5, 8], [2, 6] -> [2, 3, 5, 6, 8]