자료구조 - Sort(합병 정렬)

Merge Sort

정의: 분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 합치는 알고리즘이다.

• 시간 복잡도는 O(nlogn)
  -> 배열의 크기를 n이라 할때, 분할 할때 마다 배열의 크기가 n/2씩 감소.
  이때 분할하는데 걸리는 시간은 O(log n)
  -> 정복(합병)할때 마다 두 배열을 비교하면서 작은 요소부터 차례로 결과 배열에 추가.
  이 과정에서 최대 (n)개의 요소를 비교하게 되므로, 두 개의 배열을 합치는 데 걸리는 시간은 O(n)
• 대량의 데이터 정렬에 주로 사용.

public class sort {
    public static void merge(int A[], int low, int mid, int high) {
        //정렬할게요.
        int B[] = new int[high + 1];
        int h = low; //임시 배열 B의 low.
        int i = low; //배열 A의 low
        int j = mid + 1; // 배열 A의 mid +1
        int k;

        while (i <= mid && j <= high) {
            if (A[i] < A[j]) {
                B[h] = A[i]; //작은 놈이 임시 배열 low 지수에 저장.
                i++; // 왼쪽 배열 포인터 증가
            } else{
                B[h] = A[j];
                j++;// 오른쪽 배열 포인터 증가
            }
            h++; //임시배열도 저장할 포인터를 1만큼 증가.
        }

        // 비교할게 없다면?
        if (i > mid) { // 오른쪽 배열을 싹다 대입.
            for (k = j; k <= high; k++) {
                B[h] = A[k];
                h++;
            }
        }else { // 왼쪽 배열을 싹다 임시배열 B에 대입.
            for (k = i; k <= mid; k++) {
                B[h] = A[k];
                h++;
            }
        }

        /*while (i <= mid) {
            B[h] = A[i];
            i++;
            h++;
        }
        while (j <= high) {
            B[h] = A[j];
            j++;
            h++;
        }

         */

        for (k = low; k<=high; k++) {
            A[k] = B[k];
        }
    }

    public static void printArray(int A[]) {
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
        }
    }

    public static void mergeSort(int A[], int low, int high) { //합병할게요
        if (low < high) {
            int mid = (low+high) /2;
            mergeSort(A,low,mid);
            mergeSort(A,mid+1,high);
            merge(A,low,mid,high);
        }
    }

    public static void main(String[] args) {
        int A[] = {91, 82, 13, 85, 68, 70, 98, 24};
        System.out.println("정렬전");
        printArray(A);
        System.out.println("정렬후");
        mergeSort(A,0,A.length-1);
        printArray(A);
    }
}