[병합 정렬] 백준 2751번

문제

- 배열의 크기 N 제공
- 배열 제공 ( 개행을 통해 입력 )
- 해당 배열을 오름차순으로 정렬
(1<= N <= 1,000,000) , 시간제한 2초

 

문제분석

1,000,000이므로 O(NlogN)으로 해결할 수 있는 정렬 방법 탐색
- 병합정렬을 이용하여, 정렬 진행

 

 

병합정렬 예시

순서	배열
첫번째	42 (set1)	32 (set2)	24 (set3)	60 (set4)	15 (set5)	5 (set6)	90 (set7)	45 (set8)
두번째	32 (set1)	42 (set1)	24 (set2)	60 (set2)	5 (set3)	15 (set3)	45 (set4)	90 (set4)
세번째	24( set1)	32 (set1)	42 (set1)	60 (set1)	5 (set2)	15 (set2)	45 (set2)	90 (set2)
네번째 (정렬)	5	15	24	32	42	45	60	90

• set를 작은 단위의 그룹으로 나눈다
• 2개의 그룹씩 병합하며 정렬을 진행한다

 

2개의 그룹 정렬하는 방법 (기억하기!)

투포인터를 사용하여, 정렬 진행

24 (set1)	32 (set1)	42 (set1)	60 (set1)	5 (set2)	15 (set2)	45 (set2)	90 (set2)
(set1 인덱스)	-> 이동			(set2 인덱스)	-> 이동
(인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장)
5	15	24	32	42	45	60	90

• index를 서로 움직이면서, 더 작은 값을 먼저 배열에 저장하는 구조 ( 투포인터를 이용 )

 

 

구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bf.readLine());
        int[] arr = new int[size];
        int[] tmp = new int[size];
        for(int i =0; i<size; i++){
            arr[i] = Integer.parseInt(bf.readLine());
        }
        mergeSort(arr,tmp, 0, arr.length - 1);
        try{
            printArray(arr);
        }catch(IOException e){
            System.out.println(e);
        }
        
    }

    private static void mergeSort(int[] arr, int[] tmp,int startIndex, int endIndex){
        if (endIndex - startIndex < 1){
            return;
        }
        int middleIndex =startIndex+ (endIndex -startIndex)/2;
        mergeSort(arr, tmp,startIndex, middleIndex);
        mergeSort(arr, tmp,middleIndex + 1, endIndex);

        for(int i =startIndex; i<= endIndex; i++){
            tmp[i] = arr[i];
        }

        int index1 = startIndex;
        int index2 = middleIndex+1;
        int sortIndex = startIndex;
        while(index1 <= middleIndex && index2 <= endIndex){
            if( tmp[index1] > tmp[index2] ){
                arr[sortIndex] = tmp[index2];
                index2++;
                sortIndex++;
            }else{
                arr[sortIndex] = tmp[index1];
                index1++;
                sortIndex++;
            }
        }

        while(index1 <= middleIndex){
            arr[sortIndex] = tmp[index1];
            sortIndex++;
            index1++;
        }

        while(index2 <= endIndex){
            arr[sortIndex] = tmp[index2];
            sortIndex++;
            index2++;
        }
    }


    private static void printArray(int[] arr) throws IOException{

        for (int i : arr) {
            System.out.println(i);
        }
    }
}