병합(merge) 정렬

* 병합 정렬

정렬의 마친 두 배열을 병합하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.



1. 정렬을 마친 두 배열을 병합하기

public class MergeArray {
    //정렬을 마친 배열 a, b를 병합하여 배열 c에 저장
    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 배열에 저장한다.
            c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        while (pa < na) //a에 남아있는 요소를 복사
            c[pc++] = a[pa++];
        while (pb < nb) //b에 남아있는 요소를 복사
            c[pc++] = a[pb++];

    }
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int[] a = {2, 4, 6, 11, 13};
        int[] b = {1, 2, 3, 4, 9, 16, 21};
        int[] c = new int[13];

        System.out.println("두 배열의 병합");

        merge(a, a.length, b, b.length, c); //배열 a와 b를 병합하여 c에 저장

        System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
        System.out.println("배열 a : ");
        for (int i = 0; i < a.length; i++) {
            System.out.print("a[" + i + "] = " + a[i]);
        }
        System.out.println("배열 b : ");
        for (int i = 0; i < b.length; i++) {
            System.out.print("b[" + i + "] = " + b[i]);
        }
        System.out.println("배열 c : ");
        for (int i = 0; i < a.length; i++) {
            System.out.print("c[" + i + "] = " + c[i]);
        }

    }
}

2. 1번을 응용하여 분할 정복법에 따라 병합 정렬하기
배열을 2등분하여 앞부분과 뒷부분으로 나눈다.
앞부분과 뒷부분을 각각 정렬하고 병합한다.
여기서 재귀호출을 하게 되는데 그 앞부분과 뒷부분도 또다시 병합정렬을 이용하기 때문이다.

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++) //버퍼에다 a[left]~a[center]를 복사한다.
                buff[p++] = a[i];

            while (i <= right && j < p) //버퍼와, a배열(center 뒷부분부터 right까지)을 서로 병합정렬한다.
                a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];

            while (j < p) //buff의 나머지 요소를 배열 a에 복사한다.
                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 stdIn = new Scanner(System.in);

        System.out.println("병합 정렬");
        System.out.print("요솟수:");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "] : ");
            x[i] = stdIn.nextInt();
        }

        mergeSort(x, nx);

        System.out.println("오름차순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]= " + x[i]);
        }

    }
}

3. 자바가 제공하는 sort 사용하기
- 기본 자료형 정렬

public class ArraySortTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.print("요솟수 : ");
        int num = stdIn.nextInt();
        int[] x = new int[num];

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "] :");
            x[i] = stdIn.nextInt();
        }

        //sort 메소드는 기본 자료형의 배열을 정렬한다.
        //퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않다.
        //즉 배열에 같은 값이 존재하는 경우 같은 값 사이의 순서가 바뀔 수 있다.

        Arrays.sort(x);

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "] :");
        }
    }
}

- 클래스 객체 배열의 정렬 (병합 정렬)
클래스 객체 배열의 정렬에서 사용하는 알고리즘은 병합 정렬을 개선한 것으로 안정적인 결과가 보장된다.

아래 메소드들은 기본 오름 차순 정렬이다. static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex) : fromIndex 부터 toIndex 까지만 정렬한다.

public class SortCalendar {
    public static void main(String[] args) {
        GregorianCalendar[] x = {
                new GregorianCalendar(2017, Calendar.NOVEMBER, 1),
                new GregorianCalendar(1963, Calendar.OCTOBER, 18),
                new GregorianCalendar(1985, Calendar.APRIL, 5),
        };

        Arrays.sort(x);

        for (int i = 0; i < x.length; i++)
            System.out.printf("%04d년 %02d월 %02d일\n",
                    x[i].get(Calendar.YEAR),
                    x[i].get(Calendar.MONTH) + 1,
                    x[i].get(Calendar.DATE)
            );
    }
}

결과 출력
1963년 10월 18일
1985년 04월 05일
2017년 11월 01일

만약 정렬 시에 원하는 기준이 있을 경우 그 키를 기준으로 하는 Comparator를 구현 하면 된다. 아래 메소드들은 기본 오름 차순 정렬이다.

static void sort(T[] a, Comparator c)
static void sort(T[] a, int fromIndex, int toIndex, Comparator c) : T를 부모로 갖는 클래스이어야 한다.

public class PhyscExamSort {
    static class PhyscData {
        String name;
        int height;
        double vision;

        PhyscData(String name, int height, double vision) {
            this.name = name; this.height = height; this.vision = vision;
        }
        public String toString() {
            return name + " " + height + " " + vision;
        }

        //키 오름차순용 comparator
        //Comparator의 compare 메소드를 오버라이드하여 기준을 정함.

        static final Comparator HEIGHT_ORDER = new HeightOrderComparator();

        private static class HeightOrderComparator implements Comparator {
            @Override
            public int compare(PhyscData d1, PhyscData d2) {
                return (d1.height > d2.height) ? 1 :
                        (d1.height < d2.height) ? -1 : 0;
            }
        }
    }
    public static void main(String[] args) {
        PhyscData[] x = {
                new PhyscData("이나령", 162,0.3),
                new PhyscData("전서현", 122,1.3),
                new PhyscData("홍길동", 172,0.8),
                new PhyscData("유지훈", 182,0.9),
        };
        Arrays.sort(x, PhyscData.HEIGHT_ORDER); //HEIGHT_ORDER 를 사용하여 정렬한다.
    }
}