6-7. 병합 정렬(Merge Sort)

정렬을 마친 배열의 병합

: 정렬을 마친 각 배열에서 선택한 요소의 값을 비교해 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬

 

 

 

 

 

[그림]

 

• 배열 a와 b를 앞에서부터 차례로 비교하여 작은 값을 꺼내 비에 넣음

 

 

 

[실습 코드]

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++];;
    }

 

• 3개의 반복문을 늘어놓는 단순한 알고리즘으로 구현
• 병합에 필요한 시간 복잡도는 O(n)

 

 

 

 

 

병합 정렬

: 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘

 

 

 

 

 

[그림]

 

• 먼저, 배열을 앞부분과 뒷부분으로 분할
• 두 배열을 각각 정렬하고 병합
• 앞뒤에 놓인 6개의 요소를 정렬할 때도 다시 병합 정렬을 적용

 

 

• 병합 정렬 알고리즘

배열의 요소 개수가 2개 이상인 경우
1. 배열의 앞부분을 병합 정렬로 정렬
2. 배열의 뒷부분을 병합 정렬로 정렬
3. 배열의 앞부분과 뒷부분을 병합

 

 

 

 

 

[실습 코드]

static int[] buff; //작업용 배열
    
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[p] <= a[i]) ? buff[p++] : a[i++];
            
        while(j < p)
            a[k++] = buff[j++];
    }
}

 

• 배열 병합의 시간 복잡도는 O(n), 전체 시간 복잡도는 O(n log n)
• 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법

 

 

 

 

 

Array.sort로 퀵 정렬과 병합 정렬하기

• 03장에서 이진 검색에 사용했던 binarySearch메서드는 java.util.Arrays클래스의 클래스 메서드로 제공
• 이 클래스는 배열을 정렬하는 클래스 메서드 sort도 제공

 

 

 

기본 자료형 배열의 정렬(퀵 정렬)

[실습 코드]

import java.util.Arrays;
//Arrays.sort 메서드로 정렬(퀵 정렬)
 
System.out.println("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num];
        
for(int i = 0; i < num; i++) {
    System.out.println("x[" + i + "]: ");
    x[i] = stdIn.nextInt();
    }
        
Arrays.sort(x);
        
System.out.println("오름차순 정렬");
for(int i = 0; i < num; i++)
    System.out.println("x[" + i + "] = " + x[i]);

 

• sort 메서드가 사용하는 알고리즘은 퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않음
• 즉, 배열에 같은 값이 존재하는 경우 같은 값 사이의 순서가 뒤바뀔 수 있음

 

 

 

클래스 객체 배열의 정렬(병합 정렬)

• 클래스 객체 배열을 정렬하는 메서드는 총 4개이며, 크게 두 종류로 나눌 수 있음
• 이들 메서드의 알고리즘은 병합 정렬을 개선한 것으로 안정적인 결과 보장

 

 

 

A. 자연 정렬이 필요한 배열

: 요소의 대소 관계를 비교하여 정렬

 

static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex)

 

 

 

[실습 코드]

import java.util.GregorianCalendar;
import static java.util.GregorianCalendar.*;
import java.util.Arrays;
//달력의 배열을 정렬
 
GregorianCalendar[] x = {
    new GregorianCalendar(2017, NOVEMBER, 1),
    new GregorianCalendar(1963, OCTOBER, 18),
    new GregorianCalendar(1985, APRIL, 5),
};
        
Arrays.sort(x);
        
for(int i = 0; i < x.length; i++) {
    System.out.printf("%04d년 %02d월 %02d일\n", 
        x[i].get(YEAR),
        x[i].get(MONTH) + 1,
        x[i].get(DATE));
}

 

 

 

 

 

B. 자연 정렬이 필요하지 않은 배열

: 요소의 대소 관계를 비교할 때 comparator c를 사용해 정렬

 

static <T> void sort(T[] a, Comparator<? super T> c)
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)