병합 정렬
배열 앞부분(영역)과 뒷부분(영역)으로 분할하여 정렬 후 다시 병합(합치기)하는 작업을 반복하며 정렬하는 알고리즘
병합 과정?
위와같이 배열을 앞, 뒤로 나눠서 각자 정렬한 후에 각각의 분할된 배열을 앞에서부터 서로 비교하며 기존 배열에 병합하게 된다. 이때 비교 대상인 두 배열 중 비교 후 값으로 선택되면 그 값이 있던 배열은 다음 요소로 이동하며 비교해나간다.
//두 배열 병합하기
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++];
// a , b 배열 중 병합하고 남은 요소가 있을 시
while(pa < na)
c[pc++] = a[pa++];
while (pb < nb)
c[pc++] = b[pb++];
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
//배열이 정렬되었다고 가정하기 위함
int[] a = {2,4,6,8,11,13};
int[] b = {1,2,3,4,9,16,21};
int[] c= new int[a.length+b.length];//병합할 배열
System.out.println("두 배열을 병합");
merge(a, a.length , b , b.length , c);
System.out.println("배열 a와 b를 병합하여 배열 c에 저장!!!");
System.out.print("a 배열 : ");
Arrays.stream(a).forEach(i-> System.out.print(i + " "));
System.out.print("\nb 배열 : ");
Arrays.stream(b).forEach(i-> System.out.print(i + " "));
System.out.print("\nc 배열 : ");
Arrays.stream(c).forEach(i-> System.out.print(i + " "));
}
여기서는 정렬하는 과정은 생략하고 정렬을 마친 후 병합하는 과정을 코드로 구현했다. 정렬을 마친 두 배열은 각자 정렬기준에 따라 정렬이 되어있기에 각각의 배열 첫번째 요소부터 서로 비교를 해간다.
이때 정렬조건에 따라 비교 후 결정되는 요소는 병합 배열에 앞에서부터 차례대로 들어간다. 그리고 요소가 선택된 배열은 병합 배열로 요소가 들어갔기에 다음 요소로 이동하여 비교하고 선택하는 과정을 거친다.
최종적으로 비교 선택을 반복하다보면 두 배열 중 더 이상 추가 요소가 없을 때 비교하고 선택하는 과정은 끝이난다. 이때 병합하는 과정에서 두 배열은 동일한 정렬조건에 따라 비교 선택되었기에 한 쪽 배열에 요소가 남았으면 자연히 병합하고자 하는 배열에 순차적으로 들어가게 된다. 이 부분은 결과에 표시한 부분에서 확인할 수 있다.
병합 정렬 구현
위에서 살펴 본 정렬된 두 배열을 병합하는 과정을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라 한다.
전체 배열을 절반씩 나누어 최소로 만들고 나누어진 앞, 뒤 배열을 각각 정렬 후 병합해가며 전체 배열을 정렬
분할 정복법 : 전체 문제를 부분으로 나누어 부분적으로 문제를 해결하여 전체 문제를 해결해 나가는 방법
static int[] buff; //작업용 배열
static void __mergeSort(int[] a, int left , int right){
//배열을 분할 시 분할 된 배열크기가 1개가 되기 전까지 분할
if(left < right){
int i;
int center = (left+right) / 2; // 분할을 위한 중앙요소 위치
int p = 0; // 중앙 기준 앞쪽 요소가 몇개 있는지 체크
int j = 0; //
int k = left; //현재 left위치
/*단순 이해를 위한 출력
System.out.println("=== 현재 배열 ===");
for(int c = left ; c <= right ; c++){
System.out.print(a[c]+ " ");
}
System.out.println();
if(left < center) System.out.println("=== 부분 앞쪽 ===");*/
__mergeSort(a, left , center); // 중앙 요소 기준 좌측 배열
/*단순 이해를 위한 출력
if(center+1 < right) System.out.println("=== 부분 뒤쪽 ===");*/
__mergeSort(a,center+1,right); // 중앙 요소 기준 우측 배열
for(i = left ; i <= center ; i++) // i값은 center + 1이 되면서 빠져나간다.
buff[p++] = a[i]; // 현재 작업중인 배열 처음부터 중앙까지 저장
/*
＊i == right이면 뒤쪽 요소들을 모두 소모
＊p값은 쉽게 배열의 경우 크기 -1이 마지막 인덱스이다.즉 마지막 요소 위치에
1개 증가한 값이다.(p = buff에 저장된 요소개수)
＊앞쪽 요소들은 [buff, j]를 통하여 제어 / 뒤쪽은 [a, i]를 통해서 제어
＊앞쪽 요소들은 buff에 저장이 되어있기에 뒤쪽 요소 중 앞쪽으로 와야할 경우 이동만
해주면 된다.
＊정렬한다에 대해서 한번 생각해보면 오름차순이거나 내림차순이거나 중요한 것은
가장 앞 쪽부터 기준에 맞게 정렬이 된다는 것이다.
＊위에 부분을 생각하며 while에 조건을 확인해보면 최종적으로 앞 뒤 배열 중 한 쪽이
먼저 모든 요소가 비교 후 선택되어 더 이상 요소가 없을 시 반복종료된다.
이때, 뒤 쪽 배열이 먼저 모두 소모되었다는 것은 앞 쪽으로 모두 정렬되었다는
의미이다. 그렇기에 buff에 남은 앞 쪽 요소들만 순차적으로 남은위치에 정렬해주면
된다. 그러나 앞 쪽이 먼저 소모되었다는 것은 뒤 쪽 배열에 남은 요소들은 정렬기준에
따라 앞 쪽 요소들보다 뒤에 위치해야하며, 남은 부분들은 그대로 위치하면 된다.
*/
while(i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while (j < p) {
a[k++] = buff[j++];
}
/*단순 이해를 위한 출력
System.out.println("=== 병합 정렬 후 ===");
for(int c = left ; c <= right ; c++){
System.out.print(a[c]+ " ");
}
System.out.println();
*/
}
}
static void mergeSort(int[] a , int n){
buff = new int[n];
__mergeSort(a,0,n-1);
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("병합 정렬");
System.out.print("요솟수 : ");
int nx = s.nextInt();
int[] x = new int[nx];
for(int i = 0; i < nx ; i++){
System.out.print("x["+i+"] :");
x[i] = s.nextInt();
}
System.out.println("=== 정렬 전 ===");
Arrays.stream(x).forEach(i-> System.out.print(i + " "));
System.out.println();
mergeSort(x,nx);
System.out.println("오름차순으로 정렬했습니다.\n");
System.out.println("=== 정렬 후 ===");
Arrays.stream(x).forEach(i-> System.out.print(i + " "));
}
개인적으로 공부를 하면서 직접 단계별로 어떻게 분할되고 병합되고 정렬되는지 그려보면서 해보았다.
그 부분들이 큰 도움이되어 병합 정렬 알고리즘에 대한 자세한 부분들은 위에 코드에 부분별로 확인한 부분과 이해한 부분들을 최대한 적어보았다.
자바에서는 Arrays.sort()를 활용하여 메서드 내부적으로 정렬 알고리즘을 구현했기에 이를 활용하면 더욱 쉽게 정렬을 수행할 수 있을 것이다. 기본 자료형 배열은 퀵 정렬, 객체 배열은 병합 정렬을 개선하여 내부적으로 구현했다고 한다.