[BOJ] 백준 2751 수 정렬하기 2

출처: www.acmicpc.net/problem/2751

Approach

합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

병합 정렬은 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법

- 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다.

- 2단계 정복(Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다.

- 3단계 결합(Combine) - 분할해서 해결한 결과를 결합하여 마무리한다.

[분할 과정]

재귀함수르 통해 크기가 = 1 (left >= right)될 때까지 분할 합니다. 

 

[merge 과정]

작은 단위부터 merge할 때, 오름차순에 맞게 자리를 찾아갑니다.

병합 정렬을 구현할 때, 정렬에 사용되는 배열 변수를 '전역 변수'로 선언해야 공간복잡도가 효율적입니다.

재귀 함수 과정에서 새롭게 배열을 생성하면 메모리 낭비가 큽니다.

 

① x, y 비교 ▶ 4 < 3 이므로 k 위치에 3을 넣습니다. (y++, k++)

② 4 < 5 이므로 k 위치에 4를 넣습니다. (x++, k++)

③ 6 > 5 이므로, k 위치에 5를 넣습니다. (y++, k++)

④ 우측에는 더 이상 비교할 대상이 없으므로 좌측의 모든 숫자를 아래 배열에 채웁니다.

 

▶ 시간 복잡도 O(N logN)

퀵 정렬은 Pivot 값에 따라서 편향되게 분할할 가능성이 있다는 점에서

최악의 경우 O(N2)의 시간 복잡도가 날 수 있지만,

병합 정렬은 분할과정이기 때문에 원소의 배치와 상관없이 O(N * logN)을 보장합니다.

---

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
     static int[] arr, temp;
      
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
         
        int N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        temp = new int[N+1];
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
         
        mergeSort(1, N);
         
        for(int i=1; i<=N; i++) {
            sb.append(arr[i] + "\n");
        }
        System.out.println(sb);
    }
    public static void mergeSort(int left,int right) {
        if(left >= right) return;  
         
        int mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);    
         
    }
    public static void merge(int left, int mid, int right) {
        int x = left; int y = mid + 1;    
        int k = left;    
         
        while(x <= mid || y <= right) {    
            if(x <= mid && y <= right) {    
                if(arr[x] <= arr[y]) {
                temp[k] = arr[x++];    
                }
                else if(arr[x] > arr[y]) {
                temp[k] = arr[y++];
                }
            }
            else if (x <= mid && y > right){
                temp[k] = arr[x++];
            }
            else if (x > mid && y <= right){
                temp[k] = arr[y++];
            }
            k++;
        }
        for(int i=left; i<=right; i++)    
            arr[i] = temp[i];
    }
}