[알고리즘] 병합 정렬

병합 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬

 

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

---

정렬을 마친 배열의 병합

 

정렬된 배열 a와 b를 비교하여 작은 값을 배열 c에 넣는다.

static void merge(int[] a, int na, int[] b, int nb, int[] c) {
  int pa = 0; // a의 pointer
  int pb = 0; // b의 pointer
  int pc = 0; // c의 pointer

  // 1
  while(pa < na && pb < nb)
  	c[pc++] = (a[pa] <= b[pb] ? a[pa++] : b[pb++]);

  // 2
  while(pa < na)
  	c[pc++] = a[pa++];

  // 3
  while(pb < nb)
  	c[pc++] = b[pb++];

  for(int i = 0; i < c.length; i++)
  	System.out.print("c[" + i + "] : " + c[i] + "\t");
}

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[a.length + b.length];

  merge(a, a.length, b, b.length, c);
}

console : 1	2	2	3	4	4	6	8	9	11	13	16	21

 

1. a나 b의 pointer가 배열의 끝에 다다르면 작업을 종료합니다.

 

2. pb가 먼저 배열의 끝에 다다라서 1이 종료되었다면 a 배열에 남아있는 값들을 모두 c에 넣어줍니다.

 

3. 2와 반대로 pa가 먼저 배열의 끝에 다다라서 1이 종료되었다면 b 배열에 남아있는 값들을 모두 c에 넣어줍니다.

 

* 반복문을 늘어놓는 단순한 알고리즘으로 구현하였으며 시간 복잡도는 O(n)입니다.

---

병합 정렬

 

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

 

하나의 배열을 앞부분과 뒷부분으로 나눕니다. 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있습니다.

나누어진 배열도 병합 정렬을 이용해서 정렬합니다.

 

public class MergeSort {
    static int[] buff; // 작업용 배열

    // a[left] ~ a[right]를 재귀적으로 병합 정렬
    static void __mergeSort(int[] a, int left, int right) {
        if(left < right) {
            int i; // left ~ right까지 a 검수 인덱스
            int center = (left + right) / 2;
            int p = 0; // buff의 length
            int j = 0; // 0 ~ p까지 buff 검수 인덱스
            int k = left; // a의 시작 인덱스


            __mergeSort(a, left, center);
            __mergeSort(a, center + 1, right);

            // 1. 배열 a의 left부터 center까지 buff에 다 넣음
            for (i = left; i <= center; i++)
                buff[p++] = a[i];

            // 2. 현재 시점의 i의 값은 center+1
            // a의 인덱스 i가 right와 작거나 같고
            // buff의 인덱스 j(0)는 p(buff.length)보다 작아야함
            // buff[j]와 a[i]를 비교해서 작은 값을 a[0]부터 쌓는다
            while (i <= right && j < p)
                a[k++] = buff[j] <= a[i] ? buff[j++] : a[i++];

            // 3. buff의 값들이 a의 값 보다 클 경우 남아있을 수 있는데
            // 마지막으로 이 값 들을 a에 넣는다
            while (j < p)
                a[k++] = buff[j++];
        }
    }

    static void mergeSort(int[] x, int n) {
        buff = new int[n];

        __mergeSort(x, 0, n - 1);

        buff = null;
    }

    public static void main(String[] args) {
        int[] x = {22, 5, 11, 32, 120, 68, 70, 1};

        mergeSort(x, x.length);

        for(int t : x)
            System.out.print(t + "\t");
    }

}

console : 1	5	11	22	32	68	70	120

---

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

 

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

 

static void sort sort(byte[] a) // byte[] char[] int[] 등 기본 자료형을 정렬해 주는 메서드

 

기본 자료형을 정렬해주는 sort는 퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않습니다.

즉, 배열에 같이 값이 존재하는 경우 같은 값 사이의 순서가 뒤바뀔 수 있습니다.

 

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

 

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

요소의 대소 관계를 비교하여 정렬합니다.

static void sort(Object[] a)

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

 

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)

 

A, B에서 소개한 메서드의 알고리즘은 병합 정렬을 개선한 것으로 안정적인 결과가 보장됩니다.

 

* A의 메서드로 자연 정렬하기

public class SortCalendar {

    public static void main(String[] args) {
        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)
                    );
        }
    }
}

console
1963년 10월 18일
1985년 04월 05일
2017년 11월 01일

GregorianCalendar 클래스는 Calendar 클래스를 상속받는데, Calendar 클래스는 Comparable 인터페이스의 compareTo 메서드를 구현합니다. 구현된 compareTo 메서드를 기준으로 정렬됩니다.

 

* B의 메서드로 정렬하기

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
        static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
        static final Comparator<PhyscData> HEIGHT_ORDER_DESC = new HeightOrderComparator();

        private static class HeightOrderComparator implements Comparator<PhyscData> {
            @Override
            public int compare(PhyscData o1, PhyscData o2) {
                return (o1.height > o2.height ? 1 :
                        (o1.height < o2.height) ? -1 : 0);
            }
        }
    }

    public static void main(String[] args) {
        PhyscData[] x = {
                new PhyscData("a", 162, 0.3),
                new PhyscData("b", 152, 0.3),
                new PhyscData("c", 166, 0.3),
                new PhyscData("d", 172, 0.3),
                new PhyscData("e", 182, 0.3),
                new PhyscData("f", 142, 0.23),
                new PhyscData("g", 176, 0.63),
                new PhyscData("h", 177, 0.4)
        };

        Arrays.sort(x, PhyscData.HEIGHT_ORDER);

        for(int i = 0; i < x.length; i++) {
            System.out.printf("%-8s%3d%5.1f\n", x[i].name, x[i].height, x[i].vision);
        }
    }
}

console
f       142  0.2
b       152  0.3
a       162  0.3
c       166  0.3
d       172  0.3
g       176  0.6
h       177  0.4
e       182  0.3