병합정렬

병합 정렬 알고리즘

배열의 요솟수가 2개 이상인 경우

• 배열의 앞부분을 병합 정렬로 정렬합니다
• 배열의 뒷부분을 병합정렬로 정렬합니다
• 배열의 앞부분과 뒷부분을 병합합니다

배열 병합의 시간복잡도는 O(n), 병합정렬까지 생각하면 전체 시간복잡도는 O(n log 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;
            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의 뒷부분과 배열 buff를 배열a에 병합한다.
                a[k++] = (buff[j] <= a[i])?buff[j++] : a[i++];

            while(j < p) // buff에 남은 요소 복사
                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) {
        System.out.println("병합정렬");
        System.out.println("요솟수: 7 ");
        int nx = 9;
        int[] x = new int[]{6,4,3,7,1,9,8};

        mergeSort(x, nx); // 배열 x를 병합정렬

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

    }
}

 

---

Arrays.sort를 이용한 클래스 객체 배열의 정렬 (병합정렬)

 

A. 자연스러운 순서를 갖고 있는 배열 정렬(Int, String 배열)

import java.util.Arrays;
import java.util.Calendar;
import java.util.GregorianCalendar;

import static java.util.Calendar.*;

public class SortCalendar {
    public static void main(String[] args) {
        // GregorianCalendar는 Comparable 인터페이스를 구현하고 있음.
        GregorianCalendar[] x = {
          new GregorianCalendar(2022, 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 를 사용하여 대소관계 판단)

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class PhyscExamSort {

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        PhyscData[] x = {
                new PhyscData("강민하",162,0.3),
                new PhyscData("김찬우",173,0.7),
                new PhyscData("박민서",175,2.0),
                new PhyscData("유서범",171,1.5),
                new PhyscData("이수연",168,0.4),
                new PhyscData("장경오",174,1.2),
        };
        
        Arrays.sort(x,PhyscData.HEIGHT_ORDER);
        System.out.println("신체검사 리스트");
        System.out.println("이름  키   시력");
        System.out.println("---------------------------");
        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);
            
        }
    }

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

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

        @Override
        public String toString() {
            return name + " " + height + " " + vision;
        }
        
        static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
        
        private static class HeightOrderComparator implements Comparator<PhyscData>{

            @Override
            public int compare(PhyscData d1, PhyscData d2) {
                return (d1.height > d2.height) ? 1:
                        (d1.height < d2.height) ? -1 : 0;
            }
        }
        
    }
    
    
}