[JAVA] 백준 2751번 수 정렬하기2 : 병합 정렬( Merger Sort )

2751번: 수 정렬하기 2

 

 

1. 문제 추상화

 

주어진 수의 나열을 시간복잡도 O(NlogN) 이상의 알고리즘으로 오름차순 정렬하라.

 

2. 알고리즘

 

O(NlogN) 시간복잡도는 정렬을 두 구간으로 분할정복할 때의 시간복잡도이다.

 

N개의 수를 N번 비교하면 O(N²) ( 버블정렬 )

N개의 수를 분할한 수만큼 비교하면 O(NlogN) ( 퀵정렬, 병합정렬 )

 

퀵정렬은 최악의 경우 O(N²)의 시간복잡도를 가진다. 테스트케이스 중 퀵정렬 저격용 최악의 경우도 있기 때문에 웬만하면 병합정렬로 푸는 것이 좋다. 병합 정렬은 퀵정렬과 다른 분할 방식으로 일정한 O(NlogN) 시간복잡도를 가진다. 

 

( 관련해서는 아래 포스팅 참고바랍니다!)

[알고리즘] 퀵 정렬 (Quick Sort)

[알고리즘] 합병 정렬 ( Merge Sort )

 

 

3. 코드

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

// 병합 정렬
public class Main {

	private static BufferedReader br;
	private static BufferedWriter bw;
	private static StringBuilder sb;
	
	private static int[] arr;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		createObjects();
		makeArr();
		initializeArr();
		doMergeSort(0,arr.length-1);
		printArr();
		closeBufferedIO();
	}
	
	public static void createObjects() {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
	}
	
	public static void makeArr() throws NumberFormatException, IOException {
		int size = Integer.parseInt(br.readLine());
		arr = new int[size];
	}
	
	public static void initializeArr() throws NumberFormatException, IOException {
		for(int i=0; i<arr.length;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
	}
	
	public static void doMergeSort(int left, int right) throws IOException {
		
		if(left < right) {
			int center = (left + right)/2;
			// 선 분할
			doMergeSort(left,center);
			doMergeSort(center+1,right);
			
			// 후 병합 알고리즘 적용
			applyMergeSort(left,right);
			
		}
	}
	
	public static void applyMergeSort(int left, int right) {
		
		int[] leftArr = new int[right - left +1];
		int center = (left+right)/2;
		int leftArrSize = 0;
		
		int arrPointer = left;
		int rightPointer = center+1;
		int leftPointer = 0;
		
		for(int i=left; i<=center;i++) {
			leftArr[leftArrSize++] = arr[i];
		}
		
		for(arrPointer = left; arrPointer <= right; arrPointer++) {
			if(leftPointer < leftArrSize && rightPointer <= right) {
				arr[arrPointer] = leftArr[leftPointer] < arr[rightPointer] ? leftArr[leftPointer++] : arr[rightPointer++];
			}else {
				break;
			}
		}
		
		while(leftPointer < leftArrSize) {
			arr[arrPointer++] = leftArr[leftPointer++];
		}
	}
	
	public static void printArr() throws IOException {
		sb = new StringBuilder();
		for(int value : arr) {
			sb.append(value).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
	}
	
	public static void closeBufferedIO() throws IOException {
		bw.close();
		br.close();
	}
}