합병정렬 (Merge Sort), 백준 2751 Java

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

 

배열의 길이가 1이 될때 까지 분할 한뒤, 정렬하며 합치는 알고리즘

 

알고리즘 장점 : 안정정렬 (같은 값일 경우 상대적 위치가 바뀌지 않는다)

 

 

<Input>

3

100000

-100000

0

 

<Output>

-100000

0

100000

 

 

구현 방법 :

 

(1) 배열을 반으로 나눠준다.

(2) 나눈 배열을 다시 MergeSort에 태운다

(3) MergeSort를 타고 나온 두 배열의 요소들을 크기 비교하며 합친다.

   합칠 때    

   i ) 한쪽 배열을 끝까지 조회했을 경우

       다른 배열에 남아있는 요소는 항상 더 크므로 뒤에 전부 add 해준다.

 

 

 

import java.util.Scanner;
 
public class Problem2751_Merge {
    public static void main(String[] args) {
 
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
 
    // 1~N 까지 사용
    int[] arr = new int[N];
 
    int idx = 0;
    while (idx < N) {
        arr[idx] = sc.nextInt();
        idx++;
    }
 
    arr = mergeSort(arr);
 
    for(int i=0; i<N; i++) {
        System.out.println(arr[i]);
    }
}
 
static int[] mergeSort(int[] arr) {
 
    if(arr.length == 1) {
        return arr;
    }
    else { // 아니면 또 나눠줌
 
        int midA = (int)arr.length/2;
        int midB = arr.length-midA;
 
        int arrA[] = new int[midA];
        int arrB[] = new int[midB];
 
        System.arraycopy(arr, 0, arrA, 0, midA);
        System.arraycopy(arr, midA, arrB, 0, midB);
 
        arrA = mergeSort(arrA);
        arrB = mergeSort(arrB);
 
        // 나눈 배열이 mergesort 를 타고 나오면 합쳐줌
        arr = mergeOperator(arrA, arrB);
 
    }
 
    return arr;
}
 
private static int[] mergeOperator(int[] arrA, int[] arrB) {
    int length = arrA.length+arrB.length;
    int[] mergeArr = new int[length];
    int idx = 0;
    int idxA = 0;
    int idxB = 0;
 
    // A, B 배열 각 인덱스가 초과되지 않을 때 까지 비교해서 합침
    while(idxA<arrA.length&&idxB<arrB.length) {
        if(arrA[idxA]<arrB[idxB]) {
            mergeArr[idx] = arrA[idxA];
            idx++;
            idxA++;
        }
        else {
            mergeArr[idx] = arrB[idxB];
            idx++;
            idxB++;
        }
    }
 
    // 한쪽이 다 스캔됐으면 나머지 한쪽은 full로 갖다 붙임
    if(idxA<arrA.length) {
        System.arraycopy(arrA, idxA, mergeArr, idx, length-idx);
    }
    else if(idxB<arrB.length) {
        System.arraycopy(arrB, idxB, mergeArr, idx, length-idx);
    }
 
 
        return mergeArr;
    }
}