병합 정렬이란? 배열을 앞부분과 뒷부분 둘로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘이다.
존 폰 노이만(영화 오펜하이머에 나오는 그사람 맞음)이 1945년에 개발한 것으로 알려져 있다.
병합 정렬은 퀵정렬보다는 성능이 조금 뒤쳐지지고 데이터 크기만한 메모리가 더 필요하지만 안정적인 정렬이라는 점이 장점인 정렬이다.
병합 정렬 알고리즘은 최악, 최선, 평균 시간의 복잡도 모두에서 O(n log n)의 복잡도를 가지며 이가 의미하는 바는 대규모 데이터에 대해 효율적으로 작동 및 안정적인 정렬 알고리즘임을 의미한다.
정렬을 마친 두 배열의 병합 살펴보기
먼저 정렬을 마친 두 배열 A,B가 있다고 가정하자. 각 배열에서 선택한 요솟값을 먼저 비교한 뒤 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복해 정렬을 마친 배열을 만들게 된다.
아래 코드는 병합 정렬을 이해하기 위한 간단 코드이다.
public class MergeArray {
static void merge(int[] a, int na, int[] b, int nb, int[] c) {
int pa = 0;
int pb = 0;
int pc = 0;
while (pa < na && pb < nb)
c[pc++] = (a[pa] <= b[pb]) ? a[pa++]: b[pb++];
while (pa < na)
c[pc++] = a[pa++];
while (pb < nb)
c[pc++] = b[pb++];
}
public static void main(String[] args) {
int[] a = {2,4,6,8,11,13};
int[] b = {1,2,3,4,9,16,21};
int[] c = new int[13];
merge(a, a.length, b, b.length, c);
System.out.println("배열 c: ");
for(int i: c)
System.out.print(i+", ");
}
}배열 c에 배열a,b를 오름차순으로 정렬하는 코드이다. 배열 a,b가 미리 정렬돼 있어야 한다.
코드는 매우 간단하다. a,b,c의 pointer로 pa,pb,pc라는 변수를 생성후, 해당 변수를 활용하여 a,b배열의 요소를 순차적으로 누가 더 작은지 비교한다.
비교 후, c배열에 pc++를 통해 순차적으로 정렬하고, 배열 a나 b중 한개의 배열에서 남은 요소가 없이 모두 c배열에 저장했다면, 다른 배열의 남은 요소들을 통째로 c배열에 저장하면 된다.
병합에 필요한 시간 복잡도는 O(n)이다.
이 때 중요한 점은 이미 정렬된 배열이어야 한다는 점이다.
병합 정렬 구현하기
위 이미 정렬된 두 배열 병합방법을 응용하며, 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬(merge sort)이라고 한다.
위에서 이미 정렬된 배열된 배열을 병합하는 방법을 알아봤다. 사실 병합 정렬의 전부이다.
이미 정렬된 배열이라니? 정렬하는 알고리즘에서 이미 정렬된 배열을 가지고 와서 쓰는게 큰 의미가 있나? 생각할 수 있겠다.
하지만 배열을 계속 나누다 보면 언젠가는 정렬된다. 바로 요솟수가 1개일 때이다. 12개의 요솟수를 가지는 배열a를 계속 반으로 나누다보면 12-6-3-1 혹은 12-6-3-2-1로 결국에는 1개만 남게 만들 수 있다. 요솟수가 1개라는 말은 이미 정렬이 된 상태로 볼 수 있고 위에서 배운 이미 정렬된 배열을 조건으로 하는 병합을 수행할 수 있게 된다.
이렇게 차례대로 1-3-6-12를 역순으로 병합하면 처음 배열의 정렬된 배열을 찾을 수 있고, 멀리있는 요소와 서로 수를 교환하지 않기에 안정적인 정렬이 된다.
항상 이야기 하지만 분할 정복법은 '그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘'을 뜻한다.
아래 요솟수 12개의 배열을 통해 병합 정렬을 살펴보자.
int[] arr = {5,6,4,8,3,7,9,0,1,5,3,2};해당 배열을 6개씩 2개의 배열로 나눈다.
int[] arr1 = {5,6,4,8,3,7}; // 앞6개
int[] arr2 = {9,0,1,5,3,2}; // 뒤6개이 때, arr1, arr2를 바로 정렬하지 않고 다시 병합 정렬을 적용하는게 포인트이다. 예를들어 arr2를 아래처럼 나눈다
int[] arr2 = {9,0,1,5,3,2}; // 뒤6개
int[] arr2-1 = {9,0,1}; 뒤6개-앞3개
int[] arr2-2 = {5,3,2}; 뒤6개-뒤3개여기서 arr2-1, arr2-2도 바로 정렬하지 않고 또 다시 병합 정렬을 적용한다.
arr2-2를 예로 들자.
int[] arr2-2 = {5,3,2}; 뒤6개-뒤3개
int[] arr2-2-1 = {5}; 뒤6개-뒤3개-앞1개
int[] arr2-2-2 = {3,2}; 뒤6개-뒤3개-뒤2개여기서 arr2-2-1은 요솟수가 1개이기 때문에 잠시 보류하고 arr2-2-2를 병합 정렬한다.
int[] arr2-2-2 = {2,3}; 뒤6개-뒤3개-뒤2개
int[] arr2-2-2-1 = {3};
int[] arr2-2-2-2 = {2};자 이제 다 왔다. 2-2-2-1, 2-2-2-2 모두 요소가 1가지이기 때문에 병합을 할 수 있는 조건이된다 (요소가 1가지이기에 정렬상태라 볼 수 있음)
int[] mergedArr2-2-2 = {2,3}; // 2-2-2-1, 2-2-2-2 병합이제 아까 보류했던 2-2-1과 정렬이 끝난2-2-2를 병합한다.
int[] mergedArr2-2 = {2,3,5}; // 2-2-1, 2-2-2 병합2-1도 똑같은 방법으로 병합정렬하고, 2-2도 병합정렬을 수행한다. 후에 둘이 병합한다. 같은 방식으로 arr1, arr2도 병합한다.
int[] mergedArr1 = {3,4,5,6,7,8}; // 1-1, 1-2 병합
int[] mergedArr2 = {0,1,2,3,5,9}; // 2-1, 2-2 병합
int[] mergedArr = {0,1,2,3,3,4,5,5,6,7,8,9}; // arr1, arr2 병합최대한 이해하기 쉽게 적었다. 간단하지 않은가? 메모리만 충분하다면 그 어떤 배열도 안정적이고 비교적 빠르게 정렬 가능하다. 또한 매우 간단하기에 직관적으로 이해할 수 있다.
병합 정렬 예제 코드
public class MergeSort {
static int[] buff; // 작업용 배열
//a[left]~a[right]를 재귀적으로 병합 정렬
static void __mergeSort(int[] a, int left, int right) {
if (left < right) {
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
__mergeSort(a, left, center); // 배열의 앞부분을 병합 정렬
__mergeSort(a, center + 1, right); // 배열의 뒷부분을 병합 정렬
for (i = left; i <= center; i++)
buff[p++] = a[i];
while(i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++]: a[i++];
while (j < p)
a[k++] = buff[j++];
}
}
// 병합 정렬
static void mergeSort(int[] a, int n) {
buff = new int[n]; // 작업용 배열을 생성
__mergeSort(a, 0, n-1); // 배열 전체를 병합 정렬
buff = null; // 작업용 배열을 해체
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 : ");
int[] x = new int[sc.nextInt()];
for (int i = 0; i < x.length; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
mergeSort(x, x.length);
for(int i = 0; i < x.length; i++)
System.out.println("x[" + i + "]=" + x[i]);
}
}메모장에 하나하나 적어가며 보면 이해가 되긴 할 것이나 설명을 조금 해 보자.
↓위의 코드 생략버전
static int[] buff; // 작업용 배열
//a[left]~a[right]를 재귀적으로 병합 정렬
static void __mergeSort(int[] a, int left, int right) {
if (left < right) {
// 생략
int center = (left + right) / 2;
// 생략
__mergeSort(a, left, center); // 배열의 앞부분을 병합 정렬
__mergeSort(a, center + 1, right); // 배열의 뒷부분을 병합 정렬
// 앞부분과 뒷부분을 병합 -병합 과정
}
}
// 병합 정렬
static void mergeSort(int[] a, int n) {
buff = new int[n]; // 작업용 배열을 생성 -과정A
__mergeSort(a, 0, n-1); // 배열 전체를 병합 정렬 -과정B
buff = null; // 작업용 배열을 해체 -과정C
}mergeSort()메서드가 수행하는 내용은 아래와 같다.
과정A. 병합한 결과를 일시적으로 저장할 작업용 배열인 buff를 생성.
과정B. 정렬 작업을 수행할 __mergeSort 메서드를 호출
과정C. 작업용 배열을 해체함
여기서 과정B의 수행 내용 __mergeSort()호출이 실제로 병합 정렬을 수행하는 메서드이다.
이__mergeSort()는
a(정렬할 배열),
left(첫 요소 인덱스),
right(마지막 요소 인덱스)
를 인자로 받아 left가 right보다 작을 때만 동작한다. 이 메서드는 가장 먼저 앞부분(a[left]~a[center])과 뒷부분(a[center+1]~a[right])에 대해 __mergeSort()를 재귀 호출 한다.
이렇게 재귀호출을 하다보면 자동으로 앞부분 뒷부분이 정렬되고 __mergeSort()의 재귀호출들이 모두 끝나면 병합 코드가 실행되어 앞부분과 뒷부분을 병합하게 된다.
전체적인 구조는 이렇게 단순하지만 코드를 읽어보면 병합하는 부분이 조금 복잡하게 느껴지기에 여기도 간단한 설명을 붙여보자면,
↓병합 과정 코드
for (i = left; i <= center; i++) // 과정 1
buff[p++] = a[i];
while (i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++]; // 과정 2
while (j < p) // 과정 3
a[k++] = buff[j++];병합 순서는 다음과 같이 3단계로 이루어진다.
과정1. 배열의 앞부분(a[left]~a[center])을 buff[0]~buff[center-left]에 복사한다. for문이 끝날 때 p값은 복사한 요솟수인 'center - left + 1'이 된다.
과정2. 배열의 뒷부분(a[center+1]~a[right])과 buff에 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에 저장한다.
과정3. 배열 buff에 아직 남아있는 요소를 배열 a에 복사한다.
끝
